Questions: Turing Machines

Question 1

A Turing machine M is run on input w and runs forever without halting. Which of the following is true?

• A. M accepts w
• B. M rejects w
• C. M neither accepts nor rejects w — it loops
• D. M accepts w if the tape contains only blank symbols after finite steps

Answer: (C)

Acceptance requires halting in a designated accept state; rejection requires halting in a reject state. Looping forever is a distinct third outcome — the machine neither accepts nor rejects. This is fundamental: the halting problem asks whether we can determine, for arbitrary M and w, which of these three outcomes will occur. The answer is no — no Turing machine can decide this in general.

Question 2

Because a Turing machine's tape is infinite, any real simulation of a Turing machine would require an unbounded amount of memory.

• T. True
• F. False

Answer: False

On any terminating computation, only a finite portion of the tape is ever visited or written. The tape is 'potentially infinite' as a theoretical convenience — guaranteeing the machine never runs out of scratch space — but a real computation halts after finitely many steps, having touched only finitely many cells. The infinite tape is an abstraction that removes resource constraints from the model, not a requirement for infinite physical memory.

Question 3

What does it mean for a function f: Σ* → Σ* to be Turing-computable?

Model answer: There exists a Turing machine that, when started on any input w encoding an argument in the function's domain, always halts and leaves the encoding of f(w) on the tape.

Turing-computability is the formal definition of 'algorithmically computable.' A function is computable if a Turing machine can produce the correct output for every valid input and always terminates. Functions that cannot be computed by any TM — such as the function that maps (M, w) to 1 if M halts on w and 0 otherwise — are formally uncomputable, regardless of how much time or memory is available.