3 ms·

Not quite Turing-complete, but any Turing machine that halts on a given input can be simulated by a sufficiently large finite state machine. At each step, a com

Not quite Turing-complete, but any Turing machine that halts on a given input can be simulated by a sufficiently large finite state machine. At each step, a complete TM state can be represented by a tuple of <TM state #, cell position, tape state>. If the TM halts, then it can only have visited a finite number (K) of cells on its tape, plus every possible TM state (N), plus every possible cell position (K), plus every possible state of the tape (2^K). Therefore, we can number each possible state from 1 to N * K * (2^K). Those are the states of our FSM. The FSM transitions are wired up to match the TM transitions to the corresponding TM destination state. Similarly, any actual computer with finite memory can be modeled as a finite state machine with 2^(# bits of all memory, registers, storage) states. Edit: Changed "that halts" to "that halts on a given input".

hakuseki 4y ago
This seems not quite right to me. A Turing machine may always halt, but with time depending on its input size. The input can be arbitrarily large, so there's no finite bound on the state space.
- bdowling 4y ago
  My point, which I admit isn't very poignant, is that you can make an FSM that simulates a TM that only uses a finite portion of its tape. Yes, for some machines you will always be able to construct an input that exceeds what a particular FSM can do. When that happens, however, you can make a bigger FSM that simulates a larger (but still finite) tape. This is analogous to putting more memory in your computer when you have a problem that doesn't fit.
Kranar 4y ago
This is most certainly untrue, a finite state machine can only decide a regular language. Pushdown automatas, which can decide context free languages, also always halt but there is no finite state machine that can simulate them. In other words, there is no finite state machine that can act as a decider for the language "a^ib^i" even though there is a Turing Machine that can decide that language (and since it's a decider, it always halts). Another way of saying this that is more practical is that there is no finite state machine that can be used to decide whether an arbitrary input string is valid HTML, even though a Turing machine exists that always halts and can perform such a decision. The flaw in your argument, and one reason why it may seem convincing, is that in a very subtle way you're constructing a specific finite state machine after knowing the behavior of the Turing machine for a given input, but this is not a valid construction. You must first construct the finite state machine and then apply the input on it, you can't take an input and then build a finite machine customized for it on the basis of what a Turing machine does. If you could do that then it would be trivial to solve any problem whatsoever, just have one state machine that always returns true for all inputs, and another that always returns false for all inputs, and pick the appropriate FSM for your given input based on whether a Turing machine returns true or false. Once you fix a particular choice of finite state machine and then apply an input to it, it's always possible to apply the pumping lemma to identify additional inputs that contain some middle portion of the original input that can be repeated indefinitely. https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...
- bdowling 4y ago
  I edited my post to change the qualifier from "that halts" to "that halts on a given input". Perhaps I should change it to say that you can build a FSM that simulates a machine with a bounded, finite tape. Obviously, such a machine is not a Turing machine because it does not have an infinite tape, the defining characteristic of a TM which allows it to handle arbitrarily-large problems. To solve a problem without a TM solution already available, you can iteratively rebuild the FSM simulator to handle more and more simulated tape states. Assume the FSM simulates states for a TM with a tape of up to size K. If the FSM tries to write beyond the bounds, you make it transition to a terminal "Out of Bounds" state. To use the FSM on an arbitrary input, you run it until it halts. If it halts in the "Out of Bounds" state, you reconstruct the machine to simulate a larger tape (e.g., 2K or 2^K). Continue until the FSM halts on the input (if ever, this doesn't solve the halting problem). Regarding the language a^ib^i, an analogous point would be that you can make an FSM that can decide the language up to an arbitrarily large I*.
  - Kranar 4y ago
    Not quite sure I follow. There is a Turing Machine that will halt for any input you give it and return true if that input is valid HTML, and false otherwise. There is no FSM that can do that. For your second point about iteratively rebuilding an FSM, I mean sure but this goes to my point how you're using the input to decide what FSM to use, which is not a valid construction and even if for the sake of argument you want to go down that route, the choice of what FSM to use requires a Turing Machine so it's not an FSM simulating a Turing Machine but the other way around, the Turing Machine being used to simulate an FSM. As a matter of correctness, you can't base your choice of FSM on the input. If you could, then you don't need any kind of fancy reasoning whatsoever, you can just pick between FSM A or FSM B, where FSM A is a 1 state FSM that always evaluates to true and FSM B is a 1 state FSM that always evaluates to false and you just pick the one you want to use on the basis of what a Turing machine would do. Heck, you could just argue that an FSM is basically a lookup table or a cache of hardcoded inputs whose lengths are no greater than N, and maps those inputs to true or false. But this isn't simulating anything.
    - 4y ago

hakuseki 4y ago

This seems not quite right to me. A Turing machine may always halt, but with time depending on its input size. The input can be arbitrarily large, so there's no finite bound on the state space.

bdowling 4y ago
My point, which I admit isn't very poignant, is that you can make an FSM that simulates a TM that only uses a finite portion of its tape. Yes, for some machines you will always be able to construct an input that exceeds what a particular FSM can do. When that happens, however, you can make a bigger FSM that simulates a larger (but still finite) tape. This is analogous to putting more memory in your computer when you have a problem that doesn't fit.

Kranar 4y ago

This is most certainly untrue, a finite state machine can only decide a regular language. Pushdown automatas, which can decide context free languages, also always halt but there is no finite state machine that can simulate them. In other words, there is no finite state machine that can act as a decider for the language "a^ib^i" even though there is a Turing Machine that can decide that language (and since it's a decider, it always halts). Another way of saying this that is more practical is that there is no finite state machine that can be used to decide whether an arbitrary input string is valid HTML, even though a Turing machine exists that always halts and can perform such a decision. The flaw in your argument, and one reason why it may seem convincing, is that in a very subtle way you're constructing a specific finite state machine after knowing the behavior of the Turing machine for a given input, but this is not a valid construction. You must first construct the finite state machine and then apply the input on it, you can't take an input and then build a finite machine customized for it on the basis of what a Turing machine does. If you could do that then it would be trivial to solve any problem whatsoever, just have one state machine that always returns true for all inputs, and another that always returns false for all inputs, and pick the appropriate FSM for your given input based on whether a Turing machine returns true or false. Once you fix a particular choice of finite state machine and then apply an input to it, it's always possible to apply the pumping lemma to identify additional inputs that contain some middle portion of the original input that can be repeated indefinitely. https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...

bdowling 4y ago
I edited my post to change the qualifier from "that halts" to "that halts on a given input". Perhaps I should change it to say that you can build a FSM that simulates a machine with a bounded, finite tape. Obviously, such a machine is not a Turing machine because it does not have an infinite tape, the defining characteristic of a TM which allows it to handle arbitrarily-large problems. To solve a problem without a TM solution already available, you can iteratively rebuild the FSM simulator to handle more and more simulated tape states. Assume the FSM simulates states for a TM with a tape of up to size K. If the FSM tries to write beyond the bounds, you make it transition to a terminal "Out of Bounds" state. To use the FSM on an arbitrary input, you run it until it halts. If it halts in the "Out of Bounds" state, you reconstruct the machine to simulate a larger tape (e.g., 2K or 2^K). Continue until the FSM halts on the input (if ever, this doesn't solve the halting problem). Regarding the language a^ib^i, an analogous point would be that you can make an FSM that can decide the language up to an arbitrarily large I*.
- Kranar 4y ago
  Not quite sure I follow. There is a Turing Machine that will halt for any input you give it and return true if that input is valid HTML, and false otherwise. There is no FSM that can do that. For your second point about iteratively rebuilding an FSM, I mean sure but this goes to my point how you're using the input to decide what FSM to use, which is not a valid construction and even if for the sake of argument you want to go down that route, the choice of what FSM to use requires a Turing Machine so it's not an FSM simulating a Turing Machine but the other way around, the Turing Machine being used to simulate an FSM. As a matter of correctness, you can't base your choice of FSM on the input. If you could, then you don't need any kind of fancy reasoning whatsoever, you can just pick between FSM A or FSM B, where FSM A is a 1 state FSM that always evaluates to true and FSM B is a 1 state FSM that always evaluates to false and you just pick the one you want to use on the basis of what a Turing machine would do. Heck, you could just argue that an FSM is basically a lookup table or a cache of hardcoded inputs whose lengths are no greater than N, and maps those inputs to true or false. But this isn't simulating anything.
  - 4y ago