From Finite States to Turing Machines

Prof. Dr. Mirco Schoenfeld

Recap

Last session was about finite state automata (FSA).

Recap

As a special form of FSA, we introduced
deterministic finite automata (DFA) and
non-deterministic finite automata (NFA).

Recap


https://commons.wikimedia.org/wiki/File:Tornelli.jpg


https://commons.wikimedia.org/wiki/File:Turnstile_state_machine_colored.svg

Today’s computers


https://commons.wikimedia.org/wiki/File:ASRock_K7VT4A_Pro_Mainboard.jpg

Today’s computers

Today’s computers are based on the von Neumann model often implemented using a x86-64 architecture.

https://commons.wikimedia.org/wiki/File:AMD_Opteron_146_Venus,_2005.jpg

Today’s computers

At it’s core, they deal with 0 and 1.

https://commons.wikimedia.org/wiki/File:Standby_switch.jpg

What are today’s computers?

Imagine a Modern CPU. Every bit in a machine can only be in two states (0 or 1).

Therefore, there are a finite number of possible states.

In addition, when considering the parts of a computer a CPU interacts with, there are a finite number of possible inputs from the computer’s mouse, keyboard, hard disk, different slot cards, etc.

As a result, one can conclude that a CPU can be modeled as a finite-state machine.

Aziz, Cackler, and Yung (2004)

What are today’s computers?

Is a modern computer a finite-state machine?

What are today’s computers?

Now, consider a computer.

Although every bit in a machine can only be in two different states (0 or 1), there are an infinite number of interactions within the computer as a whole.

It becomes exceeding difficult to model the workings of a computer within the constraints of a finite-state machine.

However, higher-level, infinite and more powerful automata would be capable of carrying out this task.

Aziz, Cackler, and Yung (2004)

Turing machine

The first “infinite” model of computation
was conceived by Alan Turing.

It is known as the Turing machine.

Turing machine

https://en.wikipedia.org/wiki/File:Turing_Machine_Model_Davey_2012.jpg

Turing machine

A Turing machine can be thought of
as an FSA equipped with infinite storage.

https://en.wikipedia.org/wiki/File:Turing_Machine_Model_Davey_2012.jpg

The storage is an infinite number of one-dimensional array of cells.

Turing machine

A Turing machine consists of

  • a tape providing unlimited one-dimensional memory capacity
  • a head used to read and write symbols and move the tape left and right one cell at a time
  • a state register storing the state of the machine
  • a finite table of instructions

Formal definitions

A Turing machine \(M\) is a 7-tuple, \(( Q, \Gamma, b, \Sigma, \delta , q_0 , F)\), with

  • a finite, non-empty set of states \(Q\)
  • a finite, non-empty set of tape alphabet symbols \(\Gamma\)
  • a blank symbol \(b \in \Gamma\)
  • a finite set of input symbols called the alphabet \(\Sigma \in \Gamma \setminus b\)
  • a transition function \(\delta: (Q \setminus F) \times \Gamma \not\to Q \times \Gamma \times \{L,R\}\)
  • an initial or start state \(q_0 \in Q\)
  • a set of accept states \(F \subseteq Q\)

Formal definitions

The transition function \(\delta:\)

\(\delta: (Q \setminus F) \times \Gamma \not\to Q \times \Gamma \times \{L,R\}\)

\(\delta\) specifies the next state transited from the current state, which symbol to overwrite the current symbol pointed by the head, and the next head movement and

  • L is left shift
  • R is right shift

From Turing machines to modern PCs

In Turing machines, every part of the machine and its actions are finite, discrete, and distinguishable.

The difference to FSA lies in the capability of a Turing machine to change symbols on its tape thereby simulating computer execution and storage.

https://en.wikipedia.org/wiki/Turing_machine

From Turing machines to modern PCs

For this reason, it can be said that the Turing Machine has the power to model all computations that can be calculated today through modern computers.

Aziz, Cackler, and Yung (2004)

From Turing machines to modern PCs

A Turing machine is an idealised model of a central processing unit (CPU) that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data.

https://en.wikipedia.org/wiki/Turing_machine

Turing limitations

There are two major limitations in the analogy between Turing machines and modern PCs:

  • modern PCs are Random-Access Stored-Program machines separating programs from instruction memory. That allows for some computational optimizations. (more on that later)
  • modern PCs are interacted with. So the model of a computer producing outputs based on inputs rarely matches how interactions actually happens.

Thanks

https://xkcd.com/329/

Acknowledgement

Acknowledgement:

This script is inspired by Aziz, Cackler, and Yung (2004).

References

Aziz, Amal Dar, Joe Cackler, and Raylene Yung. 2004. “Automata Theory.” Online. https://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/index.html.
Back to Lecture Website