# Turning Machine

A **Turning Machine** is a very powerful computing machine. This was invented by **Alan Turning** in 1936. The basic fundamental of this machine is to build an automaton with finitely many states but unbounded memory.

## Parts of Turning Machine

A **Turning machine** basically has three main parts -

**Finite State Control** - It gives a command to the machine.

**Infinite Tape** - Memory device of machine.

**Tape Head** - It reads and writes a single cell.

## Turning Machine Memory Device

A **Turning machine** is a finite automaton that has an **infinite memory tape**. The tape is divided into many infinite blank cells. Each cell contains a symbol from some finite alphabet. The machine operates on this tape. It has a **tape head** that reads and writes a single memory cell at a time. It also moves the tape cell left or right at a time. In the turning machine, this tape starts with the input written on it.

## Formal Definition of Turning Machine

A **Turning machine** is a 7 tuple -

##### (Q,Σ,Γ,δ,q_{0},q_{acc},q_{rej})

**Q** - It is the finite set of states,

**Σ** - finite set of input alphabet,

**Γ** - tape alphabet,

**δ** - transition function, **Q x Γ -> Q x Γ x {L,R}**,

**q _{0}** - start state,

**q**- accept state,

_{acc}**q**- reject state.

_{rej}So, a turning machine has two alphabets, the **input alphabet** and the **tape alphabet**. The **tape alphabet** contains all symbols that can be written on the tape. But, it can contain at least one **blank symbol**. The blank symbol is denoted with ** □**. When a Turning Machine receives an input, it can do one of the three things with the input -

- Accept the input (q
_{acc}) - Reject the input (q
_{rej}) - Continue the computing (loop)

## Types of Turning Machine

There are different types of Turning Machine-

- Multi-tape Turning machine
- Multi-head Turning machine
- Non-deterministic Turning machine
- Double tape infinite tape Turning machine

## Universal Turning Machine

A Turning machine that can simulate any other Turning machine is called the **Universal Turning Machine**. It means one turning machine acts as an input to the other turning machine.

There is a Universal Turning Machine **U**, it accepts encoding **U(M,w)** of a turning machine **M** and string **w**. It simulates the execution of **M** on **w**.

The language **L _{TM}** is the language of

**M**.

**L**_{TM} = { ⟨M, w⟩ }

+\
Non-Deterministic PDA

Multi-tape Turning Machine