0
$\begingroup$

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?

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

  2. For the Rice's theorem:

    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?

$\endgroup$
2
+100
$\begingroup$

Suppose D is a decider for (1).

HALT(A, w):   
1) Construct M = "On input n:
                 100) Run A on w
                 200) if n <= 1000
                 300)    accept
                 400) else
                 500)    reject
                 "
2) if D accepts M
     accept
   else
     reject

Notice that:
$\quad\quad$D accepts M ⇒ A halts on w in line 100
$\quad\quad$D rejects M ⇒ A loops on w in line 100

So, if D existed HALT(A, w) would be a decider for the Halting Problem. So, D cannot exist and (1) must be undecidable.

Note that there is some ambiguity in problem (1). If you assume that the inputs can only be natural numbers then your solution works and the problem is decidable. If you assume like I did that the input can be any number, then the problem is undecidable.

For problem (2), just change step 1 to:
1) Construct M = "On input n: 100) Run A on w 200) return 1001 "

For problem (3), just change step 1 to:
1) Construct M = "On input n: 100) Run A on w 200) return 1 "

Notice that in all 3 proofs, you first construct an algorithm M so that it decides the language defined in (1), (2) and (3) iff A halts on w.

For Rice's Theorem we will use problem (1) as an example.
For $(1), P = \{<M> : M$ accepts $n \le 1000$ within 1000 steps $\}$
To use Rice's Theorem, the following 2 conditions must hold:

a) $P$ is non-trivial
$\quad$Informally, this just means that $P$ does not contain all TM's.
$\quad$Formally, there exists $M_1$, $M_2$ such that $M_1 \in P$ and $M_2 \notin P$
$\quad$Clearly this condition holds for $P$

b) $P$ is a property of decidable languages
$\quad$Formally, if $L(M_1) = L(M_2)$ then $\langle M_1 \rangle \in P$ iff $\langle M_2 \rangle \in P$
$\quad$This condition does not hold for $P$.
$\quad$For example, we have $L(M_1) = L(M_2) = \{w: w \le 1000\}$
$\quad$ However if $M_1$ accepts within 1000 steps while $M_2$ accepts after 1000 steps then $M_1 \in P$ but $\quad M_2 \notin P$
$\quad$ So, Rice's Theorem is not applicable in this case.

Informally, Rice's Theorem differentiates between what a TM must compute vs how it does the computation. The "what" is a property of the language $P$. The "how" is a property of the TM. For example, consider TM's that decide whether an input number is prime. That is a property of P. But the details of how the TM decides whether a number is prime is a property of the TM.

Now consider problem (2)
$\quad P = \{ \langle M \rangle$ : for some input w, M gives a number that can be interpreted as a palindrome $\}$
$\quad$Now, $M \in P$ would mean $L(M) = \{w$ : On input w, M returns a number that can be $\quad$interpreted as a palindrome. In this case you can verify for yourself that Rice's Theorem applies.

Hope this helps.

$\endgroup$
  • $\begingroup$ About applying Rice's theorem at (2) do we have to give an input $w$ where the output cannot be interpreted as a palindrome and one so that the output can be interpreted as a palindrome? $\endgroup$ – Mary Star Jul 14 at 18:24
  • $\begingroup$ So, for example let $M_1$ be a machine so that $M_1(w)=010$ and let $M_2$ be a machine so that $M_2(w)=0w1$ ? $\endgroup$ – Mary Star Jul 14 at 18:29
  • 1
    $\begingroup$ To prove that P is not trivial in (2), you can construct a TM that never returns a palindrome on all inputs. For example, just have it return "10" on all inputs. To prove that P is a property of decidable languages, note that L($M_1$) = $\{ w : M_1$ on input w returns a palindrome $\}$. Now, if $L(M_1) = L(M_2)$ then it is clear that we must have $M_1 \in P$ iff $M_2 \in P$ $\endgroup$ – user137481 Jul 15 at 0:42
  • $\begingroup$ Thank you very much!! :-) $\endgroup$ – Mary Star Jul 18 at 17:21

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.