# Tagged Questions

Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

127 views

### completeness and creative

I'm trying to show that any complete $\Sigma_1^0$ set is creative. The definition of creative I understand is: if there is a total recurvise function f s.t. f(e) is an element of A iff f(e) is an ...
71 views

### recursive maps and decimal representation

I'm trying to think of an example of a real number $R$ such that the map $n \mapsto R[n]$, where $R[n]$ is the $n$th digit of the decimal representation of $R$, is not recursive. So I was thinking to ...
158 views

### recursive and creative theorem

How can we show that if A is creative, then A is not recursive. Only thing I can get out is the fact that if A is creative, if it is rec. enumerable and the complement(A) is productive. Thanks
185 views

### How does one prove that 1-generic set is not computable?

Without resorting to diagonalization proof of halting problem, how does one prove that 1-generic set is not computable?
165 views

### How to show Simp. and Creat. are $\Sigma^0_2$-Hard

Let Simp={$e:W_e$ is simple} and Creat={$e:W_e$ is creative} I'm having troubles showing these sets are $\Sigma^0_2$-Hard, ie that any $\Sigma^0_2$ set can be many-one reduced to them. I've already ...
72 views

### Identifying a pattern in an array

Is there a way to identifying a pattern and/or recursive function for an array? If yes, how can I do this. Could anyone please help me with some information and/or resource for this? Any help is ...
198 views

### Proof of Kleene's T predicate being primitive recursive

As I am looking over Kleene's T predicate, I was unable to find why Kleene's T predicate is primitive recursive. Can anyone show why? (I know what primitive recursive is.)
316 views

82 views

### Proving induction from basic recursion lemma

Induction Principle: Let $A$ be a set such that $0 \in A$ and $n \in A \implies n + 1 \in A$. Then for all $n \in \mathbb{N}$, $n \in A$. Basic Recursion Lemma: For all sets $X, W$ and given ...
54 views

### analytical hierarchy and individual variable quantifiers

For analytical hierarchy, $\Sigma^1_0$ is usually defined as the class of formula that does not have any set quantifier - but does this mean that there can be any number of quantifiers for individual ...
66 views

### $\mid$ in simply typed lambda calculus

$e = x \mid \lambda x\!:\!\tau.e \mid e \, e \mid c$ So, what is $\mid$ in this example of simply typed lambda calculus? The syntax of the simply typed lambda calculus is essentially that of ...
181 views

95 views

### Recursive functions, successor function

How to show that the power function $\displaystyle A=2^{m^2}$ is primitive recursive based on successor function? Thanks much in advance!!!
197 views

### Explain why if the language A is recursive, then A is reducible to 0*1*

I'm in a theory of computation class and there is a problem that I think I am way overthinking. Can anyone point me in the right direction with the following: Give a short justification of the fact ...
373 views

### Converse of Collatz Conjecture

How to write a pseudocode program that halts only if the Collatz Conjecture is false. Thanks much in advance!!!
181 views

### Recursive relation and predicate

If we let P(x,y) be a primitive recursive relation and g(x) be a primitive recursive function. Then how to show that there exists a y < g(x)*P(x,y) is a primitive recursive relation? And how can ...
600 views

### Turing machine that computes if two integers are equal

I am a philosophy student taking a Logic II class and I am scared. I have encountered the following question and I am bewildered about where to start or what to do. Design a Turing machine to ...
117 views

### Primitive Recursion maps

Is there an example of a bijective map pi: N^2 --> N (where N = natural #'s) which is primitive recursive? I'm thinking along the lines of projection function but can't quite spell it. Are there some ...
92 views

### $\omega-$model for $RCA_0$ and Proof of Ramsey's Theorem in $ACA_0$

These are two questions I encounter in Reverse Mathematics recently. In the characterization of the $\omega-model$ $M$ for $RCA_0$, the necessary and sufficient condition is $M$ is non-empty and ...
117 views

### Difference between language is decidable and function calculable by turing machine

I'm trying to understand the difference between saying a language is decidable and a function is calculable by a turing machine. I must have understood something wrong, because for me it doesn't make ...
103 views

### Sources on a category of ordinals

all I'm reading old papers on generalized recursion theory, and I've run across a paper by Van de Wiele ("Recursive dilators and generalized recursions") that 'lives in' the category ON, whose ...
223 views

### Ackermann function in terms of higher order recursion

Wikipedia provides a higher-order definition of Ackermann function. First it gives the normal recursive definition \begin{equation*} A(m,n)=\left\{ \begin{array}{ll} n+1 & \text{if $m=0$} \\ A(m-1,...
233 views

### Representing Recursion and Primitive Recursion diagrammatically

I'm interested in how Recursion, and Primitive Recursion, could be represented diagrammatically. It occurred to me that this would be a good way of seeing the difference. Also, I'm interested in how ...
76 views

### Prove $B = \{ \varphi_n(n) | n \in \mathsf{K} \}$ to be recursive

The set $B$ is the range of universal function given the domain $\mathsf{K}$, where $\mathsf{K} = \{ n | \varphi_n(n) \textit{ halts} \}$. How can we prove such claim?
I'm fairly certain this question has a very simple answer, and that I've learned it before; I just can't seem to remember it. Suppose I have a nonempty lightface Borel set $X\subseteq 2^\omega$. What ...
### On Cardinalities of $\mathcal{RE}$ and $\mathcal{P}(\mathbb{N})$
We denote $\mathcal{RE}$ as the universe set of recursively enumerable sets. A set is recursively enumerable iff its semi-charactersitic function is computable (one can write its semi-verifier). The ...