# 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

### Is this language decidable?

Is this language decidable? $$\{x\mid \text{x is the code of a Turing machine that always halts on y in less than y^3 steps}\}$$ I think it is, because it halts in a finite number of ...
79 views

99 views

### If $L\in REG$ then $M$ has a finite number of distinct rows

Let $L \subseteq \Sigma^{\star}$ and let $M^{\Sigma^{\star} \times \Sigma^{\star}}(\{0,1\})$ an infinite matrix such that for each $x,y\in \Sigma^\star$:  m_{x,y}=\begin{cases} 1 & x y\in L\\ 0 &...
111 views

### Computability function - how to express it in set theory/arithmetic hierarchy

Let's say that $f$ is computable function such that for particular inputs $x$ and $y$, $f(x) = 0$ and $f(y) = 0$. If we want to express this in logical form (arithmetic hierarchy formula), what would ...
129 views

### recursively enumerable of Godel numbering

There are statements for natural number x, like followings m: "x is even natural number" n: "x+1 is odd number and x>1" l: "x is positive integer multiple of two" m, n, l has same boolean value ...
85 views

### What's the error in this argument that Fin$\le_m$Inf

There must be an error in the following argument since Fin is not many-one reducible to Inf, I can't seem to find it. Here it is informally (I hope it's straightforward and not confusing): Take any ...
84 views

### For a one-to-one function is the pullback of a recursively enumerable set $f^{-1}[W_e] = W_{g(e)}$ where $g$ is one-to-one?

Let $\phi_e : \mathbb{N} \to \mathbb{N}$ be the recursive function coded by $e$ and $W_e = \{ x : \phi_e(x) \text{ is convergent}\}$. A set $A$ is recursively enumerable if $A = W_e$ for some $e$. ...
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
181 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?
### 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 ...