Turing machine and the stopping problem.
An introduction to the Turing machine and the downtime problem. one of the great milestones of computing, why decide to write about ?? because it is a way of showing the great contributions of Alan Turing and everyone who was part of the construction of modern computing.
Who was Alan Turing? a brief presentation, Alan Mathison Turing, was a mathematician, cryptanalyst, computer scientist, contributed to the definition of algorithms and also contributed to biology. He was known for cracking the codes of the enigma (Nazi machine that was used in the war by the Germans to attack his rivals), he and his team of mathematicians succeeded.One post would not be enough to talk about Alan Turing, maybe a book would.
What is a Turing machine?
The Turing machine or universal machine was a theoretical device, consisting of 4 components built and designed by the mathematician Alan Turing, next we will talk a little about these components.
1- The Turing machine has some components that make it work, the first one is the tape.This tape is potentially divided into calculations, each space in the cell can be formal or represent by some symbol of the finite alphabet. Represented ∑ = {S0.S1 … Sn}
2-The second component is the reading head, it basically serves to read a symbol, write a symbol in cells and has free movement both to the right and to the left, thus going one cell square at a time.
3-The third component is a state register, which at every moment of time the turing machine will be in a state that belongs to a set of possible states.
Q = {q1, q2 … qm}
4-The fourth item is instruction, but what is instruction? on the machine there is a set of instructions that are formed by operation that exist on the processor, microprocessor and some programmable peripherals, with mmonic representation (created only for better human interpretation, does not interact with the programming).
In the Turing machine a set of instructions is a quadruple of form (q1, Sj, a, ql), when the machine receives an instruction in the form (q1, Sj, a, ql) this will inform that it is in a qi state and reading the Sj state do the following:
If α (alpha) = Sk, delete Sj and write Sk in the square being read.
if α (alpha) = D, move the head to the right of reading one square to the right.
if α (alpha) = E, move the head to the left of reading one square to the left.
In this example we have this configuration of the turing machine
where we have the following instructions i1 (q1,0, D, q1), where q1 is the state and is reading 0, the header will read the state and then go to the right. with that the next configuration will be.
we will execute another instruction to know the behavior of the machine, the instruction is i2 (q1,1,0, q2), it basically asks that the head is going to be the value 1 in the state q1 change the value to 0 and jump to the q2 state.If you notice he changed the value and his status, thus ending the execution of the instruction
some curiosities of the turing machine is that it is five times formed by MT = (Q, ∑, I, q, F)
Q = {q1, q2 …. qm} is a set of states
∑ = {S0, S1 …. Si} is your alphabet
I = {i1, i2 … ij} is the set of instructions
q1 ∈ Q is your initial state
F which is a subset of final stages
Computability of functions
In this topic we will give an example of computable turing function, called F: N ^ K-> N, K> = 1, this machine will always start in the state of the smallest number that we can use as an example q1.It closes if there is no instruction
I tried to make it as clear as possible,if you liked the theme, I liked it and also share it with your friends, any questions I’m here.
#turing
#machine
#computer science
#science
imagens:google.com
