# Questions tagged [recursive]

The tag has no usage guidance.

10 questions
Filter by
Sorted by
Tagged with
44 views

### Check if language is decidable [closed]

I would like to determine if the following language is decidable or not. L = { w $\in$ $\Sigma^*$ | $T(M_w)$ is recognized by a Turing machine with at most 42 states}. I know that every finite ...
146 views

### Turing meta-oracle

Let H(P) be some program that given P('s source code) computes whether or not P terminates, i.e. solves the halting problem. H only needs to terminate if P terminates. (This disallows solutions like ...
135 views

### What is the relationship between tail recursion with other recursions? [closed]

I'm rather confused by the recursion theory. From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But ...
434 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 $O(c^n)$,...
782 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 ...
377 views

### Primitive Recursive Isomorphisms

What is the relationship between invertible primitive recursive functions (that is, a primitive recursive function that is an isomorphism) and all primitive recursive functions? Can every primitive ...
262 views

### How to describe the set of “all computable functions” using Coq?

Would the set of all computable functions be just the set of all maps of the form f : forall n : nat, P n -> nat where ...
100 views

### Computational complexity of some recursive property

I am currently working on a property of graphs defined as follows. A graph $G$ is said to be OL-AP iff one of the following two conditions holds: $G$ is an isolated vertex. $G$ is connected and for ...
Consider the following algorithm, where $c$ is a fixed constant. ...