Turing Machines

What is a Turing machine?

• A theoretical machine that can simulate any computer algorithm

• A physical object used for computation

• A machine that can only perform simple computations

• A machine that can only read and write symbols

Who introduced the Turing Machine

• Dijkstra

• Ada Lovelace

• Alan Turing

• John von Neumann

In the Church-Turing thesis, what is claimed about Turing machines?

• a)They can be physically built with perfect accuracy

• b)They can solve all mathematical problems

• c)They can model any effectively calculable function

• d)They require less memory than other computational models

The set of symbols used for a Turing Machine is called an

• Alphabet

• Symbols Collection

• Dictionary

• Functional Set

Which of the following does a turing machine consist of?

• a)A tape, a state register, and an algorithm

• b) A tape, a controller, and a read/write head

• c) A memory unit, a processor, and an input/output device

• d) A memory unit, a processor, and an input/output device

A turing machine operates over:

• a) finite memory tape

• b) infinite memory tape

• c) depends on the algorithm

• d) none of the mentioned

Which of the functions are performed by the turing machine after reading a symbol?

• a) writes the symbol

• b) moves the tape one cell left/right

• c) proceeds with next instruction or halts

• d) none of the mentioned

Turing machine can be represented using the following tools:

• a) Transition graph

• b) Transition table

• c) Queue and Input tape

• d) All of the mentioned

A turing machine that is able to simulate other turing machines:

• a) Nested Turing machines

• b) Universal Turing machine

• c) Counter machine

• d) None of the mentioned

If d is not defined on the current state and the current tape symbol, then the machine

• a) does not halts

• b) halts

• c) goes into loop forever

• d) none of the mentioned