1. The Turing machine is thought to be the brainchild of ______________ during the Second World War.
2. The Turing machine is ___________________ of a machine capable of carrying out (simulating) any computable algorithm, even complex ones.
3. Fill in the blanks for the following excerpt.
4. The following excerpt describes what Alan Turing suggested:
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.
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:
9. A Turing machine will also have ______________ and an _________ alphabet made of the symbols to be written to and read from the tape.
10. The tape is always _________________________.
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 ________________________.
13. A transitiion function is described in four parts: current state, symbol read, next state and ______________.
14. It is assumed that rules are written down and followed. If no rule is specified for the current state then ________________________________.
15. It is the ______________ that contains the input to the Turing machine.
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.
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?
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.
25. Modern computers are tanginle and therefore slower than Turing machines but they can also compute things that a Turing machine could never attempt.