4.4 Turing machines

• What is a Turing machine?

  Theoretical model of computation
• A Turing machine manipulates symbols on an infinite tape
• What is the purpose of the infinite tape in a Turing machine?

  Stores symbols
• Match the computational problem with the corresponding action in a Turing machine:

  Counting numbers ↔️ Read, write, move

  Sorting a list ↔️ Compare, swap, move

  Searching an array ↔️ Read, move
• Sequence the steps a Turing machine takes to count numbers:

  1️⃣ Start in state $q_{0}$ with "123□" on the tape

  2️⃣ Read "1", write "1", move right, transition to $q_{1}$

  3️⃣ Read "2", write "2", move right, transition to $q_{2}$

  4️⃣ Read "3", write "3", move right, transition to $q_{3}$

  5️⃣ Read "□", write "□", move left, halt
• All computational problems can be solved by a Turing machine.

  False
• What is the classic undecidable problem for Turing machines?

  The halting problem
• The halting problem is an example of an undecidable problem.
• Match the problem type with its characteristic in Turing machines:

  Decidable problem ↔️ Machine always halts with yes or no

  Undecidable problem ↔️ Machine may not halt or provide an answer
• The distinction between decidable and undecidable problems highlights the bounds of what can be computed.
• Match the computational model with its memory and language recognized:

  FSA ↔️ Limited memory, Regular languages

  PDA ↔️ Stack, Context-free languages

  Turing machine ↔️ Infinite tape, Context-sensitive and recursive languages
• Deterministic Turing machines follow a unique path based on the current state and tape symbol.
• The read/write head of a Turing machine can only move left.

  False
• What dictates the actions of a Turing machine based on the current state and symbol read?

  Transition rules
• The read/write head allows the Turing machine to process information
• Match the components of a Turing machine with their descriptions:

  Infinite Tape ↔️ Stores symbols in cells

  Read/Write Head ↔️ Reads and writes symbols

  Finite Set of States ↔️ Represents machine's context

  Transition Rules ↔️ Dictate actions based on state
• What is the alphabet of a Turing machine?

  Finite set of symbols
• The alphabet of a Turing machine includes the blank symbol.
• What is the alphabet of a Turing machine designed to add two binary numbers?

  $\Sigma =$$\{0, 1, □\}$
• A Turing machine is a theoretical model of computation that manipulates symbols on an infinite tape
• The infinite tape of a Turing machine is divided into cells
• The read/write head of a Turing machine can move left or right
• The transition rules of a Turing machine are based on the current state and the symbol read
• The infinite tape of a Turing machine is divided into cells, each holding a symbol.
• The finite set of states in a Turing machine represents the machine's current context
• Transition rules in a Turing machine dictate actions based on the current state and symbol read.
• The components of a Turing machine work together to read, write, and process information on the tape
• Key components of a Turing machine

  1️⃣ Infinite Tape

  2️⃣ Read/Write Head

  3️⃣ Finite Set of States

  4️⃣ Transition Rules
• The alphabet of a Turing machine includes the blank symbol.
• For a Turing machine adding binary numbers, the alphabet might be $\Sigma =$$\{0, 1, □\}$, where $□$ represents the blank
• The transition function in a Turing machine specifies the next state to transition to.
• The transition function in a Turing machine determines the symbol to write
• If the current state is `q0` and the symbol read is `0`, the transition function might specify to move to state `q1`, write `1`, and move right.
• Steps in the operation of a Turing machine

  1️⃣ The read/write head reads the symbol from the current cell on the tape.

  2️⃣ The machine determines the next action using the transition function.

  3️⃣ The transition function specifies the next state, symbol to write, and head movement.

  4️⃣ The head moves accordingly, updating the tape and transitioning to the next state.
• The read/write head moves one cell to the right after updating the tape.
• What does a Turing machine's read/write head read from the current cell?

  Symbol
• The transition function specifies the next state, the new symbol to write, and the direction to move the read/write head
• A Turing machine uses an infinite tape divided into cells, each holding a symbol.
• What is the purpose of the read/write head in a Turing machine?

  Reads and writes symbols
• The finite set of states in a Turing machine represents the machine's context