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

  empty output headers

  initially empty input tape.

  an initially empty magnetic header

  completely full (with 1s) 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 ____________________.

  simulate any other machine

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

  never simulate any other machine other than itself

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

 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.

  FALSE

  TRUE

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

  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

  track of the input type and input number

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

  longer the tape had to be.

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

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

  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 millions of simultaneous computations using one magnetic head

  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 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 can solve the halting problem

  a language that is inferior to other languages

  a language that is infinite in memory

  universal programming language

 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

  program

  cache store

  central processing unit

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

  recursively called

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

  coded onto a tape

  returned as a parameter to itself (thus recurring infinitely)