# 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.
```

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.

TRUE

FALSE

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

tape

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:

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

bus

output

bitrate

input

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

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

input bit

input tape

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.

FALSE

TRUE

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

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.

FALSE

TRUE

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

unary

denary

binary

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

TRUE

FALSE

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

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.

FALSE

TRUE