6 ms·

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

• 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!