> A programming language being Turing-complete isn't really news, it's... the main point, unless you are intentionally trying to avoid being Turing-complete.
For example, Bitcoin "smart contracts" are intentionally not Turing-complete, and there are not per-opcode costs like there are for EVM and eWASM (which are embedded in other programs than Ethereum)
> A key part of the proof is a mathematical definition of a computer and program, which is known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first cases of decision problems proven to be unsolvable. This proof is significant to practical computing efforts, defining a class of applications which no programming invention can possibly perform perfectly.
> [...] any quantum algorithm can be expressed formally as a particular quantum Turing machine. However, the computationally equivalent quantum circuit is a more common model.[1][2]
> History: [2005] A quantum Turing machine with postselection was defined by Scott Aaronson, who showed that the class of polynomial time on such a machine (PostBQP) is equal to the classical complexity class PP.
When I read the title, I too assumed it was about dialectical chatbots and - having just read turtledemo.chaos - wondered whether there's divergence and potentially infinite monkeys and then emergence of a reverse shell to another layer of indirection; turtles all the way down w/ emergence.
For example, Bitcoin "smart contracts" are intentionally not Turing-complete, and there are not per-opcode costs like there are for EVM and eWASM (which are embedded in other programs than Ethereum)
"The Cha Cha Slide Is Turing Complete" https://news.ycombinator.com/item?id=32477593 :
> Turing completeness: https://en.wikipedia.org/wiki/Turing_completeness
> Church-Turing thesis: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
Halting problem: https://en.wikipedia.org/wiki/Halting_problem :
> A key part of the proof is a mathematical definition of a computer and program, which is known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first cases of decision problems proven to be unsolvable. This proof is significant to practical computing efforts, defining a class of applications which no programming invention can possibly perform perfectly.
Quantum Turing machine > History: https://en.wikipedia.org/wiki/Quantum_Turing_machine :
> [...] any quantum algorithm can be expressed formally as a particular quantum Turing machine. However, the computationally equivalent quantum circuit is a more common model.[1][2]
> History: [2005] A quantum Turing machine with postselection was defined by Scott Aaronson, who showed that the class of polynomial time on such a machine (PostBQP) is equal to the classical complexity class PP.
Complexity Zoo > Petting Zoo > {P, NP, PP,}, Modeling Computation > Deterministic Turing Machine https://complexityzoo.net/Petting_Zoo#Deterministic_Turing_M...
-
When I read the title, I too assumed it was about dialectical chatbots and - having just read turtledemo.chaos - wondered whether there's divergence and potentially infinite monkeys and then emergence of a reverse shell to another layer of indirection; turtles all the way down w/ emergence.