3 ms·

To further push the point that many things are Turing complete and that it should not be seen as synonymous with complex, Gwern has a nice list of Surprisingly

To further push the point that many things are Turing complete and that it should not be seen as synonymous with complex, Gwern has a nice list of Surprisingly Turing complete things [0] that includes Peano Arithmetic, Pokemon Yellow and Magic the Gathering. I personally find lists of programming language that made the conscious decision to not be Turing complete (such as Coq the theorem prover) more intriguing. [0]: https://www.gwern.net/Turing-complete https://www.gwern.net/Turing-complete

dragontamer 6y ago
> To further push the point that many things are Turing complete and that it should not be seen as synonymous with complex, Gwern has a nice list of Surprisingly Turing complete things [0] that includes Peano Arithmetic, Pokemon Yellow and Magic the Gathering. If you know how to reach Turing completeness in those systems, you wouldn't call any of those "simple". MtG for instance is considered one of the more complicated card games. Pokemon Yellow's turing completeness proof involved arbitrary code execution by swapping memory locations around. Peano axioms / Arithmetic underlies an entire theory of abstract mathematics. --------------- EDIT: I think decidable is an important attribute of systems that are weaker than Turing Complete. There are still very powerful decidable equations (ex: 3SAT, most famously), which has an answer (either satisfiable, or unsatisfiable), but may need O(2^n) time (or longer) to calculate the result. Turing Complete is only semi-decidable: if something halts it will halt in finite time. If something won't halt, you'll never know.
- nestorD 6y ago
  While I do agree for MtG and Pokemon Yellow (their main value as examples is that they are fun and inexpected), Peano arithmetic is simple. It is fondamental but still probably the simplest way to implement natural integers : a natural number is either 0 or one plus a number.
  - dragontamer 6y ago
    The general thing about complexity (be it 3SAT or Turing Completeness) is that the underlying rules are extremely simple. The issue is understanding the implications of those rules. For something like 3SAT, all possible 3SAT puzzles can be solved (aka: either satisfied with an example, or unsatisfied with a "certificate of unsatisfiability"). For problems in the Turing Complete complexity class, the "implications" of the rules you list are semi-decidable. Ex: Is there an odd-perfect number (https://en.wikipedia.org/wiki/Perfect_number https://en.wikipedia.org/wiki/Perfect_number)? Well, all we gotta do is try all numbers. Once we find an odd perfect number, we'll know its possible. But if we never find an odd perfect number, we remain in a state of uncertainty. Though I guess, a future mathematical proof may prove if an odd perfect number exists or not. So I guess I'm back to the halting theorem as an example. For the halting-theorem: you can "solve" any computer by simply executing the program and waiting for it to end. If it ends, you know its a program that ends. If it doesn't end... well... semi-decidable. You don't know that it never ends. ------------- Anyway, if a hypothetical type-system were "only as powerful as 3SAT", then all calculations under that type system would be proven to come to a solution eventually. EDIT: And even weaker systems, such as "Horn-clause Logic", (which is the basis for Prolog programming language) can have further proofs of efficiency (not only will all systems come to a solution eventually, but we have strong proofs about the number of steps a computer will take to reach that solution). These attributes are likely useful to elements of programming language design. Sure, we are making a Turing complete language (aka: machine code). But that doesn't mean that all sub-languages in the language need to also be Turing complete. Imagine if "printf" or "scanf" was Turing complete, it'd be a complexity nightmare!!

dragontamer 6y ago

> To further push the point that many things are Turing complete and that it should not be seen as synonymous with complex, Gwern has a nice list of Surprisingly Turing complete things [0] that includes Peano Arithmetic, Pokemon Yellow and Magic the Gathering. If you know how to reach Turing completeness in those systems, you wouldn't call any of those "simple". MtG for instance is considered one of the more complicated card games. Pokemon Yellow's turing completeness proof involved arbitrary code execution by swapping memory locations around. Peano axioms / Arithmetic underlies an entire theory of abstract mathematics. --------------- EDIT: I think decidable is an important attribute of systems that are weaker than Turing Complete. There are still very powerful decidable equations (ex: 3SAT, most famously), which has an answer (either satisfiable, or unsatisfiable), but may need O(2^n) time (or longer) to calculate the result. Turing Complete is only semi-decidable: if something halts it will halt in finite time. If something won't halt, you'll never know.

nestorD 6y ago
While I do agree for MtG and Pokemon Yellow (their main value as examples is that they are fun and inexpected), Peano arithmetic is simple. It is fondamental but still probably the simplest way to implement natural integers : a natural number is either 0 or one plus a number.
- dragontamer 6y ago
  The general thing about complexity (be it 3SAT or Turing Completeness) is that the underlying rules are extremely simple. The issue is understanding the implications of those rules. For something like 3SAT, all possible 3SAT puzzles can be solved (aka: either satisfied with an example, or unsatisfied with a "certificate of unsatisfiability"). For problems in the Turing Complete complexity class, the "implications" of the rules you list are semi-decidable. Ex: Is there an odd-perfect number (https://en.wikipedia.org/wiki/Perfect_number https://en.wikipedia.org/wiki/Perfect_number)? Well, all we gotta do is try all numbers. Once we find an odd perfect number, we'll know its possible. But if we never find an odd perfect number, we remain in a state of uncertainty. Though I guess, a future mathematical proof may prove if an odd perfect number exists or not. So I guess I'm back to the halting theorem as an example. For the halting-theorem: you can "solve" any computer by simply executing the program and waiting for it to end. If it ends, you know its a program that ends. If it doesn't end... well... semi-decidable. You don't know that it never ends. ------------- Anyway, if a hypothetical type-system were "only as powerful as 3SAT", then all calculations under that type system would be proven to come to a solution eventually. EDIT: And even weaker systems, such as "Horn-clause Logic", (which is the basis for Prolog programming language) can have further proofs of efficiency (not only will all systems come to a solution eventually, but we have strong proofs about the number of steps a computer will take to reach that solution). These attributes are likely useful to elements of programming language design. Sure, we are making a Turing complete language (aka: machine code). But that doesn't mean that all sub-languages in the language need to also be Turing complete. Imagine if "printf" or "scanf" was Turing complete, it'd be a complexity nightmare!!