Preview

04 - Universal Turing Machine

 1. A Universal Turing Machine is a machine that takes as input a number that identifies a Turing Machine and simulates the specified Turing Machine running on ___________________.

  an initially empty magnetic header

  empty output headers

  completely full (with 1s) input tape

  initially empty input tape.

 2. Fill in the blanks for this excerpt.
It became necessary to introduce the notion of a 
universal turing machine (UTM), which along with the 
input on the tape, takes in the description of a machine M. 

The UTM can go on then to simulate M on the rest of 
the contents of the input tape. 

A universal turing machine can thus ____________________.

  never simulate any other machine other than itself

  solve any problem, including the halting problem as it is infinite in nature

  simulate up to a billion other machines simulatenously (e.g concurrently)

  simulate any other machine

 3. The problem with Turing Machines is that a different one must be constructed for every new computation to be performed, for every input output relation.

  TRUE

  FALSE

 4. The Universal Turing Machine can simulate any Turing Machine.

  TRUE

  FALSE

 5. The universal machine keeps _____________________________of the simulated machine and simulates each step.

  track of the input type and the magnetic header's pointer

  track of the machine and tape state

  track of the input type and input number

  track of only the current tape state and the final state of the magnetic head's input bit

 6. The more you wanted your 'machine' to do the __________________________.

  shorter the input had to be (to allow for greater output)

  longer the tape had to be.

  longer the magnetic header would have to be

  longer the output that feeds back into the input would have to be

 7. Fill in the blanks for this excerpt.
Since a Universal Turing Machine can simulate every Turing Machine
and a Turing Machine can _________________________________________
this means a Universal Turing Machine can perform all computations.

  perform any computation according to our intuitive notion of computation

  perform millions of simultaneous computations using one magnetic head

  perform multiple computations using a single bit

  perform any computation that involves addition or subtraction (but nothing more complex than that)

 8. If it possible to simulate a Universal Turing Machinein a programming language, that language is a __________________________.

  universal programming language

  a language that is infinite in memory

  a language that is inferior to other languages

  a language that can solve the halting problem

 9. One could say that a universal Turing machine is just a programmable computer and the description on the tape of another Turing machine is a ______!

  cache store

  program

  central processing unit

  piece of RAM

 10. The key idea in creating a Universal Turing machine is to notice that the information that defines a specific Turing machine can be _____________.

  coded as a series of 1s and 0s that are ouput on a magnetic head

  returned as a parameter to itself (thus recurring infinitely)

  coded onto a tape

  recursively called