The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
1answer
79 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 ...
-2
votes
0answers
39 views

Tautology and K Set in Computability book, a challenges? [closed]

We know from Martin Davis's book, $K$ is a Halting Set Problem as $K=\{e \mid e \in W_e\}$. Question: I read in the book that written the following aren't tautology: If $ W_{e_{1}} \neq ...
0
votes
1answer
78 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
62 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
45 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 ...
6
votes
0answers
58 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 ...