Turing machines Flashcards
What is the most powerful computational model introduced in this course?
The Turing Machine.
What are the two components of a Turing Machine?
A head (control unit) and a tape (infinite memory).
What can a Turing machine do at each step?
Read a symbol, write a symbol, and move left or right on the tape.
What type of memory does a Turing machine use?
An infinite tape of cells storing symbols.
What language can a finite automaton not recognize?
L = { aⁿbⁿ | n ≥ 0 }
What language can a pushdown automaton not recognize?
L = { aⁿbⁿcⁿ | n ≥ 0 }
What language is undecidable by any machine?
The halting problem.
What is the formal definition of a Turing machine?
A 6-tuple (Q, Σ, Σ₀, s, δ, H) with states, tape alphabet, input alphabet, start state, transition function, and halting states.
What symbols must be included in the tape alphabet of a Turing machine?
▷ (start-of-tape marker) and ⊔ (blank symbol).
What are halting states in a Turing machine?
States in which the machine stops executing.
Can a Turing machine move left off the tape?
No — it cannot move left from the start-of-tape marker ▷.
What is a configuration of a Turing machine?
A 4-part description (q, u, a, v) — current state, left content, current symbol, right content.
How is a computation defined in a Turing machine?
A sequence of configurations from the initial to a halting configuration.
What does it mean for a Turing machine to accept a word?
It halts on the input in an accepting state.
What is a semidecidable language?
A language where the TM halts for all strings in the language but may run forever on others.
What is a decidable language?
A language for which a TM halts on all inputs, accepting or rejecting correctly.
What is another name for a decidable language?
A recursive or Turing-decidable language.
What condition must hold for a language to be decidable?
Both the language and its complement must be semidecidable.
What is the Church-Turing Thesis (informally)?
Everything computable by an algorithm can be computed by a Turing machine.
What does the Turing machine model provide in theoretical computer science?
A precise definition of computation and computability.
