Remix.run Logo
jcranmer 2 days ago

One of the things about Turing-completeness is that it is very easy to become accidentally Turing-complete, since the conditions you need for completeness are very weak. (Famously, C++ template instantiation is unintentionally Turing-complete).

Z3 is an example of an accidentally Turing-complete machine.

tengwar2 2 days ago | parent | next [-]

With the important exception of "infinite tape". That always gets forgotten.

embedding-shape 2 days ago | parent | prev [-]

> Z3 is an example of an accidentally Turing-complete machine.

Kind of easy to let that pass though, given the "imitation game" wasn't even introduced by Turing until way after the Z3 machine was completed.

layer8 2 days ago | parent [-]

The imitation game (aka Turing test) has nothing to do with Turing completeness.