10 ms·

Surprisingly Turing-Complete (2021)

108 points by GarethX 4y ago

FartyMcFarter 4y ago
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.
- _hl_ 4y ago
  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?
  - lmm 4y ago
    By that logic you might as well say a piece of paper, or this text input box, is Turing complete, since a human can execute a Turing machine on it.
    - isitmadeofglass 4y ago
      > 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.
    - Isognoviastoma 4y ago
      Notably, finite automata are Turing complete. (TM is DFA + looping).
      - tromp 4y ago
        No; TM is finite control (i.e. DFA which already have a notion of looping) + unbounded storage.
        Isognoviastoma 4y ago
        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".
    - turboponyy 4y ago
      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.
      - edgyquant 4y ago
        That user didn’t “miss the point” and you’ve only reiterated their point that by your logic a piece of paper and pencil is “Turing complete”
        curiousgal 4y ago
        You missed their point, a piece of paper and pencil is not making any decisions.
        posterboy 4y ago
        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?
        linschn 4y ago
        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.
    - Avshalom 4y ago
      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.
    - thesz 4y ago
      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.
    - posterboy 4y ago
      > this text input box, is Turing complete, since a human can execute a Turing machine on it. By using Peano Axioms? Now wait a minute!
- joe_the_user 4y ago
  Well yeah, 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.
  - tromp 4y ago
    No, because being in NP restricts computations to a polynomial number of (non-deterministic) steps.
    - joe_the_user 4y ago
      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.
- lisper 4y ago
  > 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.
- bdowling 4y ago
  The LAMBDA function in Excel can define an infinitely recursing function without using scripting. https://techcommunity.microsoft.com/t5/excel-blog/announcing-lambda-turn-excel-formulas-into-custom-functions/ba-p/1925546 https://techcommunity.microsoft.com/t5/excel-blog/announcing...
  - blast 4y ago
    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?
    - unnah 4y ago
      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.
    - bdowling 4y ago
      > 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]). [0] https://en.wikipedia.org/wiki/Linear_bounded_automaton https://en.wikipedia.org/wiki/Linear_bounded_automaton
jdmoreira 4y ago
Magic the Gathering is turing complete. https://arxiv.org/abs/1904.09828 https://arxiv.org/abs/1904.09828
- aidenn0 4y ago
  Mentioned (and linked) in TFA
- dathinab 4y ago
  as mentioned in the article
e10jc 4y ago
motohagiography 4y ago
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.
- scatters 4y ago
  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.
- saagarjha 4y ago
  The interesting part there was using the Turing machine to gain the ability to set up program stare reliably for the sandbox escape.
dang 4y ago
Related: Surprisingly Turing-Complete - https://news.ycombinator.com/item?id=22839035 https://news.ycombinator.com/item?id=22839035 - April 2020 (49 comments) Surprisingly Turing-Complete - https://news.ycombinator.com/item?id=10318729 https://news.ycombinator.com/item?id=10318729 - Oct 2015 (61 comments)
deleted 4y ago
[deleted]
bdowling 4y ago
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...
dysoco 4y ago
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.
oldgradstudent 4y ago
I take the strict view. 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)
- linschn 4y ago
  This is useless pedantry: by this metric absolutely nothing in the universe can be Turing Complete, and it's only a theoretical construct. Turing completeness is a useful tool for the analysis of actual, real life computers and their programs, despite their finitude.
  - oldgradstudent 4y ago
    Of course. 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.
    - linschn 4y ago
      I am sorry, I completely missed the sarcasm. Textual communication is hard. Your imitation of hn pedantry was so good that I fell for it.
Traubenfuchs 4y ago
Does it list Jira? https://news.ycombinator.com/item?id=17689446 https://news.ycombinator.com/item?id=17689446
- gwern 4y ago
  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.)
MaxBarraclough 4y ago
Was surprised to see no mention of Langton's ant, which is somewhat like Conway's Game of Life, and was eventually shown to be Turing complete. https://en.wikipedia.org/wiki/Langton%27s_ant https://en.wikipedia.org/wiki/Langton%27s_ant

108 points by GarethX 4y ago

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.

_hl_ 4y ago
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?
- lmm 4y ago
  By that logic you might as well say a piece of paper, or this text input box, is Turing complete, since a human can execute a Turing machine on it.
  - isitmadeofglass 4y ago
    > 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.
  - Isognoviastoma 4y ago
    Notably, finite automata are Turing complete. (TM is DFA + looping).
    - tromp 4y ago
      No; TM is finite control (i.e. DFA which already have a notion of looping) + unbounded storage.
      - Isognoviastoma 4y ago
        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".
  - turboponyy 4y ago
    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.
    - edgyquant 4y ago
      That user didn’t “miss the point” and you’ve only reiterated their point that by your logic a piece of paper and pencil is “Turing complete”
      - curiousgal 4y ago
        You missed their point, a piece of paper and pencil is not making any decisions.
        posterboy 4y ago
        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?
      - linschn 4y ago
        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.
  - Avshalom 4y ago
    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.
  - thesz 4y ago
    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.
  - posterboy 4y ago
    > this text input box, is Turing complete, since a human can execute a Turing machine on it. By using Peano Axioms? Now wait a minute!
joe_the_user 4y ago
Well yeah, 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.
- tromp 4y ago
  No, because being in NP restricts computations to a polynomial number of (non-deterministic) steps.
  - joe_the_user 4y ago
    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.
lisper 4y ago
> 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.
bdowling 4y ago
The LAMBDA function in Excel can define an infinitely recursing function without using scripting. https://techcommunity.microsoft.com/t5/excel-blog/announcing-lambda-turn-excel-formulas-into-custom-functions/ba-p/1925546 https://techcommunity.microsoft.com/t5/excel-blog/announcing...
- blast 4y ago
  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?
  - unnah 4y ago
    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.
  - bdowling 4y ago
    > 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]). [0] https://en.wikipedia.org/wiki/Linear_bounded_automaton https://en.wikipedia.org/wiki/Linear_bounded_automaton

jdmoreira 4y ago

Magic the Gathering is turing complete. https://arxiv.org/abs/1904.09828 https://arxiv.org/abs/1904.09828

aidenn0 4y ago
Mentioned (and linked) in TFA
dathinab 4y ago
as mentioned in the article

e10jc 4y ago

motohagiography 4y ago

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.

scatters 4y ago
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.
saagarjha 4y ago
The interesting part there was using the Turing machine to gain the ability to set up program stare reliably for the sandbox escape.

dang 4y ago

Related: Surprisingly Turing-Complete - https://news.ycombinator.com/item?id=22839035 https://news.ycombinator.com/item?id=22839035 - April 2020 (49 comments) Surprisingly Turing-Complete - https://news.ycombinator.com/item?id=10318729 https://news.ycombinator.com/item?id=10318729 - Oct 2015 (61 comments)

deleted 4y ago

[deleted]

bdowling 4y ago

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

dysoco 4y ago

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.

oldgradstudent 4y ago

I take the strict view. 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)

linschn 4y ago
This is useless pedantry: by this metric absolutely nothing in the universe can be Turing Complete, and it's only a theoretical construct. Turing completeness is a useful tool for the analysis of actual, real life computers and their programs, despite their finitude.
- oldgradstudent 4y ago
  Of course. 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.
  - linschn 4y ago
    I am sorry, I completely missed the sarcasm. Textual communication is hard. Your imitation of hn pedantry was so good that I fell for it.

Traubenfuchs 4y ago

Does it list Jira? https://news.ycombinator.com/item?id=17689446 https://news.ycombinator.com/item?id=17689446

gwern 4y ago
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.)

MaxBarraclough 4y ago

Was surprised to see no mention of Langton's ant, which is somewhat like Conway's Game of Life, and was eventually shown to be Turing complete. https://en.wikipedia.org/wiki/Langton%27s_ant https://en.wikipedia.org/wiki/Langton%27s_ant