- Thread starter
- #1

- Apr 14, 2013

- 4,008

Are the following questions decidable? Give an appropriate algorithm or show that the problem is undecidable using Rice's theorem.

- Does an arbitrary Turing machine halt with all inputs less than or equal to 1000 within the first 1000 steps?

- Does an arbitrary algorithm with the appropriate input give a number, that interpreted as a string, it is palindrome?

- Does an arbitrary algorithm, that does not halt for at least one input, give any natural number as an output value?

I have done the following:

- It is decidable whether a deterministic Turing halts within the first $ 1000 $ steps for any input less than or equal to $ 1000 $.

We execute the Turing machine sequentially on all words $ w \in \Sigma^{\star} $ with $ w \leq 1000 $ for a maximum of $ 1000 $ steps.

If we have simulated at most $ 1000 $ steps, we hold and the output is "yes", otherwise we stop as soon as we have simulated the Turing machine on all words $ w $ and the output is "no".

Is this correct?

- To use Rice's theorem do we have to find a function that has a palindrome output and one that has not a palindrome output, to get a non-trivial property?

- Let $\phi$ be the function that is computed by an algorithm. We consider the set $M=\{i\in \mathbb{N}_0\mid \text{ For all } n\in \mathbb{N}_0 \ \phi_i(n) \text{ is defined }\}$, or not?

Let $i,j \in \mathbb{N}_0$ with $\phi_i = n$ for some natural number $n\in \mathbb{N}$ and $\phi_j\neq m\in \mathbb{N}$ (since the machine does not halt for at least one input).

Then $i \in M$ and $j \notin M$, so $M\neq \emptyset$ and $M\neq \mathbb{N}_0$, and now we acan apply Rice's theorem.

Is that correct?