The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
25 views

What is the precise mathematical definition of n-iterated recusion?

Primitive recursion can be extended to double-recursion as in the following link: http://www.andrew.cmu.edu/user/kk3n/recursionclass/1primrec.html How can this be generalized to n-iterated ...
0
votes
0answers
19 views

Between languages and problems [duplicate]

I have a pretty good handle on what recursive and recursively enume table languages mean with respect to Turing machines and how they relate to one another through my algorithms class. What I don't ...
-3
votes
1answer
189 views

What is a Universal Turing machine? [closed]

Could a Universal Turing machine be set up so that it is able to 'reprogram' itself to 'behave' like any specific Turing machine without using some 'outside' source of info to cause it to do this?
1
vote
1answer
38 views

Proving a language to be Recursively Enumerable?

I know to prove a language to be Recursively Enumerable, it is ideal to represent a Turing machine for it. Let L be set of strings which have alphabet {u,d,l,r}, where u is up 1, d is down 1, etc. L ...
4
votes
1answer
153 views

Primitive Recursion and course-of-values recursion - examples?

I ran into examples that I not trivially understand on course-of-values recursion, In defining a function by primitive recursion, the value of the next argument $f(n+1)$ depends only on the ...
0
votes
1answer
94 views

Many-one-reductions with finite image

Let $K$ be the halting set and suppose $K \leq_m A$ (under some function $f$), that is, $K$ is many-one-reducible to $A$. How can $f(K)$ be a finite set? Why if‌ $B$ is recursive, is $f^{-1}(B)$ ...
4
votes
1answer
71 views

What does it mean for something to be $\prod_x^y$-complete or $\sum_x^y$-complete?

I'm having trouble understanding the definitions for complexity classes in the arithmetic heirarchy, and because of the naming schemes, "Googling" things is somewhat difficult. Can anyone provide me ...
2
votes
3answers
57 views

Recursive methods with stacks

I'm doing some practice papers for revision for my finals and I came across this question: "This question is about recursion. A recursive method can always be implemented by an iterative method ...
13
votes
1answer
161 views

Is There a Complete Problem for the Class of Turing Decidable Problems?

Languages such as $\text{HALT}_{TM}$ are $\textsf{RE-complete}$ under many-one reductions. It is trivial to see that $\text{co-RE}$ has complete problems, too. S. Schmitz [1] considers some classes ...