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 ___________________.

  completely full (with 1s) input tape

  empty output headers

  an initially empty magnetic header

  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.

  FALSE

  TRUE

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

  FALSE

  TRUE

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

  track of the input type and input number

  track of the machine and tape state

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

  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 __________________________.

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

  longer the tape had to be.

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

  longer the magnetic header 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 any computation that involves addition or subtraction (but nothing more complex than that)

  perform millions of simultaneous computations using one magnetic head

  perform multiple computations using a single bit

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

  a language that is inferior to other languages

  a language that can solve the halting problem

  universal programming language

  a language that is infinite in memory

 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 ______!

  piece of RAM

  central processing unit

  program

  cache store

 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 onto a tape

  returned as a parameter to itself (thus recurring infinitely)

  recursively called

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