If functionally complete means that any logic circuit can be constructed, doesn't this imply that IEEE-754 floating point subtraction is effectively Turing complete? (Or not?)
Turing complete is often misused to say functionally complete, either because people mistake the two or because it makes for a more appealing blog post / article:
- mov is in fact not turing complete: it needs a jmp instruction (https://harrisonwl.github.io/assets/courses/malware/spring20...)
- homomorphic encryption systems are functionally complete but not Turing complete (since looping leaks the number of operations done, break the encryption)
> It doesn't make sense to say that a bunch of operations are or are not Turing complete.
and the article’s first sentence says that a “system of rules” such as a computer’s instruction set can be Turing complete.
The article matches my understanding, which is that Turing completeness is a property describing the expressive power of a bunch of operations. You don’t need a computer with infinite memory, or even any physical computer at all, for a bunch of operations to be Turing complete.
Right, I wasn’t arguing that physical computers can be Turing machines, but instead that sets of operations can be Turing complete. There are sets of operations with which one can compose a program that perfectly simulates a Turing machine.
The problem is that physical computers cannot always run these programs accurately, due to memory constraints. But the set of operations is itself Turing complete.
That's too pedantic. A machine that has enough memory to make it indistinguishable from an infinite tape should be good enough.
> or time.
I don't think infinite time is part of the definition? If it can go step by step indefinitely, that's fine.
[0] https://github.com/xoreaxeaxeax/movfuscator/blob/90a49f31219...
> You can bulid a turing-complete machine out of NAND-gates, but to say that a NAND-game is turing-complete is like saying that you can live in a brick. You can't, but you can bulid a house out of bricks and live in that.