An automaton, as I have seen so far, is used to tell if a string belongs to the

Question

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?

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?

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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.