Turing Machine

computation requires-cleanup

Definition

Turing Machine

A Turing machine consists of seven components:

where:

• is a finite set of states.
• is the input alphabet.
• is the tape alphabet.
• is a transition function.
• (left, right, stay) is the direction in which the head should move.
• is the initial state.
• is the blank symbol.
• are the accepting) states.

A Turing machine halts on the first occasion of a final state . In that case, is undefined.

Turing Machine (Boundary Symbols)

A Turing machine consists of eight components:

where:

• is a finite set of states.
• is the alphabet of the input tape.
• is the alphabet of the working tape.
• is a transition function
• (left, right, stay) is the direction in which the head should move.
• is the initial state.
• is the left boundary symbol on the working tape
• is the left boundary symbol on the input word
• is the right boundary symbol on the input word
• is the blank symbol.
• are the accepting) states.

A Turing machine halts on the first occasion of a final state .

Tape

Definition

Tape (Turing Machine)

A tape is an infinite sequence of elements where each element can be blank or a state . Almost all cells are non-blank.

Link to original

Configuration

Definition

Configuration (Turing Machine)

A configuration is a complete snapshot of a Turing machine at a single moment.

Move to left, i.e.: :

Move to right, i.e.: :

Move stays (no movement), i.e.: :

Link to original

Language

Accepted Language

Accepted Language (Turing Machine)

The accepted language of a Turing machine are all words for which terminates:

Recursive Enumerable Language

Definition

Recursively Enumerable Language

A language is recursively enumerable if there exists a Turing machine such that:

1. for every , halts and accepts ,
2. for every , either rejects or runs forever.

i.e., there exists a Turing machine that accepts .

Equivalently, there’s a program that enumerates all strings of (possibly with repetition) , every member of appears after finite time.

Link to original

Recursive Language

Definition

Recursive Language

A language is recursive (or decidable) if there exists a total Turing machine such that, for every input , halts and:

1. if , accepts ;
2. if , rejects .

Equivalently:

• The characteristic function is computable.
• Both and its complement are recursively enumerable.
• There exists a program that, given any string , decides membership in finite time.

Link to original

Deterministic

Definition

Deterministic Turing Machine

A deterministic Turing machine is a Turing machine whose transition relation assigns at most one move to every state–symbol pair:

Such a relation is a partial function, denoted

Every configuration of has at most one successor, so the computation on an input is a single path. The machine accepts an input if that path reaches an accepting state .

The definition is the special case of the nondeterministic Turing machine obtained by requiring at most one move per state–symbol pair.

Link to original

Computation

Computation of an Arithmetic Function

Denote as the binary representation of an . The initial configuration of a Turing machine with alphabet . The input works on input:

where must not contain leading zeros.

The initial configuration of is where (blank symbol) separates each block.

Example Initial Configuration

Let and with binaries . Here, the initial configuration is:

The end configuration of a (function-computing) Turing machine is given by:

with (final state), (tape words), and emits .

Parsing " "

• The head is position at the leftmost bit because (final state) precedes .
• Right after the number there is a blank (a delimiter).
• The machine is in an accepting (final) state , i.e., it has halted.
• Therefore, the output is .

is arbitrary content elsewhere. It doesn’t matter what’s left in or .

Computation of

A Turing machine with input alphabet computes an arithmetic function if works on as input, and outputs . Denote .

Example with input

Let . Let be:

State/Input

For instance, let be the input. Thus, the tape contains :

The Turing machine halts at . The output is , see final configuration.

The computed function is , whereby .

Note: The same Turing machine , when the pair is encoded on the tape as , computes , whereby:

Here is the binary length:

Examples

A machine for

The following two-tape Turing machine accepts exactly the language :

where:

The machine marks matching blocks of , , and symbols and accepts when the input is exhausted.