Decidability and undecidability of a set or language

Question

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}\}$

Answer 1

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.

Answer 2

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.