Which of the following correctly describes a Turing machine that *decides* a language?
AIt accepts every string in the language and may loop forever on strings not in it
BIt halts on every input, accepting strings in the language and rejecting all others
CIt rejects every string not in the language but may loop on strings that are in it
DIt always moves rightward and halts when it reaches a blank symbol
A decider must halt on all inputs — both accepting members and explicitly rejecting non-members. A recognizer (Turing-acceptable) only guarantees halting on members; it may loop forever on non-members. This accept/reject/loop trichotomy is the central distinction in computability theory.
Question 2 True / False
A Turing machine is essentially a mathematical model of a modern computer — both have finite memory and equivalent computational power.
TTrue
FFalse
Answer: False
A Turing machine has an *infinite* tape, giving it unbounded working memory — far more idealized than any real computer. Real computers have finite memory, which technically makes them closer to finite automata. The TM is a theoretical abstraction used to define the limits of computation, not a description of physical hardware.
Question 3 Short Answer
What is the key property that makes Turing machines more computationally powerful than pushdown automata?
Think about your answer, then reveal below.
Model answer: The ability to move bidirectionally on an infinite read-write tape, reading and rewriting arbitrary cells — replacing the limited LIFO stack with unrestricted working memory.
PDAs use a stack — last-in, first-out memory that can only be accessed from the top. A TM's tape head can move left or right and rewrite any cell, giving it full random-access working memory. This allows TMs to recognize languages like {aⁿbⁿcⁿ} that PDAs cannot, and underpins the Church-Turing thesis that TMs capture all effectively computable functions.