# 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).

119 views

120 views

### Proving the free occurrence of a variable is primitive recursive

Show that FreeOcc$(m,n,i)$, which holds when $m$ is the godel number of a wff $\varphi$ and the $i^{th}$ symbol of $\varphi$ is a free occurrence of the variable $x_{n}$, is primitive recursive. ...
113 views

### Example of sets $A, B$ such that $A', B'$ are Turing equivalent but $A, B$ are not.

I have been wondering if the following statement is true, $$A\equiv_TB\iff A'\equiv_TB'$$ where $A, B\subseteq\omega$ and $A'$ denotes the Turing jump of $A$. I have been able to show ...
378 views

### the set of sentences (i.e. closed formulas) of first-order logic and the Chomsky hierarchy

The set of well-formed formulas (wffs) in first-order logic (FOL) is decidable, because it's straightforward to translate the standard recursive syntax rules into a context free grammar, and all ...
600 views

### Non-recursive subset which is recursively enumerable

What is an example of recursively enumerable subset of the natural numbers which is not recursive?
185 views

### “direct” ways in which a non-computable number is used?

I was wondering whether non-computable numbers are ever of "direct" use ? I understand they are immensely useful indirectly, because we need them to do analysis in the real numbers for instance. ...
125 views

### Showing a set $\Sigma^0_n$ subset of $\mathbb{N}$ is $\Sigma^0_n$-complete

This is both a general and specific question in basic computability theory. Broadly speaking, I am not very comfortable with showing whether or not a subset of $\mathbb{N}$ is $\Sigma^0_n$ (or ...
126 views

### Relationship between $\Sigma_{1}$ and $\Pi_{1}$ functions (Logic)

I am working on the following homework problem for a logic class on Godel's incompleteness theorems and the following question is asked. Is the converse of Theorem $13.1$ true? Explain. Theorem ...
213 views

### Help on two exercises about computability theory

In Cooper's book, I can't think out the solutions of two exercises. 1.show that there exists a simple set S contains the set of all even numbers. 2.show that each creative set is contained in some ...