logoalt Hacker News

croesyesterday at 6:23 PM3 repliesview 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)


Replies

jcranmeryesterday at 6:55 PM

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.

show 2 replies
Manuel_Dyesterday at 6:39 PM

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.

kensyesterday at 6:40 PM

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

show 1 reply