4 ms·

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 s

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

_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