Turing machine
What is the Turing Machine?
The Turing Machine is a theoretical model of a computer invented by the
English mathematician Alan Turing in 1936. It is an abstract way of
representing any algorithm.
How is it composed?
1.- A paper strip divided into cells. Each cell can contain a symbol (0, 1, or
blank).
2.- A reader/writer head: which can read the symbol in the current cell,
write another symbol, and move left or right.
3.- A state table: defines what to do based on the read symbol and the
current state.
4.- A set of rules (program): tells the machine what action to take.
How it works?
With the head, read the current symbol on the tape, depending on the state
and the symbol, it performs three actions:
-Writes a symbol
-Moves (left or right)
-Changes state
Repeat this process until you reach a stop state (Halt).
What is it for?
Turing originally used it to test the limits of computation; it was key to
solving the decidability problem, which is whether one can know whether
an algorithm will halt or not, also called the halting problem, which he
showed to be generally independent.
In practice, it is a mathematical basis for the development of programming
languages, algorithms, artificial intelligence, computation theory, etc. Every
current computer is equivalent to a Turing Machine (Turing equivalence
principle).
This principle states that anything that can be computed by any mechanical
means can be computed by a Turing Machine. This means that any
computing system that can run algorithms is as powerful as a Turing
Machine if it has infinite memory and unlimited time.
How is it used today?
Although a Turing Machine is not physically used, it has many modern
applications:
- Universal Computation Model:
The Turing Machine was the first theoretical model of a universal
computer that could execute any algorithm given the right set of rules.
This concept inspired the idea of programmable computers: a single
piece of hardware that can perform multiple tasks, depending on the
software. Basically, all the devices we use today, such as computers,
cell phones, etc, are instructions processed by a system based on
this model.
- Basis of programming languages
Languages like Python, C, Java, etc., are based on control structures
(if statements, loops, etc.) that can simulate a Turing Machine. Every
time we use a program, we are using tools built on the concept that
any logical process can be modeled and executed as a Turing
Machine.
- Criptografía y seguridad informática
Turing applied his logical understanding to break the Enigma code
during World War II, which directly influenced the development of
modern cryptography, used in banking security, email, VPNs, and
blockchain. All of these tools are based on concepts that Turing and
his machine applied.
How has the concept of the Turing Machine developed in
Mexico?
At universities like UNAM or our UANL, they teach the principles of
this machine in subjects such as computation theory, algorithms,
automata, and formal languages. It is a fundamental part of the study
of computer science, research centers such as CINVESTAV, the
Institute for Research in Applied Mathematics and Systems (IIMAS)
at UNAM, and INAOE are investigating the use of Turing-based
mathematical models for:
-Programming languages.
-Natural language processing.
-Quantum computing and cellular automata.
Mexican researchers have worked on extending Turing models to
probabilistic or quantum machines, with applications in cryptography
and simulation.
3 important points:
- Alan Turing first defined a precise mathematical model of what it
means to follow a set of instructions step by step, what we now call
an algorithm. This concept underlies virtually all modern programming
and also the logic behind processors.
- Turing demonstrated that a single machine can simulate any other
Turing machine, thus giving rise to the concept of the universal
computer. Today, we use multipurpose computers to browse the
internet, edit documents, program, and more.
- Turing proved that not all problems can be solved with algorithms; it's
impossible to know whether a program will stop or run forever. This
influences how we program today, since not everything can be
automated.
Bibliografies:
- Copeland, B. J. (2004). The Essential Turing: Seminal Writings in
Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life.
Oxford University Press.
- Church, A. (1936). An Unsolvable Problem of Elementary Number
Theory. American Journal of Mathematics.
- Tanenbaum, A. S., & Bos, H. (2015). Modern Operating Systems (4th
ed.). Pearson.
Conclusion:
My conclusion about the research I did on the Turing Machine, created by
Alan Turing, is one of the most important inventions achieved in England,
because although as such this machine is not literally used today, it did
serve as the basis for practically the modern world we know today, the
devices we use today like our cell phones or the same computer that I am
using to write this are created under the concepts that Alan Turing
stipulated almost 100 years ago, I am IAS and knowing the bases of the
tools I use like computers or the same programming languages that are the
basis of my career, is impressive, ultimately this activity helped me better
understand my career and how it works.
