02 - Turing Machine

 1. The Turing machine is thought to be the brainchild of ______________ during the Second World War.

  Charles Babbage

  Bill Gates

  Alexander Turing

  Alan Turing

 2. The Turing machine is ___________________ of a machine capable of carrying out (simulating) any computable algorithm, even complex ones.
Some say that the computer was invented twice – 
once by Charles Babbage and once by Alan Turing.

While Babbage’s machine was supposed to be a 
practical thing, Turing’s was just a machine 
of the mind. It was invented not to compute 
tables of numbers but to solve problems in 
logic and to probe the limits of computation
 and human thought. ...

  a physical, tangible prototype

  an abstract concept

  a futuristic drawing

  an object of a class

 3. Fill in the blanks for the following excerpt.
Below is a very simple representation of a
Turing machine. 

It consists of an infinitely-long tape which 
acts like the memory in a typical 
computer, or any other form of data storage. 

The squares on the tape are usually blank at the 
start and can be written with symbols. 

In this 
case, the machine can only process the symbols 
0 and 1 and " " (blank), and is thus said to 
be a _______________________________.

  3-symbol Turing machine.

  4-symbol Turing machine

  2-symbol Turing machine

  0 based Turing machine

 4. The following excerpt describes what Alan Turing suggested:
A number, sequence or algorithm is computable if,
and only if, a Turing machine can be described which
is capable of computing it. 



 5. Turing machines can be used to describe the limitations of modern-day computers without having to deal with the complexities of devices too much.



 6. The following excerpt explains what a Turing machine is comprised of. Select which option correctly fills in the blanks.
A Turing machine is made up of:

1. A ____ divided into squares for reading
and writing symbols to; this _____ has a definite
left most end but the ____ is infinitely long

2. A head which can move left and right to read and write
from the _____.

3. A transition table which depicts the operations performed
by a Turing machine. 

  CPU (central processing unit)

  optical sheet

  magnetic sheet


 7. A Turing machine is NOT an example of a finite state machine as it essentially only has three different states and they cannot be altered.



 8. A Turing machine has a set of possible states including:

  The 'next' state is defined within the transition table (Turing called it the machine's state of mind!)

  All of the above are valid answers and reveal something about the different available states

  a current state

  a 'next' state

 9. A Turing machine will also have ______________ and an _________ alphabet made of the symbols to be written to and read from the tape.

  an output / input

  an input / output

  a magnetic head / output

  a set of formulas / output

 10. The tape is always _________________________.

  exactly a byte long (8 bits)

  finite in nature

  a fixed size, allowing for 256 bytes of data

  infinitely long

 11. In a Turing machine the _____ is the symbol read in from the tape by the head.





 12. The output in a Turing machine is the symbol to be written to the tape and the ________________________.

  stop bit, which ends the program altogether

  next input, which feeds back in to another system

  halt bit, which ensures that the halting problem is solved

  direction in which to go next

 13. A transitiion function is described in four parts: current state, symbol read, next state and ______________.

  tape operation

  halting problem execution

  bit operation

  head operation

 14. It is assumed that rules are written down and followed. If no rule is specified for the current state then ________________________________.

  the Turing machine halts

  The Turing machine programs itself to read in a 'zero', thus halting the program

  The Turing machine reads back the previous instruction and starts working backward

  the Turing machine does not halt, it simply does not know what to do!

 15. It is the ______________ that contains the input to the Turing machine.

  output tape

  magnetic head

  input bit

  input tape

 16. The head of the Turing machine starts from the right-most area of the input.



 17. It is possible for the head of the Turing machine to go off the tape, which is why it must start from the right-most side of the input and work backwards to safety.



 18. The head operates in accordance with the ___________________ where an input is read, the ______________depicts what the next operation should be.

  magnetic head

  programmed instructions and symbols

  transition table

  ouput tape

 19. It is not possible for a Turing machine with a limited number of symbols to represent other symbols.



 20. Turing machines are often represented using _________, which is the simplest form of counting.





 21. In a Turing machine, how does the machine repeat the sequence endlessly, and how does the machine stop running the program?

  It doesn't. This is where the 'halting problem' comes in

  The program tells it to using instructions fed in using high level code (e.g. C++)

  The program tells it to with assembly code instructions

  The program tells it to with the concept of a machine state

 22. The Church-Turing thesis claims that any computable problem can be computed by a Turing machine. This means that a computer more powerful than a Turing machine is not necessary to solve computable problems



 23. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; sadly most programming languages are NOT Turing complete



 24. Read the rather long excerpt that describes the difference between FSM and Turing machines and fill in the blanks with the most correct statement.
A Turing machine can also perform a special action – 
it can stop or halt – and it is this particular
behaviour that attracts a great deal of attention.

For example, a Turing machine is said to recognise 
a sequence of symbols written on the tape if it is 
started on the tape and halts in a special state 
called a final state. What is interesting about 
this idea is that there are sequences that a 
Turing machine can recognise that a finite state machine, 
i.e. a Turing machine without a tape, can’t.

For example, a finite state machine can recognise 
a sequence that has three As followed by three 
Bs e.g. AAABBB and so can a Turing machine. 
But only a Turning machine can recognise a sequence 
that has an arbitrary number of As followed by the 
same number of Bs.

That is a Turing machine is 

  less powerful than a finite state machine because it can count


  more powerful than a finite state machine because it contains more symbols on its tape at any given time

  less powerful than a finite state machine because it cannot halt or recognise finite problems

 25. Modern computers are tanginle and therefore slower than Turing machines but they can also compute things that a Turing machine could never attempt.