Computing_Principles_Quiz 2

What is the main difference between a finite automaton and a Turing machine?

• A. A Turing machine has infinite states.

• B. A Turing machine can move backwards.

• C. A Turing machine can read and write on the tape.

• D. A finite automaton can solve any problem.

What does the Church–Turing Thesis state?

• A. All problems are solvable by Turing machines.

• B. Computers are faster than Turing machines.

• C. All reasonable models of computation are equivalent to Turing machines.

• D. Only Turing machines can process numbers.

A Turing machine can run forever on some inputs

• True

• False

All problems can be solved by a Turing machine.

• True

• False

What makes a programming language “Turing-complete”?

( Many options )

• 1. It can simulate a Turing machine, including features like conditional branching (if/else), loops, and mutable variables.

• It supports recursion or infinite loops, along with the ability to read/write data to memory arbitrarily.

• It can solve any computational problem that a Turing machine can solve, given sufficient time and resources.

• It only needs to support variable assignment and comparisons, without requiring complex control structures.

What is an undecidable problem ( Many options )

• A problem for which no algorithm can be constructed to always produce a correct yes/no answer

• A problem that is too complex for current computers but might be solvable with future technology.

• 1. A problem that cannot be solved by any Turing machine, regardless of time and memory.

• A problem where some instances may have solutions, but no general algorithm exists for all cases.

All context-free languages can be accepted by a Turing machine

• True

• False

A semi-decidable language has a Turing machine that always halts

• True

• False

Which of the following is an example of a decidable problem

• The Halting Problem

• Checking if a number is even

• Solving any Sudoku puzzle

• Determining if a program runs forever

What happens when a Turing machine reaches a reject state

• It halts and rejects the input

• It erases the tape

• It continues running forever

• It halts and accepts the input