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?)
No, functionally complete is mussing the looping functionality to be Turing complete.
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:
- homomorphic encryption systems are functionally complete but not Turing complete (since looping leaks the number of operations done, break the encryption)
However, the movfuscator as implemented does still require a sigaction(2) syscall (via an INT 0x80 or similar) to set up a signal handler, under the justification that "it is not actually part of the program" and that "if we were in ring 0, we wouldn't need help from the kernel" [0]. The latter part seems a little dubious to me: without the help of the bootloader running non-MOV instructions, you'd never be able to escape from 16-bit real mode into 32-bit protected mode, since you wouldn't be able to load a valid GDT with the LGDT instruction.
You also need an infinite memory to be called "Turing complete". It doesn't make sense to say that a bunch of operations are or are not Turing complete. It's a property of a whole machine, not just a set of operations. And no real machine can possibly be Turing complete, because they don't have infinite memory or time.
> In computability theory, a system of data-manipulation rules (such as a model of computation, a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Turing machine (devised by English mathematician and computer scientist Alan Turing).
And Turing machines have unbounded memory. That's usually ignored when talking about Turing completeness, but it's nevertheless true that physical computers cannot simulate all Turing machines.
> it's nevertheless true that physical computers cannot simulate all Turing machines
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.
> 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.
To quote someone from reddit (substitute NAND gates with subtraction)
> 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.
