MHB Can Turing Machine Decidability Extend to Complex Algorithm Outputs?

[mathmari]

Hey!

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

1. Does an arbitrary Turing machine halt with all inputs less than or equal to 1000 within the first 1000 steps?
   
2. Does an arbitrary algorithm with the appropriate input give a number, that interpreted as a string, it is palindrome?
   
3. 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:

1. 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?
   
2. 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?
   
3. 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?

(Wondering)

 

[Evgeny.Makarov]

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.

Strictly speaking, it is not clear how to compare a word $w$ and the number 1000, and what the alphabet $\Sigma$ is in this case.

If we have simulated at most $ 1000 $ steps, we hold

"Halt", not "hold". Can we halt after 5 steps because 5 is less than 1000?

and the output is "yes"

After running the machine on a single word?

In general I agree with this answer, but it should be written more precisely, possibly using pseudocode.

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

Please write the version of Rice's theorem you are using. Sometimes, for example in te Sipser's textbook, it is formulated for machines that only accept or reject their input but otherwise produce no output.

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

What else can a machine give as an output value? I am not sure I understand the property of algorithms that has to be recognized. Could you write it more precisely, preferably using a formula?

Let $\phi$ be the function that is computed by an algorithm.

This sound like "Let $y$ be the square of a number". Which number?