Not quite Turing-complete, but any Turing machine <i>that halts on a given input</i> 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.<p>Similarly, any actual computer with finite memory can be modeled as a finite state machine with 2^(# bits of all memory, registers, storage) states.<p>Edit: Changed "<i>that halts</i>" to "<i>that halts on a given input</i>".
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?<p>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.
At times I've seen people claiming a system is Turing complete even though it can't even implement an infinite loop.<p>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.<p>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.
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.
Was surprised to see no mention of <i>Langton's ant</i>, which is somewhat like Conway's Game of Life, and was eventually shown to be Turing complete.<p><a href="https://en.wikipedia.org/wiki/Langton%27s_ant" rel="nofollow">https://en.wikipedia.org/wiki/Langton%27s_ant</a>
Magic the Gathering is turing complete.
<a href="https://arxiv.org/abs/1904.09828" rel="nofollow">https://arxiv.org/abs/1904.09828</a>
Does it list Jira?<p><a href="https://news.ycombinator.com/item?id=17689446" rel="nofollow">https://news.ycombinator.com/item?id=17689446</a>
I take the strict view.<p>Nothing in the list is Turing-complete because they don't have infinite tape it its equivalent.<p>Since memory is finite they are all finite state machines and therefore can only accept regular languages.<p>(Except Peano arithmetic and the like which are purely theoretical)