Hacker News Reader

Comment by croes | Hacker News Reader

> Nevertheless, the Z3 was Turing-complete – how to implement a universal Turing machine on the Z3 was shown in 1998 by Raúl Rojas.

https://en.wikipedia.org/wiki/Z3_(computer)

View on HN

The Z3 lacked conditional branching. The hack to make it technically a universal Turing machine is to execute all possible branches of a program and discard the undesired branch results, so the end result is the same as if it had genuine branching abilities. But of course that'd drastically drive up the computation time if you actually tried to use the machine in that way.

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.

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

> 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.

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

Yes, even Rojas says, "From a practical perspective, and in the way the Z3 was really programmed, it was not equivalent to modern computers." https://www.researchgate.net/publication/3330654_How_to_make...

Who said it has to be equivalent to modern computers?

Reply on news.ycombinator.com