1
$\begingroup$

I want to find out whether the following sets are decidable or not. Generally speaking, what exactly should be done about it? Doing some research, I think a language or set is decidable if a Turing machine exists that decides it, meaning the output for a given input is "yes" or "no". Please shed some light on the problem.

  1. $\{x|x \text{is the code of a Turing machine that always halts in less than a finite number of steps}\}$
  2. $\{x|x \text{is the code of a Turing machine that uses at most thousand cells on its tape}\}$
$\endgroup$
  • $\begingroup$ If you would like to separate the questions, simply keep this as number 1, and ask 2-5 in other questions. Hopefully, Hagen won't mind moving his answer for 2 to your other question (it will probably mean more reputation :-). $\endgroup$ – robjohn May 13 '13 at 8:26
  • $\begingroup$ @robjohn: I'd rather keep number one and two here so that Hagen's answer is still valid. Thank you for your help. $\endgroup$ – Gigili May 13 '13 at 15:14
2
+200
$\begingroup$

I understood $A$ to be

$A = \{x : $ there exists a $n$ such that $\Phi_x(y)$ halts in less than $n$ steps for all $y\}$.

$A$ is not computable. $K$ is known to be incomputable. So we will make a reduction of $K$ to $A$. For each $e \in \omega$, we will make a Turing machine $T_e$ as follows: For any input $y$, $T_e$ will start running $\Phi_e(e)$. If $\Phi_e(e)$ does converge, then at this same stage $T_e(y)$ will converge. If $\Phi_e(e)$ does not coverge then $T_e(y)$ will not converge. There is a computable function $f$ that maps $e$ to the index of the Turing program $T_e$.

The claim is that this $f$ is the many to one reduction $K \leq_m A$. To see this, if $e \in K$, then $\Phi_e(e) \downarrow$. Then there is a least $n$ such that $\Phi_{e}(e)\downarrow$ in $n$ steps. Thus $\Phi_{f(e)} = T_e$ will converge on every input $y$ in $n$ steps. Hence $f(e) \in A$. If $e \notin K$, then $\Phi_e(e)\uparrow$. $\Phi_e$ does not converge on $e$. hence $T_e = \Phi_{f(e)}$ does not converge on any input. Thus $f(e) \notin A$.

Since $K \leq_m A$ and $K$ is not computable, $A$ is not computable.

Let $B$ denote the second set. Since $K$ is not computable, $\bar{K}$, its complement, is also not computable. We will strive to make a reduction $\bar{K} \leq_m B$.

For each $e \in \omega$, we will make a Turing machine $T_e$ as follows: On any input $y$, start running $\Phi_e(e)$. At every stage such that $\Phi_e(e)$ does not halt, the Turing program $T_e$ will stay put on the current box of the tape. For every step such that $\Phi_e(e)$ does halt, then $T_e$ will write a zero in the box and move to the right.

Let $f$ be the computable function taking $e$ to the index of the Turing pargram $T_e$. Observe that for any $e$ and $y$, $T_e(y) = \Phi_{f(e)}$ does not halt. However if $x \in \bar{K}$, then $\Phi_e(e) \uparrow$. Hence $T_e$ on any input will not halt but use only 1 box (the first original box). This shows that $f(e) \in B$. If $e \in \bar{K}$, then $\Phi_e(e)\downarrow$. $\Phi_e(e)$ will eventually halt. After this point $T_e$ on any input will move to the right forever. So $T_e$ will use infinitely many boxes on the tape. Thus $f(e) \notin B$.

This is the desired reduction $\bar{K} \leq B$. Since $\bar{K}$ is not computable, $B$ is not either.

$\endgroup$
  • $\begingroup$ Thank you. So you're saying that they're not decidable? $\endgroup$ – Gigili May 17 '13 at 17:05
  • $\begingroup$ I don't understand very well, how the set you defined is equal to the set $A$ in my question? $\endgroup$ – Gigili May 17 '13 at 17:12
  • 1
    $\begingroup$ @Gigili The set $A$ is the set of all index such that there exists a $n$ such that on all input you halt in less than $n$ step. So there is a bound on the time it takes to halt that works for all inputs. Without this, your set just the set of all index of Turing machine that halt on all input. This is just Tot, the set of all total computable function, which is well known to be incomputable. In fact, complete $\Pi_2^0$. (You can not halt in infinitely many steps.) $\endgroup$ – William May 17 '13 at 18:29
  • $\begingroup$ Could you provide some sources that further explains the subject? $\endgroup$ – Gigili Jun 9 '13 at 13:41
1
$\begingroup$
  1. A Turing machine is able to emulate machine $x$ for 1000 steps (including the finitely many visible input tapes the machine might see during 1000 steps), so decidable.

  2. If $x$ has $n$ states, then the machine plus tape plus position on tape has something like $2^{1000}\cdot 1000\cdot n$ possibilities and it can be verified in finite time whether the machine will or will not "jump out of" these finitely many possibilities. Decidable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.