The tag has no usage guidance.

learn more… | top users | synonyms

3
votes
0answers
31 views

Axiomatisation in the presence of recursion [migrated]

I read Klaus Havelund's thesis on the Fork Calculus: http://havelund.com/Publications/thesis.ps He develops the Fork calculus for reasoning about concurrent functional programs, the motivation being ...
6
votes
1answer
72 views

Growth rate of primitive recursive functions

Pardon me for asking a question whose answer is surely well-known, but is beyond my expertise: Q. Is the growth rate of each primitive recursive function $f(n)$ bounded by some exponential ...
1
vote
0answers
40 views

Omitting parameters in primitive recursive functions

will replacing the usual schema of primitive recursion: $$ f(0,\vec x) = c (\vec x)\\ f(n+1,\vec x) = g(f(n,\vec x), n, \vec x) $$ by the form: $$ f(0,\vec x) = c(\vec x)\\ f(n+1,\vec x) = g(f(n,\vec ...
0
votes
1answer
54 views

How can I find tight asymptotic bounds for this half-history recurrence relation?

The recurrence relation $\forall n\in\mathbb{N}\cup\{0\}$ is $T(n)=\Theta(n^2)+2\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}{T(i)}$, with base case of $T(0)=0$. Fairly simple tree analysis shows that ...
15
votes
4answers
472 views

Program reasoning about own source code

The inspiration for this question is the following (vague) question: What are the programming language/logical foundations for having an AI which could reason about its own source code and modify it? ...
2
votes
0answers
105 views

Is there a closed form equation for the back-propagation equation update in Neural Networks?

I was trying to understand if there was a way to express the back-propagation equations from neural networks in a better way as to understand them better. I believe the equations can be written in a ...
8
votes
3answers
635 views

Are there problems for which divide-and-conquer / recursion is provably useless?

When we try to construct an algorithm for a new problem, divide-and-conquer (using recursion) is one of the first approaches that we try. But in some cases, this approach seems fruitless as the ...
5
votes
1answer
88 views

Extending simple types to allow `fix`

I'm reading some lecture notes saying that “fix cannot be defined in the simply typed lambda-calculus” and that “no expression that can lead to non-terminating ...
5
votes
2answers
161 views

Higher order Quines - when do super Quines exist?

The normal Quine - a program that prints its own code - is a special case of an n-Quine. An n-Quine is a program that prints code for a different program that after n iterations of printing and ...
1
vote
1answer
519 views

Difference between a cyclic and a left-recursive context-free grammar?

I am currently reading a paper indicating that a cyclic CFG and a left-recursive CFG are different things: The original purpose of the LC transform is to allow simulation of left-corner parsing ...
2
votes
1answer
176 views

recursion schemes that prune

Probably the most common recursion scheme is the catamorphism, or fold. This is a recursion that takes a data type and "deconstructs" it into something else. For example, we can calculate the length ...
5
votes
1answer
777 views

Trampoline that automatically balances heap and stack

While working through Fogus' Functional Javascript, I came across the trampoline function, which can be used to make safe recursive functions that don't blow up the stack. In Fogus' words, "Of course ...
6
votes
2answers
296 views

Does “Productive function” mean just that in ME O'Neill, The Genuine Sieve of Eratosthenes?

M.E. O'Neill in the Epilogue of "The Genuine Sieve of Eratosthenes" (preprint http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf DOI 10.1017/S0956796808007004) quotes Richard Bird that "union is ...
4
votes
2answers
225 views

Mathematical explanation of recursion and lambda (referenced in The Little Schemer)

In the preface of Friedman and Felleisen's book The Little Schemer it states: We could, for example, describe the entire technical content of this book in less than a page of mathematics, but a ...
2
votes
0answers
110 views

Recursion Schemes for Static Analysis (AST)

In the process of creating an AST analysis framework one of the challenges is creating good reusable functions and to avoid too much boiler-plate code. To that end catamorphisms seem like a good fit, ...
9
votes
6answers
2k views

Removing recursion - a look into theory behind the scenes

I am new to this site and this question is certainly not research level - but oh well. I have a little background in software engineering and almost none in CSTheory, but I find it attractive. To make ...
3
votes
2answers
1k views

Stack memory usage for tail calls

I'm puzzled by this statement from Wikipedia: For tail calls, there is no need to remember the place we are calling from — instead, we can perform tail call elimination by leaving the stack ...
6
votes
1answer
380 views

Parallel solution of recurrence equation

One of the most well known parallel algorithms for the solution of recurrence equations is the one proposed by Kogge and Stone (it can be found here). They proved that all recurrence equations of the ...
14
votes
5answers
1k views

History of recursion

Who introduced the idea of recursion? Can someone explain where it came from and how it impacted computer science?