Question on another GRE Comp Sci problem (Turing Machine stuff...)
- From: "Federico Magallanez" <steganographer@xxxxxxxxx>
- Date: 27 Aug 2005 00:40:39 -0700
I have downloaded the official GRE CS problem at
http://ftp.ets.org/pub/gre/CompSci.pdf and try to solve it. The
following problem is rather tough to deal with.
----
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.
Thanks.
.
- Follow-Ups:
- Re: Question on another GRE Comp Sci problem (Turing Machine stuff...)
- From: Markus Redeker
- Re: Question on another GRE Comp Sci problem (Turing Machine stuff...)
- Prev by Date: Canadian Universities
- Next by Date: Re: Question on another GRE Comp Sci problem (Turing Machine stuff...)
- Previous by thread: Canadian Universities
- Next by thread: Re: Question on another GRE Comp Sci problem (Turing Machine stuff...)
- Index(es):
Relevant Pages
|