3.2 VARIANTS OF TURING MACHINES (Afbrigði af Turing-vélum )

Question 1

Alternative definitions of Turing machines abound, including versions with multiple tapes or with nondeterminism. They are called ?

Answer 1

variants of the Turing machine model.

Question 2

A multitape Turing machine

Answer 2

A multitape Turing machine is like an ordinary Turing machine with several tapes. Each tape has its own head for reading and writing. Initially the input appears on tape 1, and the others start out blank. The transition function is changed to allow for reading, writing, and moving the heads on some or all of the tapes simultaneously.

Question 3

Are Turing machines more powerful than ordinary Turing machines?

Answer 3

No, they are equivalent in power.

Question 4

Every multitape Turing machine has an equivalent single-tape Turing machine.

Question 5

A nondeterministic Turing machine

Answer 5

At any point in a computation, the machine may proceed according to several possibilities.

Question 6

Every nondeterministic Turing machine has an equivalent deterministic Turing
machine.

Question 7

A language is Turing-recognizable if and only if some nondeterministic Turing machine recognizes it.

Question 8

We call a nondeterministic Turing machine a decider if ?

Answer 8

all branches halt on all inputs.

Question 9

an enumerator

Answer 9

Loosely defined, an enumera- tor is a Turing machine with an attached printer. The Turing machine can use that printer as an output device to print strings. Every time the Turing machine wants to add a string to the list, it sends the string to the printer.

Question 10

A language is Turing-recognizable if and only if some enumerator enumerates it.