Preview

01 - Halting Problem

 1. The halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or _______________________.

  recursively call itself in order to solve the problem

  or stop and start to go back on itself

  continue to run forever.

  delete itself and all associated elements

 2. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

  TRUE

  FALSE

 3. A key part of the proof was a mathematical definition of a computer and program, which became known as a _________________.

  caching system

  halting peripheral

  turing machine

  halting machine

 4. The halting problem is undecidable over Turing machines. It is one of the first examples of a ____________.

  CPU

  regular expression

  finite state machine

  decision problem

 5. Read the excerpt below and decide whether the following statement is true or false: No f can exist that handles this case. 
Informally, for any program f that might determine if programs halt, a "pathological" program g called with an input can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do

  TRUE

  FALSE

 6. The problem is to determine, given a program and an input to the program, whether the program will ______________________________.

  recursively call itself and then halt on n - 1 iterations

  run forever given no input

  eventually stop when given double the same amount of input

  eventually halt when run with that input.

 7. Analyse the program (pseudocode) below. This program will ________________________________. 
while (true) continue

  halt on the first iteration

  halt eventually, but only if the input is 'true'. It would not work for 'false'

  halt eventually

  not halt and go on forever in an infinite loop

 8. The following program also does not halt. 
print "Hello, world!"

  TRUE

  FALSE

 9. Turing proved no algorithm exists that always correctly decides whether, for a given arbitrary program and input, the program halts when run with that input.

  FALSE

  TRUE

 10. The essence of Turing's proof is that any such algorithm can be made to ______________________________.

  recursively call itself and therefore can not be solved unless the base case is met

  duplicate itself, meaning the input doubles and would cause an infinite loop

  iterate n - 1 times and therefore cannot be correct

  contradict itself and therefore cannot be correct.

 11. Read the excerpt and problem below. Decide which answer is most accurate in response to the question. 
Your town has put on a massive competition to
find a solution to the travellingsalesman problem.  
The individuals that are competing have to send in
their programs which solve the problem to you. 
Your job is to build a program to check that every 
program that is sent in eventually finds the correct
solution, given a particular input.  

Is this possible? Explain your answer either way.

  Yes, it is possible, although if the input wasn't given correctly it could lead to the halting problem

  Yes, it is possible. This is an example of a solvable problem.

  No, it is not possible. This is because checking solutions is possible, but checking that the input entered is valid would pose an impossible task

  No, it is not as this is an example of the halting problem

 12. The halting problem is theoretically decidable for linear bounded automata (LBAs) or deterministic machines with _______________.

  infinite memory

  finite memory

  Big O complexity of O(n)

  infinite space

 13. A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state

  FALSE

  TRUE

 14. The halting problem is historically important because it was one of the first problems to be proved ____________.

  haltable

  random

  infinite

  undecidable

 15. The ____________ as shown below, represents the halting problem 
K := { (i, x) | program i halts when run on input x}

  halting set

  malting set

  turing machine set

  big O halt set

 16. The proof that the halting problem is not solvable is a proof by ________________.

  contradiction

  infinite recursion

  inference

  deduction

 17. Read the excerpt below and fill in the blanks. 
To illustrate the concept of the proof, suppose that there 
exists a total computable function halts(f) that returns 
true if the subroutine f halts (when run with no inputs) 
and returns false otherwise. 

Now consider the following subroutine:

def g():
    if halts(g):
        loop_forever()

halts(g) must either return true or false, because halts was 
assumed to be total. If ______________________, then g will 
call loop_forever and never halt, which is a contradiction

  halts(g) returns true

  def(g) returns true

  def (g) returns false

  halts(g) returns false

 18. The concepts raised by Gödel's incompleteness theorems are very similar to those raised by the halting problem, and the proofs are quite similar

  FALSE

  TRUE

 19. Fill in the blanks in the following excerpt. 
It's important to note that Halting problem depends 
on what programs we're considering. 

The halting problem on _____________is undecidable. 

Conversely, the halting problem on finite state automata
 is easily decidable; all finite state automata halt. 

Thus it's important to specify the model

  turing machines

  an infinite amount of space

  infinite state machines

  infinite state automata

 20. The halting problem on usual computers is ___________. To see this, note that there are a finite number of bits in the memory, and thus a finite number of possible configurations the computer can be in.

  infinite

  undecidable

  intractable

  decidable


Report an error