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".
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.
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*.
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.
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.
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.
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).
>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.
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)).
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.
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.
Are these meta programs (running on virutal turing machines made of symbolic circuits within programs) effectively able to only arrange the base program's heap, and still need an overflow somewhere in the base program to break out of the base program's sandbox?
I remember this technique being used in the wild and described by google's TAG group in a recent paper, but this part about how it goes from toy virtual machine within the base program to a sandbox escape didn't land for me.
Yes, but a weird machine program may be able to turn an extremely unlikely exploit into a guaranteed one; for example rowhammer, or heating up the hardware to induce bit flips, or simply making enough vulnerable objects that when a "cosmic ray" bit flip eventually occurs, it will immediately result in a breakout. Or purely in software, by arranging for hash collisions that would be prohibitively unlikely to occur in a normal execution.
Even if it can't achieve breakout, a weird machine program may still be able to observe its host and leak information to an attacker-controlled server via timing attacks. I think the ExSpectre attack mentioned near the end is related to this.
At times I've seen people claiming a system is Turing complete even though it can't even implement an infinite loop.
For example, Excel spreadsheets (without scripting) can't loop infinitely as far as I know, and yet I've seen it claimed that they're Turing complete.
In the case of this article, what does it mean to say Peano arithmetic is Turing complete? Arithmetic only provides you with a way to manipulate numbers, it doesn't provide any way to loop AFAIK.
> what does it mean to say Peano arithmetic is Turing complete?
It means that for any TM described by a state transition table X which produces output Y when run on tape Z, there exists a corresponding theorem of PA that encodes that fact under a suitable mapping from X, Y and Z to natural numbers.
UPDATE: The converse is also true: for any theorem of PA there exists a TM that produces a proof of that theorem. The interesting bit here is that there is one TM that does this for any theorem of PA. And note that this machine is not the same as the universal TM that emulates any other TM.
UPDATE2: The way I worded that was a little misleading. There are many TM's that produce a proofs of theorems of PA, but you only need one of them to produce any proof you want. Of course, the universal TM is one of the machines that can be deployed for this task.
It doesn't matter if the system can "automatically" implement an infinite loop. E.g. in excel it's fine if the user is involved by clicking a button repeatedly or something to drive the system forward. It's more about, is the description of this system rich enough to emulate the semantics of a turing machine?
I think you're missing the point. Unlike in the case of an ideal Turing machine, nothing in this universe transitions through states without energy. Computers rely on the power grid to run their processor cycles, even though I doubt that you would consider computers to not be Turing complete.
This is not that different from the Excel example: the system displays Turing completeness if supplied a clock as input (a person clicking a button in the spreadsheet, for instance). The human is not making any decisions in this case - the logic manifests itself entirely from within the system.
No, it seems that you are the one that don't understand.
A piece of paper is not Turing Complete because the computation happens in the head of whoever is holding the pen.
An excel sheet (or actually a power point presentation!) is, because the user just has to mindlessly, unconditionally, do a simple, non computational action to make the cycles go forward.
There is a difference between the two scenario, and if you can't see it, please do ask questions until I'm able to make that clear to you.
The turing machine isn't mindful, anyway, the engineer is.
You don't have to turn this into a philosophical problem that will inevitably pitch hypothetical GAI against menial workers, thousand monkeys on a typewriter, or equivalently a young person and billions of neurons on blank canvas. That's not anymore about the technical point of the submission. It would need back up from psychology to remain remotely technical: why did the chicken cross the road?
Turing machine emulates a computer (a human that computes) with an infinite pencil, infinite sheet of paper and infinite eraser.
Lambda calculus emulates a computer (a human that computes) with an infinite pencil and infinite sheet of paper.
This is taken, if I remember correctly, straight from the communication between Church and Turing.
So, the logic is correct. Human can execute Turing machine and Turing machine (and lambda calculus) were invented to formalize the notion of human computers.
Right, I forgot storage. Yet in the context of "a model (spreadsheet) with bounded storage and bounded computation steps count is TM complete when looping is externalized", one can externalize storage as well, or encode storage in DFA states and use bigger DFA when storage of current runs out, or handwave storage unboundedness as in argument about spreadsheet.
Also DFA has no looping as in "doing infinite computation steps over finite input".
the paper is not turing complete, it's just the working memory/input but turing completeness is in the rules applied to that input, not in the what/who is applying them.
> By that logic you might as well say a piece of paper
Yes, and if you read through the pieces of paper that make up the articles that described Turing copleteness you’ll realize that they don’t talk about mechanical machines but about mathematical and local systems. Moving rocks in the desert according to fixed rules can make up a Turing complete system, as can markings on paper.
With this loose definition of Turing complete - manipulations of a thing with a finite number of states that could be infinite by extension (you supply the manipulations) - then everything that's NP-complete is Turing complete, including Microsoft's Minesweeper and clones.
Well, myself and the gp were referring to the approach of the OP, saying "X is Turing complete" meaning "would be Turing complete if you add these extra elements, like a tape or whatever". If you start with a time-limited Turing Machine and remove the time-limit, then you have a full Turing Machine now don't you.
Don't take any of this very seriously, my comment was more about the looseness of the whole approach in the article than any significant claim.
The claims about spreadsheets being Turing complete predate this, though. I always wondered the same thing - how do you get there without looping, and without infinite cells?
To consider any system Turing complete you have to extend it to having infinite memory. This is why all actual, non-theoretical computers are equivalent to finite state machines (or linear bounded automata [0]).
You can do looping by enabling iterative calculation mode, which has been supported in Excel for much longer than LAMBDA. In iterative mode, Excel attempts to resolve cyclic references in formulas by recalculating until the results converge, or a maximum number of iterations is reached. Unfortunately setting a maximum number of iterations is required... but one could argue that iterative mode does bring the spreadsheet model a bit closer to Turing completeness.
Tangential question; but I just found out about gwern's page and I'm amazed at the amount of content and a lot of it looks very interesting, does anyone know any more personal websites similar to this one? I'm sure there were at least a couple but I can't find them.
No. I would need more details to decide, not an apocryphal 'some guy supposedly proved it somehow' comment. (For example, if Jira used some scripting interface like JS or something, then it would be very unsurprising - merely disappointing.)
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".