# 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

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