4 ms·

It doesn't. As someone pointed out, Tic Tac Toe can be implemented in Finite State Machines [1], which have less computational ability than Turing Machines [2].

It doesn't. As someone pointed out, Tic Tac Toe can be implemented in Finite State Machines [1], which have less computational ability than Turing Machines [2]. [1] https://en.wikipedia.org/wiki/Finite-state_machine https://en.wikipedia.org/wiki/Finite-state_machine [2] https://en.wikipedia.org/wiki/Turing_machine https://en.wikipedia.org/wiki/Turing_machine

Buge 12y ago
Isn't the only difference between a finite-state machine and a Turing machine whether the memory is finite or not? Then you could argue that nothing has ever been made that is Turing complete because everything can be simulated by a finite-state machine because of memory limitations.
- Dewie 12y ago
  Yes; in the strictest sense, CPU+RAM is a finite state machine, not a Turing machine with an unbounded memory.
- edmccard 12y ago
  There is a difference, though, between a finite state machine and a Turing machine with a finite amount of memory. An FSM cannot recognize context-free languages, but a Turing machine can--even when it's implemented on a computer without infinite memory. (Actually, you only need a pushdown automata for context-free languages--I forget what the next step up in the hierarchy is, the one that does require Turing completeness)
  - mikeash 12y ago
    A Turing machine without infinite memory can't recognize context-free languages. Take the standard example of recognizing the language of balanced parentheses. With finite memory, there's a limit to how many parentheses you can keep track of. That limit is going to be gigantic for any reasonable amount of memory, but it's still a limit. The language of balanced parentheses with a depth limit is no longer a context-free language, but a regular language, and as such can be recognized by a FSM. It's trivial to demonstrate that a Turing machine with finite memory is equivalent to a FSM. Enumerate all possible memory contents. This number is, again, large for any reasonable amount of memory, but it is finite. For each possible memory content, enumerate the Turing machine states. Each memory state plus machine state becomes one FSM state. The Turing machine defines a transition from one state to another plus an action on memory, which becomes an FSM transition to the state that encodes both the new machine state and the new memory state.
    - timtadh 12y ago
      Not at all true, the language of balanced parens is not regular and cannot be matched by a FSM no matter how much memory you have.[1] It can be matched by a Push Down Automata PDA. The primary difference between a PDA and an FSM is a PDA has a stack which acts as memory. Thus, a PDA can remember how many parens it has seen before. Every time it sees an open paren it will push it onto the stack, when it sees a close paren it pops. When the stack is empty it matches if the input has been consumed. The difference between a PDA and a Turing machine is the stack is now a read/writable tape which can move in either direction. Notice how in both formulations there is no limit on the memory (the PDA stack is could be infinite as can the Turing machine tape). In contrast a Finite State Machine doesn't have any memory. The finite refers to the number of states not the amount of memory. Indeed, Turing machines are traditionally formulated with finite states as well. Thus, a FSM can never match the langauge of matching parens but a Turing machine can. It will either match or consume all of its memory if memory is limited. Memory limitations are not a statement on computational power but rather a statement on feasibility. https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Use_of_lemma https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang... EDIT: Your second paragraph is of course correct - you could encode every possible stack as a FSM if there is a bound on the stack. HOWEVER, if you have a limit on memory but it is essentially unknown (you know memory is finite but you don't know exactly what the limit is) a PDA or a Turing machine will of course be able to match things your FSM cannot (because they can take advantage of the memory your FSM cannot assume it has in its states). Memory limitations are in some sense an implementation detail. We could design a computer to pause while we buy more ram. Then it could use as much memory (in theory) as the human race could produce. That sounds like infinite for some definition of the word.
      - Sharlin 12y ago
        > Not at all true, the language of balanced parens is not regular and cannot be matched by a FSM no matter how much memory you have. But this is not what the grandparent was saying. They said that the language of balanced parentheses with some depth limit d can be matched with a FSM, for any finite d. Similarly, a "Turing machine" with a bounded tape can only recognize a bounded version of the balanced parentheses language.
  - coolsunglasses 12y ago
    Regular -> Context-Free -> Context-Sensitive http://en.wikipedia.org/wiki/Chomsky_hierarchy http://en.wikipedia.org/wiki/Chomsky_hierarchy Incidentally, applicative parsers can parse* context-free grammar whereas monadic parsers can parse context-sensitive grammars. https://cs.uwaterloo.ca/~plragde/842/handouts/app-mon-qiao.pdf https://cs.uwaterloo.ca/~plragde/842/handouts/app-mon-qiao.p... * actually there's a cheat for getting applicative parser combinator libraries to parse a CSG, but lets put that aside for now.
- im3w1l 12y ago
  In my opinion an important point is that for a turing complete language being run on a machine with finite memory, if you have problem for which it runs out of memory, you could conceivably throw more memory at the problem and have it work. If you a non-complete language, more memory is not enough, you will have to do a rewrite in addition.

Buge 12y ago

Isn't the only difference between a finite-state machine and a Turing machine whether the memory is finite or not? Then you could argue that nothing has ever been made that is Turing complete because everything can be simulated by a finite-state machine because of memory limitations.

Dewie 12y ago
Yes; in the strictest sense, CPU+RAM is a finite state machine, not a Turing machine with an unbounded memory.
edmccard 12y ago
There is a difference, though, between a finite state machine and a Turing machine with a finite amount of memory. An FSM cannot recognize context-free languages, but a Turing machine can--even when it's implemented on a computer without infinite memory. (Actually, you only need a pushdown automata for context-free languages--I forget what the next step up in the hierarchy is, the one that does require Turing completeness)
- mikeash 12y ago
  A Turing machine without infinite memory can't recognize context-free languages. Take the standard example of recognizing the language of balanced parentheses. With finite memory, there's a limit to how many parentheses you can keep track of. That limit is going to be gigantic for any reasonable amount of memory, but it's still a limit. The language of balanced parentheses with a depth limit is no longer a context-free language, but a regular language, and as such can be recognized by a FSM. It's trivial to demonstrate that a Turing machine with finite memory is equivalent to a FSM. Enumerate all possible memory contents. This number is, again, large for any reasonable amount of memory, but it is finite. For each possible memory content, enumerate the Turing machine states. Each memory state plus machine state becomes one FSM state. The Turing machine defines a transition from one state to another plus an action on memory, which becomes an FSM transition to the state that encodes both the new machine state and the new memory state.
  - timtadh 12y ago
    Not at all true, the language of balanced parens is not regular and cannot be matched by a FSM no matter how much memory you have.[1] It can be matched by a Push Down Automata PDA. The primary difference between a PDA and an FSM is a PDA has a stack which acts as memory. Thus, a PDA can remember how many parens it has seen before. Every time it sees an open paren it will push it onto the stack, when it sees a close paren it pops. When the stack is empty it matches if the input has been consumed. The difference between a PDA and a Turing machine is the stack is now a read/writable tape which can move in either direction. Notice how in both formulations there is no limit on the memory (the PDA stack is could be infinite as can the Turing machine tape). In contrast a Finite State Machine doesn't have any memory. The finite refers to the number of states not the amount of memory. Indeed, Turing machines are traditionally formulated with finite states as well. Thus, a FSM can never match the langauge of matching parens but a Turing machine can. It will either match or consume all of its memory if memory is limited. Memory limitations are not a statement on computational power but rather a statement on feasibility. https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Use_of_lemma https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang... EDIT: Your second paragraph is of course correct - you could encode every possible stack as a FSM if there is a bound on the stack. HOWEVER, if you have a limit on memory but it is essentially unknown (you know memory is finite but you don't know exactly what the limit is) a PDA or a Turing machine will of course be able to match things your FSM cannot (because they can take advantage of the memory your FSM cannot assume it has in its states). Memory limitations are in some sense an implementation detail. We could design a computer to pause while we buy more ram. Then it could use as much memory (in theory) as the human race could produce. That sounds like infinite for some definition of the word.
    - Sharlin 12y ago
      > Not at all true, the language of balanced parens is not regular and cannot be matched by a FSM no matter how much memory you have. But this is not what the grandparent was saying. They said that the language of balanced parentheses with some depth limit d can be matched with a FSM, for any finite d. Similarly, a "Turing machine" with a bounded tape can only recognize a bounded version of the balanced parentheses language.
- coolsunglasses 12y ago
  Regular -> Context-Free -> Context-Sensitive http://en.wikipedia.org/wiki/Chomsky_hierarchy http://en.wikipedia.org/wiki/Chomsky_hierarchy Incidentally, applicative parsers can parse* context-free grammar whereas monadic parsers can parse context-sensitive grammars. https://cs.uwaterloo.ca/~plragde/842/handouts/app-mon-qiao.pdf https://cs.uwaterloo.ca/~plragde/842/handouts/app-mon-qiao.p... * actually there's a cheat for getting applicative parser combinator libraries to parse a CSG, but lets put that aside for now.
im3w1l 12y ago
In my opinion an important point is that for a turing complete language being run on a machine with finite memory, if you have problem for which it runs out of memory, you could conceivably throw more memory at the problem and have it work. If you a non-complete language, more memory is not enough, you will have to do a rewrite in addition.