Surprisingly Turing-Complete (2021)
gwern.net
gwern.net
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 analogous to putting more memory in your computer when you have a problem that doesn't fit.
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_lang...
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*.
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.
L_n = { w | TM accepted the word w in at most n steps }
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).
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.
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)).
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.
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.
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.
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.
Also DFA has no looping as in "doing infinite computation steps over finite input".
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.
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?
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.
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.
By using Peano Axioms? Now wait a minute!
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.
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.
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.
https://techcommunity.microsoft.com/t5/excel-blog/announcing...
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]).
Surprisingly Turing-Complete - https://news.ycombinator.com/item?id=22839035 - April 2020 (49 comments)
Surprisingly Turing-Complete - https://news.ycombinator.com/item?id=10318729 - Oct 2015 (61 comments)
Nothing in the list is Turing-complete because they don't have infinite tape it its equivalent.
Since memory is finite they are all finite state machines and therefore can only accept regular languages.
(Except Peano arithmetic and the like which are purely theoretical)
Turing completeness is a useful tool for the analysis of actual, real life computers and their programs, despite their finitude.
That was supposed to be a sarcastic response to pedantry in the thread.
Turing completeness is a model, not reality. Choosing the right model is a judgment call.