4 ms·

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. Th

by 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.

ablob 4y ago
His point is that the language of all inputs on which a Turing Machine holds after at most N steps is regular. So for any given Language L that a Turing Machine TM decides, there is a family of languages: L_n = { w | TM accepted the word w in at most n steps } where n is a natural number such that every L_n is a regular language. And as you already said, a regular language can be decided by a finite state machine. Edit: It was never stated that a Turing Machine could be simulated completely, but that one can choose an N that is large enough for a given need. If that N wasn't large enough for a given input, then so be it - the input is not accepted (or whatever you defined it to be).
- Kranar 4y ago
  >It was never stated that a Turing Machine could be simulated completely, but that one can choose an N that is large enough for a given need. What I read was that an FSM can be used to simulate Turing Machines that always halt which was then edited to claim that an FSM can simulate a Turing Machine that halts for a given input. Both those claims are false for reasons I explained. You have further revised the claim to state that for a given bound on the length of an input, there exists an FSM that can simulate a Turing Machine for that same input. That's technically true but that's no more insightful than just saying that FSMs are a proper subset of Turing Machines. For example you wouldn't say that the FSM corresponding to some regular expression, for example "a*b*", is a simulator for a Turing Machine that's a decider for strings that start with zero or more "a"s followed by zero or more "b"s. If you put a fixed bound on the length of the input then you can just take a notebook, list all inputs in lexicographical order along with whether that input maps to true or false. Since presumably the length of the input is bounded by some fixed constant N, then the number of inputs is also bounded by 2^N (assuming a binary alphabet). The confusion that really needs to be avoided is the idea that there's a subset of Turing Machines that can be simulated by FSMs on the basis of whether or not the TM halts, as though TMs that halt can be simulated by an FSM, and that the key differentiator between an FSM and a TM has to do with infinite loops. It's totally possible for a TM to halt on all inputs and yet there is no corresponding FSM.
  - bdowling 4y ago
    Hi Kranar. See my other post with the reference to linear bounded automata. I think you're right on all points. Also, I agree that "simulates" is probably the wrong word. There would be a one-to-one mapping between FSM states and restricted-TM (or Linear Bounded Automaton) states and it would "simulate" the TM by stepping through mapped states until it reached a terminal state, but the number of states required and the transition table would be ridiculous. I don't think it would exactly be a look-up table, but it's close. (i.e., it would be O(2^N), for a binary alphabet, to construct the transition table, but looking up the terminal state for each input state would also be O(2^N)).
bdowling 4y ago
Looking at Wikipedia, what I'm thinking of may be equivalent to a Linear Bounded Automaton. https://en.wikipedia.org/wiki/Linear_bounded_automaton https://en.wikipedia.org/wiki/Linear_bounded_automaton Specifically, I'm thinking of the "less restrictive definition." Also, I realize I elided over the fact that a FSM traditionally reads its input "as it goes", whereas a TM has its input pre-written to the tape. To work the way the TM would, my FSM would need to have its initial state set to the one corresponding to the TM initial configuration, and it would take some clock input that it would ignore at each step. Each state would have one transition that would ultimately lead to a terminal state, if it doesn't loop forever. Actually constructing an FSM based on this idea is impractical because constructing it would require a huge number of states. Again, the number of FSM states would be equal to (# TM states) * (number of cell positions) * (# symbols)^(bounds of tape). For anything non-trivial that's a ludicrous number of states. Similarly, constructing the state transition table would be O((# symbols)^(bounds of tape)) operations. Logically, it can be done but it's only useful as a mental exercise.
geysersam 4y ago
It's common to regard a computer as Turing complete. And most computers have no problems parsing html. However, any real computer is a finite state machine.

by Kranar 4y ago

ablob 4y ago

His point is that the language of all inputs on which a Turing Machine holds after at most N steps is regular. So for any given Language L that a Turing Machine TM decides, there is a family of languages: L_n = { w | TM accepted the word w in at most n steps } where n is a natural number such that every L_n is a regular language. And as you already said, a regular language can be decided by a finite state machine. Edit: It was never stated that a Turing Machine could be simulated completely, but that one can choose an N that is large enough for a given need. If that N wasn't large enough for a given input, then so be it - the input is not accepted (or whatever you defined it to be).

Kranar 4y ago
>It was never stated that a Turing Machine could be simulated completely, but that one can choose an N that is large enough for a given need. What I read was that an FSM can be used to simulate Turing Machines that always halt which was then edited to claim that an FSM can simulate a Turing Machine that halts for a given input. Both those claims are false for reasons I explained. You have further revised the claim to state that for a given bound on the length of an input, there exists an FSM that can simulate a Turing Machine for that same input. That's technically true but that's no more insightful than just saying that FSMs are a proper subset of Turing Machines. For example you wouldn't say that the FSM corresponding to some regular expression, for example "a*b*", is a simulator for a Turing Machine that's a decider for strings that start with zero or more "a"s followed by zero or more "b"s. If you put a fixed bound on the length of the input then you can just take a notebook, list all inputs in lexicographical order along with whether that input maps to true or false. Since presumably the length of the input is bounded by some fixed constant N, then the number of inputs is also bounded by 2^N (assuming a binary alphabet). The confusion that really needs to be avoided is the idea that there's a subset of Turing Machines that can be simulated by FSMs on the basis of whether or not the TM halts, as though TMs that halt can be simulated by an FSM, and that the key differentiator between an FSM and a TM has to do with infinite loops. It's totally possible for a TM to halt on all inputs and yet there is no corresponding FSM.
- bdowling 4y ago
  Hi Kranar. See my other post with the reference to linear bounded automata. I think you're right on all points. Also, I agree that "simulates" is probably the wrong word. There would be a one-to-one mapping between FSM states and restricted-TM (or Linear Bounded Automaton) states and it would "simulate" the TM by stepping through mapped states until it reached a terminal state, but the number of states required and the transition table would be ridiculous. I don't think it would exactly be a look-up table, but it's close. (i.e., it would be O(2^N), for a binary alphabet, to construct the transition table, but looking up the terminal state for each input state would also be O(2^N)).

bdowling 4y ago

Looking at Wikipedia, what I'm thinking of may be equivalent to a Linear Bounded Automaton. https://en.wikipedia.org/wiki/Linear_bounded_automaton https://en.wikipedia.org/wiki/Linear_bounded_automaton Specifically, I'm thinking of the "less restrictive definition." Also, I realize I elided over the fact that a FSM traditionally reads its input "as it goes", whereas a TM has its input pre-written to the tape. To work the way the TM would, my FSM would need to have its initial state set to the one corresponding to the TM initial configuration, and it would take some clock input that it would ignore at each step. Each state would have one transition that would ultimately lead to a terminal state, if it doesn't loop forever. Actually constructing an FSM based on this idea is impractical because constructing it would require a huge number of states. Again, the number of FSM states would be equal to (# TM states) * (number of cell positions) * (# symbols)^(bounds of tape). For anything non-trivial that's a ludicrous number of states. Similarly, constructing the state transition table would be O((# symbols)^(bounds of tape)) operations. Logically, it can be done but it's only useful as a mental exercise.

geysersam 4y ago

It's common to regard a computer as Turing complete. And most computers have no problems parsing html. However, any real computer is a finite state machine.