# Turing machine

The **Turing machine** is a **computing device** which consists of a **read** and **write head** , which is better known today as a **scanner** and a paper tape that passes through the machine. This ribbon was divided into **squares** , and each of them had a **symbol** at the same time . This tape was in charge of **storing** the machine, and was a kind of **input** and **output** vehicle , as well as working as a working memory to store the results of the intermediate steps of the calculation.

**Who invented it?**Alan Turing**In what year?**1936

## What is the Turing machine?

The machine is a **module** for **recognition** of more general language that any automaton **finite** and **stack** , because it has the ability to recognize languages **regular** and the **independent** context, and many other languages.

- Characteristics of the Turing machine
- History of the Turing machine
- How does it work
- Uses of the Turing machine
- Examples

## Characteristics of the Turing machine

The main characteristics of the Turing machine were the following:

- The input that the tape has before the calculation begins must consist of a finite number of symbols.
- The tape of the machine has an unlimited length.
- The read and write head can be programmable.
- The Turing machine is capable of six fundamental types of operations: read, write, move left, move right, change state, and stop.
- It has the ability to compute anything that any modern computer can compute.
- It is made up of an input and an output alphabet and a special symbol called white.

## History of the Turing machine

Alan Mathison Turing was the inventor of the Turing machine. He was known as an extremely talented man, who had great influences in the development of **computer science** and in the formalization of the concept of **algorithm** and **computation** through his Turing machine, which played a very important role in the creation of the modern computer. .

Turing first described it in his article published in 1936 on issues concerning **computable numbers** . In his article, Turing imagines that his creation is not a mechanical machine, but rather a person he decided to call a computer, who runs these deterministic mechanical rules carelessly.

## How does it work

The Turing machine works by means of a **finite control** , a **playhead** and a **tape** on which there can be different **characters** , and on which the input word is found. Towards the right side the tape has a length that is the place where the spaces are filled with the white character which is represented by the letter * “t”* . Towards its left side, the opposite happens because the tape is not infinite, which is why there is a box of the tape that is the extreme left. In addition, it has a head that moves to the left and right, so it has the ability to cycle through the same segment of the belt.

The machine is made up of an input **alphabet** and an output **alphabet** , by a **special symbol** known by the **name of target** which is normally represented by a b, Δ or 0, by a group of finite states and by a set of **transitions** between these states.

Its operation is based on the **transition** , which is responsible for receiving an **initial state** and a **string of characters** which belong to the input alphabet. From that moment on, the machine begins to read a **cell** on the tape, **erasing** the symbol, and **writing** the new symbol that belongs to the output alphabet and then advances to the left or right, one time at a time and repeating the process. as indicated in the transition function. At the end of the process it stops in a state of **acceptance** , thus representing the output.

## Uses of the Turing machine

The Turing machine has been, for example, used as a **generator of languages** , since this type of machine has several tapes including an output tape that is initially empty and then is filled with words of language. It is also used in **compilers I and II, ****state** machines, **automaton** machines and **code generators** .

In ancient times it was used in machines such as the ** “Bombe”** which was a device used by British cryptologists to be able to decipher signals encrypted by the German “enigma” machine during World War II . Also in the

**“colossus”**machines that deciphered the encrypted messages intercepted in the communications of the Nazis.

## Examples

Some examples of the Turing machine are:

- A string of X followed by a string of Y. Both of the same length.
- {X ^ n Y ^ n, n> 0}
- Ribbon Initial Status: 000111 #
- Transitions:
- 0 0 X r 1
- 1 0 0 r 1
- 1 YY r 1
- 2 XX r 0
- 3 YY r 3
- 0 YY r 3
- 1 1 AND l 2
- 2 0 0 l 2
- 2 YY l 2
- 3 # # r 4
- 4 * * r halt