4.5 Computability

• What is a Turing Machine used for in theoretical computer science?

  Simulating algorithmic procedures
• A Turing Machine tape is divided into cells that can each hold a single symbol
• The head of a Turing Machine can only move right.

  False
• What does the state register in a Turing Machine record?

  Current state
• The transition function in a Turing Machine maps the current state and tape symbol to a new state, a symbol to write, and a direction
• Arrange the components of a Turing Machine as illustrated in the diagram:

  1️⃣ State

  2️⃣ Head

  3️⃣ Tape
• The tape in a Turing Machine can only contain symbols from a finite alphabet.
• What is the function of the read/write head in a Turing Machine?

  Reads and writes symbols
• The state register in a Turing Machine stores the current state
• A Turing Machine can only accept or reject strings of symbols, it cannot modify them.

  False
• What is a decidable problem in the context of Turing Machines?

  Solved in finite time
• An undecidable problem cannot be solved by a Turing Machine in a finite amount of time
• Match the problem type with its definition and Turing Machine behavior:

  Decidable ↔️ Can be solved in finite time, halts with yes or no

  Undecidable ↔️ Cannot be solved in finite time, may run forever
• The Halting Problem is an example of an undecidable problem.
• A decidable problem can be solved in finite time
• An undecidable problem may run forever or halt without a decision
• The halting problem is an example of an undecidable problem
• A decidable problem halts with a yes or no
• An undecidable problem may run forever
• The halting problem asks whether a Turing Machine will halt given an input string
• The halting problem is undecidable
• Match the problem type with its characteristic:

  Decidable ↔️ Can be solved in finite time

  Undecidable ↔️ No finite time solution
• Steps of a Turing Machine with input "10" according to the example rules

  1️⃣ Read 1, write 0, move left to $q_{1}$

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

  3️⃣ Read 1, continue moving right until a blank is found, then halt
• The halting problem highlights the limitations of computation
• There are problems that cannot be solved by any algorithm
• What are the four main components of a Turing Machine?

  Tape, head, state register, transition function
• The tape of a Turing Machine stores input and output
• The state register tracks the current machine state
• Match the problem type with its Turing Machine behavior:

  Decidable ↔️ Halts with yes or no

  Undecidable ↔️ May run forever
• A string belongs to a regular language is decidable, whereas the halting problem is undecidable.
• What is the halting problem in computability theory?

  Determine if a Turing Machine halts
• The halting problem is undecidable for all possible inputs.
• Steps of a Turing Machine with input "10" based on the given rules:

  1️⃣ Read 1, write 0, move left to state $q_{1}$

  2️⃣ Read 0, write 1, move right to state $q_{2}$

  3️⃣ Halt because no rules for state $q_{2}$
• The halting problem highlights the limitations of computation.
• The Church-Turing thesis states that any problem solvable by an algorithm can be solved by a Turing Machine.
• What evidence supports the Church-Turing thesis?

  Equivalency proofs between models
• Computability refers to the ability of a problem to be solved by a computer program or algorithm.
• What is an example of an undecidable problem in computability?

  Halting problem
• Searching a list is an example of a decidable problem.
• Steps of a Turing Machine designed to print prime numbers based on the given rules:

  1️⃣ Read 0, write 1, move right to state $q_{1}$

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

  3️⃣ Read $␣$, write $␣$, move to HALT