Table of Contents
III. Theory and Mathematical Background – 40%
B. Automata and language theory
1. Models of computation (finite automata, Turing machines)
a. Definition: Before we made computers from sand, people designed models on paper that could calculate. These hypothetical machines are the basis for all modern computers.
b. A deterministic finite automaton (DFA) is a model of a machine that has a finite number of states and inputs. Some DFA also have output. Question #11 in the practice test shows an output-producing DFA. The arrows between the states show the input and output of the transition between the states. The number on the left of the slash is input, the other number is output. (Memory tip: English is read left-to-right; the input happens before the output, so it is on the left.) If a set of input ends on an accept state, then we say that the machine recognizes the input. The start state is the state that the machine begins to process the input from. The set of all inputs that the machine recognizes is the language of the machine.
c. A nondeterministic finite automata (NDFA) (or NFA) is a DFA that can transition to and from multiple states at one time. We can convert any NDFA into a DFA.
d. A Pushdown automaton (PDA) has states and transitions like a DFA, but it also has a feature called a stack. The stack can hold information in a LIFO order. The stack allows a PDA to recognize a wider range of languages than a DFA.
e. A Turing machine is the most powerful model of computation that we have discovered that actually represents a real world device. It has transitions states like a PDA or a DFA, but it uses a tape as both input and as working memory. The tape is of infinite length and can be accessed by the machine in any order. We have discovered that these two features are the key to this model’s power. Modern computers are based on the Turing machine.
f. A nondeterministic Turing machine is a Turing machine that can branch into multiple states (like a NDFA). We do not know of any way to convert all nondeterministic Turing machines into Turing machines. As such, there is no real world example of a nondeterministic Turing machine.
g. The Church-Turing thesis says that there are certain problems that can be solved using “effective functions.” For a function to be effective, it must be possible to solve the function in a finite number of steps with only paper and pencil. We sometimes say that this is a mechanical function. Think about calculating the first 100,000 digits of PI. It is possible for humans with paper, pencil, and the formula to accomplish this. (It would take a long time, but it is possible.) If there were not functions like this, then computers would not be possible. Unfortunately, this is more philosophy than math and cannot be proven using mathematical concepts.
