Re: Question on another GRE Comp Sci problem (Turing Machine stuff...)
- From: Markus Redeker <cep@xxxxxx>
- Date: Sat, 27 Aug 2005 10:52:33 +0200
"Federico Magallanez" <steganographer@xxxxxxxxx> writes:
>----
>47. Let M be a single-tape, deterministic Turing machine with tape
>alphabet {blank,0,1}, and let C denote the (possibly infinite)
>computation of M starting with a blank tape. The input to each problem
>below is M, together with a positive integer n. Which of the following
>problems is (are) decidable?
>I. The computation C lasts for at least n steps.
>II. The computation C lasts for at least n steps, and M prints a 1 at
>some point after the nth step.
>III. M scans at least n distinct tape squares during the computation C.
>----
>My guess was 'all these three are decidable'; however, the answer is 'I
>and III are decidable while II is undecidable.' Maybe my understanding
>on TM is quite sloppy, but I cannot understand why 'M prints a 1 at
>some point after n-th step' makes such a glaring difference. I
>appreciate any input.
The main point is that II involves an infinite number of steps. E.g., if you
have mointored the TM for N steps (where N is some big number greater than
n) and it didn'd write a 1, you cannot be sure that it won't do in future.
More detailled, you could take any Turing Machine M' operating on {0,1}
and modify it to use {blank,0} instead. Let it wait at the beginning for n
steps -- which can be done by adding n states -- and let it write a 1 when
M' halts. Then II is equivalent to the halting problem for M'.
III is more subtle. M could run forever on a finite number of squares, but
then it would have to repeat itself, which could be detected in a finite
number of steps.
Nice exercises.
--
Markus Redeker Hamburg, Germany
.
- References:
- Question on another GRE Comp Sci problem (Turing Machine stuff...)
- From: Federico Magallanez
- Question on another GRE Comp Sci problem (Turing Machine stuff...)
- Prev by Date: Question on another GRE Comp Sci problem (Turing Machine stuff...)
- Next by Date: What does 'recursive' or 'recursively enumerable' literally mean?
- Previous by thread: Question on another GRE Comp Sci problem (Turing Machine stuff...)
- Next by thread: What does 'recursive' or 'recursively enumerable' literally mean?
- Index(es):
Relevant Pages
|
