6
$\begingroup$

Something is Turing Complete if it can be used to simulate any Turing Machine.

So, can a Finite Automaton simulate a Turing Machine?

On the question Can regular languages be Turing complete? they say a Regular Language can be Turing Complete, but it does not make sense to me. I am not talking about the Language being parsed, but the Finite Automaton itself.

Finite Automatons and Regular Languages are not Equivalents. Finite Automatons are machines which accept or reject some Language. But Regular Grammars and Finite Automata are equivalents because I can convert one to another. Then, the question is, are Regular Grammars Turing Complete? Are Type 0 grammars Turing Complete? i.e., can I use a Regular Grammar or a Type 0 Grammar to do any computation I would like?

Can I write a Finite Automaton to do anything a Full-Featured General Purpose Computer can do?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ This is literally answered in TCS 101 and, presumably, any reference on computablity and/or regular languages. What motives your question here? $\endgroup$
    – Raphael ♦
    Jun 21, 2019 at 17:57
  • $\begingroup$ "Can I write a Finite Automaton to do anything a Full-Featured General Purpose Computer can do?" Sure, but good luck finding enough paper to write it on. $\endgroup$
    – DarthFennec
    Jun 21, 2019 at 19:46
  • $\begingroup$ @Raphael, my motivation is to understand how much powerful these machines are. The linked question about Regular Languages said In short, the answer is yes, which was very confusing to me. Now, with these answers, I can understand it perfectly they are not! Thanks to everybody! $\endgroup$
    – user
    Jun 22, 2019 at 1:27

4 Answers 4

Reset to default
19
$\begingroup$

No finite automaton can simulate a Universal Turing machine, so finite automatons are not Turing complete. This falls out immediately from them having a finite number of states. Universal Turing machines require an unbounded amount of space to work.

The source code of an Jot program can be recognized with a finite automaton. That automaton doesn't evaluate the program (and thus doesn't play the role of a Turing machine), it just determines whether or not it is well-formed enough to be run.

This is in contrast with most programming languages. For example, because JavaScript has nested () and {}, it's necessarily not regular (but is, at least approximately, context free). Indentation sensitive languages like Python aren't even context-free (without preprocessing of identation).

This isn't that interesting of an observation. For example, the following is a Turing-complete a subset of syntactically-valid JavaScript programs that is recognizable with a regular expression:

/^eval\("[^\n\"]+"\)$/

...just most of these will immediately throw a runtime error because eval will not parse its single argument -- essentially we can define a programming language to treat all inputs as "syntactically valid" by just defining a new runtime behavior for all the syntactically invalid ones.

What is maybe more interesting about Iota is that its grammar also naturally parallels the actual structure of programs, instead of being a weird encoding trick like the above.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Technically, you'd need [^\n\r"\\\u2028\u2029]+ to be syntactically valid. $\endgroup$
    – LegionMammal978
    Jun 21, 2019 at 20:03
  • $\begingroup$ The game of life is Turing complete while being a finite automaton $\endgroup$
    – slebetman
    Jun 22, 2019 at 14:34
  • 4
    $\begingroup$ The game of Life is not a finite automation. It's a cellular automaton that only becomes Turing complete if it has an unbounded board (and therefore infinite states) $\endgroup$
    – Curtis F
    Jun 22, 2019 at 16:38
9
$\begingroup$

Can I write a Finite Automaton to do anything a Full-Featured General Purpose Computer can do?

Your computer is a finite automaton. It's state can be uniquely described by the content of its registers, RAM, SSDs, etc. Every input (including the system clock) causes a transition from one state to the next, in a deterministic manner. Conceivably, you could enumerate all the possible states, and draw the arcs between them, forming a deterministic finite automaton (DFA). There are maaaaany states, but they are finite.

However, this only works because the infinite memory requirement of Turing machines (TMs) is often ignored (exactly because it would never be achievable, so it's of little pragmatic use).

Pushdown automata (PDAs) and TMs can be thought to have two separate components.

  1. A "decision making" part, that decides how one state should transition to a next, analogous to a CPU.
    • In a PDA, this is the automaton
    • In a TM, it's the rule set by which symbols are evaluated
  2. They also have a "working memory", whose job is to contain most of the state of the system, analogous to RAM.
    • In a PDA, this is the push-down stack
    • In a TM, it's the tape

DFAs have both of these components rolled into one. The automaton is responsible both for all decision making, and for all state-keeping. As a consequence, the state can never be bigger than the DFA.

There is an asymmetry here: PDAs and TMs are granted use of infinite storage (bottomless push-down stacks, infinite tapes), whereas DFAs are not, by definition. If a DFA was given the same affordance for infinite state-keeping (by allowing it to have infinite states), it would no longer be a deterministic finite automaton. It would be a deterministic infinite automaton!

Interestingly, infinite state-automata are not only Turing Complete, but they're actually more powerful than Turing Machines. With infinitely many states allowed, any langauge can be expressed as an automaton with one start node, one accepting state, and one non-accepting state. For every string in the language, an arc is made to the accepting state. For every other string, an arc is made to the non-accepting state.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ It's relevant to mention here that though a real-world computer has only finitely-many states, they're crucially exponentially many in the system complexity, whereas a general DFA has only linearly-many states. That's the reason a small computer can already approximate a Turing machine better than any DFA whose state diagram you could actually implement explicitly. $\endgroup$
    – leftaroundabout
    Jun 21, 2019 at 13:59
  • 1
    $\begingroup$ The last paragraph talks about expressiveness, i.e. the amount of symbols required to express an algorithm. Power is the set of expressible algorithms, and there are no algorithms known that aren't expressible with a Turing Machine, so asserting that some machine is more powerful goes well beyond the boundaries of current-day knowledge - I doubt you intended to do that ;-). $\endgroup$
    – toolforger
    Jun 23, 2019 at 9:21
  • $\begingroup$ @toolforger Are you sure? What about the halting problem? A TM can't solve it, but a Finite State Automaton should be able to (by enumerating every possible program using them as labels to "halts" and "does not halt" states $\endgroup$
    – Alexander
    Jun 23, 2019 at 14:54
  • $\begingroup$ @toolforger "there are no algorithms known that aren't expressible with a Turing Machine" I mean technically yes, seeing that our current definition of an algorithm is that it can be expressed with a Turing machine. But it is well known (and has been for a long time) that there is an infinite hierarchy of strictly more powerful models of computation $\endgroup$
    – DreamConspiracy
    Jun 23, 2019 at 17:23
  • $\begingroup$ @DreamConspiracy "that there is an infinite hierarchy of strictly more powerful models of computation" Could you tell me more about this? Is there a term I could look up? $\endgroup$
    – Alexander
    Jun 23, 2019 at 17:36
1
$\begingroup$

can a Finite Automaton simulate a Turing Machine?

No. Some Turing machines don't halt on some inputs, but every finite automaton halts on every input.

Also, I'd say that your question contains a category error. Turing completeness is a property of systems analogous to programming languages. You're asking about whether a model of computation is Turing-powerful.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I don't know if there is a difference between the English term "Finite Automaton" and the corresponding German term. However, if both terms have the same meaning, a traffic light state machine would be a "Finite Automation" with the four states: Red -> Red-Yellow -> Green -> Yellow -> Red -> Red-Yellow -> and so on. This state machine also will never halt. $\endgroup$
    – Martin Rosenau
    Jun 22, 2019 at 13:39
  • $\begingroup$ @MartinRosenau en.wikipedia.org/wiki/Deterministic_finite_automaton The machine reads an input one character at a time, changing state as it reads each character. When it reaches the end of the input, it terminates, and accepts or rejects its input according to the state it's in at the time. $\endgroup$
    – David Richerby
    Jun 22, 2019 at 14:02
  • $\begingroup$ Your answer is correct only for finite inputs (i.e. if the FA is being forced to halt on end-of-input). This used to be an implicit assumption for everybody, but is not anymore, so you'd have to mention that assumption in the answer. (Infinite input does make sense, stream processing is getting more and more attention.) $\endgroup$
    – toolforger
    Jun 23, 2019 at 9:42
  • $\begingroup$ @toolforger That's a fair point. However, we're in the context of comparing against Turing machines, and Turing machines operate on finite inputs. $\endgroup$
    – David Richerby
    Jun 23, 2019 at 13:54
  • 1
    $\begingroup$ @toolforger In my experience, the set-up you're talking about is usually called a "finite state machine" rather than a "finite automaton". $\endgroup$
    – David Richerby
    Jun 23, 2019 at 20:52
1
$\begingroup$

No

Finite Automata are not Turing Complete because they have a limited amount of memory. If that limit of memory were to be removed, the Finite Automaton in question would be Turing Complete.

Let's take a Finite Automaton which is a Turing Machine except it is restricted to 10 states. This would not be able to be Turing Complete because it wouldn't be able to simulate every program with 11 states. Even if you extend it to 10,000,000 states, it will not be able to simulate an optimal program using 1,000,000 states (a program with the minimum states being used being 10,000,000 without being able to be golfed anymore) except with a 10,000,001st state being to move right. Therefore, a Finite Automaton must not be Turing Complete due to memory constraints.

Many programming languages like Malbolge or C are affected by this because they have a limited memory.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ So no implementation of a Programming language is Turing complete under the infinite memory requirement assumption. (Which makes it pretty useless requirement) $\endgroup$
    – eckes
    Jun 23, 2019 at 19:13
  • $\begingroup$ @eckes I don't get what you are trying to say. Are you attempting to say that my answer infers that no programming language is Turing Complete with infinite memory? $\endgroup$
    – MilkyWay90
    Jun 23, 2019 at 19:37
  • 1
    $\begingroup$ No I mean real world implementations with finite memory. But I guess it’s not really relevant. $\endgroup$
    – eckes
    Jun 23, 2019 at 20:12
  • $\begingroup$ @eckes Yes, that would be considered a finite state automaton. Only the theoretical programming language with no memory limits would e Turing Complete, not the implementation in a real-world computer. $\endgroup$
    – MilkyWay90
    Jun 23, 2019 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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