Hacker News Reader

Comment by kens | Hacker News Reader

The argument that the Z3 is universal "was an impressive party trick, but diverged entirely from the way the machine was designed, how it was actually used, or indeed from anything that would have made sense in the 1940s."

Source: ENIAC in Action p255.

View on HN

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

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.

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?

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.

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

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

Reply on news.ycombinator.com