1
$\begingroup$
  1. An automaton, as I have seen so far, is used to tell if a string belongs to the language that the automaton recognizes. This is determined by the final state of the automaton running on the string as an input. I wonder what role the output of the automaton plays here for this decision problem?

  2. I saw that an automaton (e.g. a Turing machine) can model a computer. A computer takes a program (which can solve any problem, such as evaluating a function, optimizing a function, searching for something, ...)as an input, and outputs what the program asks the computer to do. So when an automaton models a computer, what do the inputs, outputs, states and transition/output rules of the automaton represent?

  3. Some also said that an automaton models an algorithm. My understanding is that an algorithm is informally a sequence of instructions ( I can't find the formal definition for an algorithm, and wonder what it is), while an automaton has a set of rules for transition and output. So I wonder how to understand that an automaton models an algorithm?

1 seems to be just a special case of 2, since the decision problem is just a kind of problem that a computer can solve.

Regarding 2 and 3, if an automaton models a computer and a program is its input, since a program represents an algorithm, isn't an algorithm an input to an automaton instead? Thanks.

$\endgroup$
5
$\begingroup$

The impetus behind all of this comes from trying to define a mathematically rigorous model of what "computation" means. Alan Turing did this in 1936 by defining a definition of a simple abstract machine that seemed to be sufficient to describe everything that we'd call computation, a device we now call a Turing Machine.

Over the years, people have investigated other models of computation that were restricted in what they could do and discovered that these simpler models were also interesting in themselves. This eventually lead to what we might call the standard introduction to computability theory, as follows.

Finite Automata. Starting with this model, we have a finite collection of states and define transitions from one state to another depending on the current character being read in an input string. Some of these states are designated as final states and the convention is that if the automaton is in a final state after reading all the characters of the input, we say that the automaton accepts the input string.

(Important Digression): Languages and problems. Starting with a machine that can determine whether a string is or is not in a particular language, we can transform this task into a task of solving a problem. For instance, we might want to solve the problem "given nonnegative integers $n$ and $m$ are they both even or both odd?" It's not hard to see that this is equivalent to "can we make a finite automaton that accepts all and only strings in the language $L_1=\{a^nb^m \mid a\equiv b\pmod 2\}$, where $a^nb^m$ is the string of $n$ copies of $a$ followed by $m$ copies of $b$. It turns out that a finite automaton can be built to do this. The point here is that any computational problem can be turned into a language recognition problem, where the language is effectively an encoding of the possible solutions. In other words, the language $$ \{(0, 0), (0, 2), (0, 4),\dots, (2, 0), (2, 4), \dots, (1, 1), (1, 3), \dots,\} $$ can, suitably coded, be recognized by a FA

Other Automata. It happens that finite automata can't recognize solutions to all problems. For example, a FA (finite automaton) can't recognize the language $L_2=\{a^nb^n\mid n\ge 0\}$, in other words, it isn't powerful enough to determine whether two nonnegative integers $n, m$ are equal. If we modify our FA model by including a stack where we can push or pop symbols depending on the input string (as well as change to another state), then this new model (a pushdown automaton or PDA, as it's known) can recognize the language $L_2$ and also the language $L_3=\{a^nb^mc^{n+m}\}$, so a PDA can determine whether two numbers sum to another. It happens, though, that PDAs aren't powerful enough to do the same for products. We can continue this process, adding enhancements to each abstract model of computation, and get a hierarchy of increasingly more powerful machines. The exciting part is that this hierarchy quickly comes to an end.

Turing Machines. If we take a FA and add to it an arbitrary long list (called a tape) initially containing the input and allow moves where the current state and the current contents of an element in the list determine the next state, what we write in the current list element, and whether we move one position forward or backward in the list, we have Turing's 1936 abstract machine, a Turing Machine, or TM. This simple device is extremely powerful: it can add, subtract, multiply, divide, move data to a different location on the tape, compare two chunks of data and base its actions on the results of the comparison, and do things like compute prime numbers and give the $n$-th digit of $\pi$. In fact, it can do everything that modern computers can do and more, since, being an abstract machine, it has an arbitrarily large amount of "memory" on its tape, potentially vastly larger than the number of elementary particles in the universe.

Things to do With TMs. With this model, we can perform all the tasks we're used to:

  • Implement Functions. We can build a TM that, say, computes square roots: given two numbers on its tape, like "3.1416#7", we can define the moves of a TM to produce the square root of the input, 3.1416, to seven digits of precision, so at the end of its calculations, the tape would contain "1.7724559". This is just an algorithm: a finite sequence of steps in some model that produces a result according to our specifications.
  • Language recognizers (and problem solvers). We could design a TM that recognizes the language of primes: $L_4=\{2,3,5,7,11,13,17,19, \dots\}$: given an input tape initially containing an integer $P$, this machine could determine if $P\in L_4$, namely if $P$ is the decimal representation of a prime number.
  • Programmable Computers. It's even possible to design a universal TM which takes a suitably coded description of a TM, $\langle M\rangle$ (perhaps by a listing of its move rules), and an input $X$ and simulate the action of $M$ on input $x$, which of course exactly what a real-world computer plus compiler does.

Remarks and Consequences

Fully fleshed out, this narrative has a flow, from simple machines to, ultimately, a machine that's more powerful than any modern physical computer. The narrative doesn't stop there, though. The Church-Turing Thesis says that anything that we would agree falls under our definition of "computation" can be accomplished by a TM. In other words, the Church-Turing Thesis is a confident bet that not only are TMs more powerful than any modern computer, but that they can accomplish anything we'd call computation on any future computer.

It gets even better, though. Since the (uncountable) infinity of possible functions from the integers to themselves is vastly larger than the (countable) infinity of possible Turing Machines, it means that there are lots of tasks that TMs (and hence computers) cannot do. That might not be a real-world problem, since the functions that TMs can't compute are in a very real sense undescribable, but there are also plenty of seemingly programmable tasks that TMs (and hence computers) cannot do. For example, "given a listing of a program and an input for that program, can we always determine whether that program will eventually halt when given that input?" Professional programmers would love such a tool, but it is provably impossible to construct a program to determine, for all program listings and inputs, whether that program will perhaps enter an infinite loop or not. Similarly, there is no hope of determining, in all cases, whether a given program will behave according to some set of specifications. So our fascinating narrative has a sad ending: there are (infinitely many) tasks computers will never be able to do.

$\endgroup$
4
$\begingroup$

What you seem to be talking about is a deterministic finite automata (DFA). A DFA has no output. It either accepts or doesn't accept its input. In other words, they only give yes/no answers.

A Turing Machine (TM) is a generalization of a DFA that is equipped with infinite memory (as opposed to the mere constant memory of the DFA). A TM is more powerful than a DFA. TMs are algorithms: they take an input, and produce an output (or loop infinitely, as it may be). While usually in complexity theory we also think of TMs as only providing yes/no answers, they can easily be modified to also give an output string.

A Turing Machine is not a computer. They are equivalent in power to the computers we use everyday, but are much simpler. They are a model of computation, that is used by theorists when discussing the theory of computation. The states and transition function have no simple direct analogue in a real-life computer.

A Turing Machine can model a computer, and not just one algorithm, because there is a Universal TM (actually, there are many) that takes another TM as its input and simulates it. That is, a Universal TM is programmable in the everyday sense of the word.

You should really read an introductory book on the Theory of Computation (the one by Sipser is excellent) if you want to understand these concepts fully. You seem to have some definitions muddled.

$\endgroup$
  • $\begingroup$ thanks. "A Turing Machine can model a computer, and not just one algorithm", but you wrote "TMs are algorithms: they take an input, and produce an output (or loop infinitely, as it may be)." I also saw here "A Turing Machine is the formal analogue of an algorithm." So what is the relation betwen a TM and an algorithm? $\endgroup$ – Tim Jun 12 '14 at 23:37
  • $\begingroup$ What is the confusion? Both comments assert that a TM is an algorithm. The fact that a TM can model a programmable computers only means that, in a sense, a computer is nothing more than a sophisticated algorithm whose input is other algorithms. $\endgroup$ – gardenhead Jun 12 '14 at 23:51
  • $\begingroup$ Thanks. I see. an algorithm is informally a sequence of instructions. What is its formal definition then? $\endgroup$ – Tim Jun 13 '14 at 0:15
  • $\begingroup$ The formal definition of an algorithm is a Turing Machine. That is, all Turing Machines compute algorithms and an algorithm is what can be computer by a Turing Machine. There are other ways of defining an algorithm, but they are all equivalent to this definition. This is known as the Church-Turing Thesis. $\endgroup$ – gardenhead Jun 13 '14 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.