Preview

02 - Turing Machine

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

Bill Gates

Alexander Turing

Alan Turing

Charles Babbage

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 futuristic drawing

an object of a class

an abstract concept

a physical, tangible prototype

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

2-symbol Turing machine

4-symbol Turing machine

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

TRUE

FALSE

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.

FALSE

TRUE

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.

tape

magnetic sheet

optical sheet

CPU (central processing unit)

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.

FALSE

TRUE

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

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

a 'next' state

a current state

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

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

a set of formulas / output

a magnetic head / output

an input / output

an output / input

10. The tape is always _________________________.

a fixed size, allowing for 256 bytes of data

infinitely long

finite in nature

exactly a byte long (8 bits)

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

bus

input

output

bitrate

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

direction in which to go next

halt bit, which ensures that the halting problem is solved

next input, which feeds back in to another system

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

tape operation

bit operation

head operation

halting problem execution

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

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

the Turing machine halts

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

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.

input tape

input bit

output tape

magnetic head

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

TRUE

FALSE

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.

TRUE

FALSE

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

ouput tape

magnetic head

programmed instructions and symbols

transition table

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

FALSE

TRUE

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

binary

unary

hexadecimal

denary

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

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

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

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

FALSE

TRUE

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

FALSE

TRUE

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 
 ___________________________________________
________________________________________________.

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

less powerful than a finite state machine because it can count

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

TRUE

FALSE

Report an error