- Deterministic Finite Automata
- Turing Machines and Universal Computation
- Decidability and the Halting Problem

Having a simple construction and easy to grasp definition, deterministic finite automata (DFA) are one of the simplest models of computation. When interconnected, discrete finite state automata have the ability to exhibit interesting dynamical behavior. These characteristics make DFA an ideal unit with which to build a system suitable for studying the connection between dynamical behavior and computational ability.

A deterministic finite automaton can be viewed as a simple machine consisting of three components: sensor, memory and instruction book.

The automaton sensor is the device by which data is input. For example the automaton
could have a thermometer reading temperature, a magnet reading a hard drive,
an antenna reading radio waves, or anything else that would import information.
We restrict the accuracy of the imported information by allowing the automaton
to recognize only a finite number of different input values or *symbols*.
For example, if a discrete finite state automaton was taking values from a thermometer
as input, we could restrict its recognition of temperatures between
and
in steps of
.

The automaton memory has the limited capacity to store only a single symbol.
The type of symbols that can be stored need not be the same as those being returned
by the automaton sensor. We refer to this stored symbol as the automaton's *state*.
We allow the automaton to exist in only a finite variety of different states.

The automaton instruction book is the set of rules by which the automaton changes its state. The rulebook dictates what state the automaton should be in based upon the automaton's current state and input symbol. The automaton consults this rulebook everytime an input symbol is read.

An automaton begins operation in a predefined state known as its initial state (or start state). The automaton then enters into this loop:

read input symbol consult instruction book transition to new state |

Because operation continues until the input source has been exhausted, it is often practical to place a finite limit on the amount of information that may be made available to an automaton for input.

That an automaton may operate on a finite set of input data and end in a discernible
final state motivates us to view the automaton as a mapping between the set
of input symbols and its final state. This view is further enriched by naming
some of the automaton's possible states *accepting* states. This allows
us to say that an automaton either accepts or rejects its input data set based
upon its final state.

We use J. C. Martin's [9] notation as our basis for

is a finite set of states. |

is a finite set of input symbols. |

is the initial state. |

is the set of accepting states. |

is the state transition function. |

The transition function acts as an automaton behavioral rulebook. Based upon the automaton's current state and input symbol, the transition function dictates what state the automaton should next be in. Thus, a useful question to ask when studying the behavior of any finite automaton (FA) is: How many unique transition functions can I define for a particular FA?

Above, we defined the transition function for an FA as . is the set of states the FA can be in. is the set of symbols the FA can accept as input. By dissecting this definition, we shall count how many different ways there are to define the function .

The domain of the function says that our input is in . Since and are finite, the number of possible inputs is . To count the number of unique ways can be defined, we need to count the number of different ways we can specify what output any particular input could have. The range of tells us that any input can have possible outputs. In other words, for some and :

Thus, we have a choice of different transitions that can occur for each of the inputs, or, possible transition functions. We record this result as

This counting problem can be reformulated as: For a given alphabet, how many words of a particular length are there? In the previous case, our word length was (the number of possible inputs) and our alphabet was the set of output symbols (having ``letters''). Thus, we would be choosing different letters for each position in our word times. Therefore, there are different words that can be written down.

To get a better understanding of the size of , we shall calculate the number of possible transition functions for a couple of example automata. The important point to remember is that the function , having exponential growth, creates a strong bounding condition on the complexity of the automata one can consider for practical, computational exploration.

For this automaton, and . Thus, the number of unique transition functions we could define for this FA would be .

What follows is a brief description of Turing machines and universality. The goal of this section is to describe what is meant by the phrase ``universal computation''. We shall avoid an in-depth discussion of Turing machine construction and operation as well as most of the interesting theories that surround and grow out of them. For a proper treatment of this most fascinating material, J. C. Martin's book [9] is recommended.

Like a finite automaton, a *Turing machine* is a simple computing device
consisting of a finite set of input states, finite set of input symbols, an
initial state, and a transition function. We choose at least one of the input
states to be special, calling it the *halt state,* and define our transition
function such that there are no more possible transitions once the machine reaches
the halt state. Unlike a finite automaton, a Turing machine's input data is
said to be given on a finite, but unbounded, strip of magnetic tape. A tape
head connected to the Turing machine is placed at the beginning of this input
data and has the ability to move forwards and backwards along the tape. In addition,
Turing machines have a finite set of tape symbols which they can both read and
write to the tape via the tape head.

Dr. Alan Turing wrote a thesis which argued that Turing machines are as powerful as the most powerful computing device possible. In other words, no matter how fast or complex our computing devices become, they will have no more capabilities (power) than a Turing machine.

A special form of Turing machine is the *universal Turing machine*. Universal
Turing machines have the ability to simulate any other Turing machine when given
a description and set of input data for that other Turing machine.

One view of the relationship between Turing machines and universal Turing machines is that a Turing machine is like a single computer program and a universal Turing machine is like an operating system. In this view, a Turing machine is a defined algorithm acting on input data. A word processor, taking text input and outputting a formatted document, is a good example of a Turing machine. On the other hand, a universal Turing machine has the ability to ``run'' any other Turing machine along with its associated input. This is just as our home computers have the ability to simulate any other computing device that has been encoded as software. A prime example is running software that simulates a pocket calculator or word processor.

When we say a computational device is *universal,* we typically mean that
the device has the capability to simulate any other computational device. A
common method for proving a device is universal is to show that it is capable
of simulating another device already known to be universal. For example, if
you were to show a system capable of simulating the components necessary and
sufficient to build a computer (gates, timers, etc.) then you would have shown
that system to be a universal computer.

Decidability and the Halting Problem

One very important result obtained by Dr. Turing was proof that there exist completely deterministic processes for which it is impossible to decide whether or not they will complete. In terms of Turing machines, his proof implies that given a Turing machine and some input data, it is impossible to decide whether or not that Turing machine will halt. This result should not seem so surprising given the existence of such problems like the Three-Body Problem wherein you know all the details of the mathematical algorithms used to compute the system's evolution, yet are unable to give a general solution for how the system will evolve. One could say that there is a certain sensitivity to the system's initial configuration. This notion will be further explored in section .

In the course of the following Halting Problem proof and discussion there may be unfamiliar notation. We take the time now to describe what is meant:

We construct a universal Turing machine, , which takes as input a string , and subsequently runs with input . We define such that if outputs `` '' then should transition to an infinite loop and if outputs `` '' then transitions to the halt state.

What will happen if we ran with input string ? This will run on . There are two well defined possibilities for what will do: either it will enter into an infinite loop or it will halt. We look at these outcomes:

loops on ) output `` '' halts on halts on ) output loops on . A paradoxical cycle.

Since both cases end in a contradiction, our initial assumption that is decidable must be incorrect. The Halting Problem is undecidable.

We construct a Turing machine, , which determines whether or not an input even number greater than 2 can be written as the sum of two primes. This is a simple computable process which can be described as follows:

- Copy the input number to a new place, call it .
- Create a second number .
- In a loop do the following:
- Subtract one from and add it to .
- If is less than half of the input number then we have exhausted all possible prime number candidates and the input number fails the Goldbach conjecture: output `` '' and halt.
- If and are both prime then the input number is the sum and it passes the Goldbach conjecture: output `` '' and halt.

We construct another Turing machine, , which runs . first gives the number 4. then enters the following loop:

- If should output `` '' then halt.
- Run with the next higher even number.

Run on . If produces `` '' then we know the Goldbach conjecture failed for some even number; the Goldbach conjecture must be false. If produces `` '' then we know that runs forever; the Goldbach conjecture must be true.

Since all machines used must exist, we must be able to create the above composite machine to solve the Goldbach conjecture.

- ...
language
^{1} - The language recognized by finite state automata is known as a regular language. Regular languages appear as the simplest language in Chomsky's language hierarchy. For more information see J. C. Martin's book [9].