Home › Quizzes › Recursion Theory

Recursion Theory

Recursion Theory is a branch of mathematical logic that studies the foundations of computation and the limits of what can be computed. This quiz covers basic concepts in recursion theory, including computability, decidability, and Turing machines.

14 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

What is the Halting Problem?

  1. The problem of determining whether a given program will ever halt.
  2. The problem of determining whether a given program will halt in a finite number of steps.
  3. The problem of determining whether a given program will halt in an infinite number of steps.
  4. The problem of determining whether a given program will halt in a finite or infinite number of steps.
Question 2 Multiple Choice (Single Answer)

What is a Turing machine?

  1. A mathematical model of computation that consists of a tape, a head, and a set of instructions.
  2. A physical device that can be used to perform computations.
  3. A programming language that is used to write programs for Turing machines.
  4. A software program that can be used to simulate Turing machines.
Question 3 Multiple Choice (Single Answer)

What is the Church-Turing thesis?

  1. The thesis that every computable function can be computed by a Turing machine.
  2. The thesis that every Turing machine can be simulated by a computer.
  3. The thesis that every computer program can be written in a Turing-complete programming language.
  4. The thesis that every algorithm can be implemented on a physical computer.
Question 4 Multiple Choice (Single Answer)

What is a decidable problem?

  1. A problem that can be solved by an algorithm that always terminates.
  2. A problem that can be solved by an algorithm that sometimes terminates.
  3. A problem that can be solved by an algorithm that never terminates.
  4. A problem that cannot be solved by any algorithm.
Question 5 Multiple Choice (Single Answer)

What is an undecidable problem?

  1. A problem that can be solved by an algorithm that always terminates.
  2. A problem that can be solved by an algorithm that sometimes terminates.
  3. A problem that can be solved by an algorithm that never terminates.
  4. A problem that cannot be solved by any algorithm.
Question 6 Multiple Choice (Single Answer)

What is the Rice's theorem?

  1. A theorem that states that every non-trivial property of the set of all partial recursive functions is undecidable.
  2. A theorem that states that every non-trivial property of the set of all Turing machines is undecidable.
  3. A theorem that states that every non-trivial property of the set of all computer programs is undecidable.
  4. A theorem that states that every non-trivial property of the set of all algorithms is undecidable.
Question 7 Multiple Choice (Single Answer)

What is the Kleene's recursion theorem?

  1. A theorem that states that every partial recursive function can be defined by a Turing machine.
  2. A theorem that states that every Turing machine can be simulated by a computer.
  3. A theorem that states that every computer program can be written in a Turing-complete programming language.
  4. A theorem that states that every algorithm can be implemented on a physical computer.
Question 8 Multiple Choice (Single Answer)

What is the Post's correspondence problem?

  1. A problem that asks whether there is a way to match up two lists of symbols so that the corresponding symbols in each list form a valid word.
  2. A problem that asks whether there is a way to match up two lists of symbols so that the corresponding symbols in each list form a valid sentence.
  3. A problem that asks whether there is a way to match up two lists of symbols so that the corresponding symbols in each list form a valid program.
  4. A problem that asks whether there is a way to match up two lists of symbols so that the corresponding symbols in each list form a valid algorithm.
Question 9 Multiple Choice (Single Answer)

What is the Busy Beaver problem?

  1. A problem that asks what is the maximum number of steps that a Turing machine with a given number of states can take before it halts.
  2. A problem that asks what is the maximum number of steps that a Turing machine with a given number of symbols can take before it halts.
  3. A problem that asks what is the maximum number of steps that a Turing machine with a given number of instructions can take before it halts.
  4. A problem that asks what is the maximum number of steps that a Turing machine with a given number of tapes can take before it halts.
Question 10 Multiple Choice (Single Answer)

What is the halting problem?

  1. A problem that asks whether a given Turing machine will ever halt.
  2. A problem that asks whether a given Turing machine will halt in a finite number of steps.
  3. A problem that asks whether a given Turing machine will halt in an infinite number of steps.
  4. A problem that asks whether a given Turing machine will halt in a finite or infinite number of steps.
Question 11 Multiple Choice (Single Answer)

What is the diagonalization argument?

  1. An argument that shows that there is no algorithm that can solve the halting problem.
  2. An argument that shows that there is no algorithm that can solve the Post's correspondence problem.
  3. An argument that shows that there is no algorithm that can solve the Busy Beaver problem.
  4. An argument that shows that there is no algorithm that can solve any undecidable problem.
Question 12 Multiple Choice (Single Answer)

What is the incompleteness theorem?

  1. A theorem that states that every consistent axiomatic system is either incomplete or contradictory.
  2. A theorem that states that every axiomatic system is either complete or contradictory.
  3. A theorem that states that every consistent axiomatic system is either complete or undecidable.
  4. A theorem that states that every axiomatic system is either incomplete or undecidable.
Question 13 Multiple Choice (Single Answer)

What is the Gödel's incompleteness theorem?

  1. A theorem that states that every consistent axiomatic system is either incomplete or contradictory.
  2. A theorem that states that every axiomatic system is either complete or contradictory.
  3. A theorem that states that every consistent axiomatic system is either complete or undecidable.
  4. A theorem that states that every axiomatic system is either incomplete or undecidable.
Question 14 Multiple Choice (Single Answer)

What is the Turing's proof of the halting problem?

  1. A proof that shows that there is no algorithm that can solve the halting problem.
  2. A proof that shows that there is no algorithm that can solve the Post's correspondence problem.
  3. A proof that shows that there is no algorithm that can solve the Busy Beaver problem.
  4. A proof that shows that there is no algorithm that can solve any undecidable problem.
← Back to Quizzes