Hacker News Reader

Comment by SuchAnonMuchWow | Hacker News Reader

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:

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

View on HN

You don't need jmp, a faulting mov works as well, like mov CS, eax.

https://github.com/xoreaxeaxeax/movfuscator#notes

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.

[0] https://github.com/xoreaxeaxeax/movfuscator/blob/90a49f31219...

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

From https://en.wikipedia.org/wiki/Turing_completeness

... Yes? What are you trying to say? Did you go and lookup what a Turing machine is? Or read the section entitled "Non-mathematical usage"?

You said

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

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.

What makes you say a physical computer doesn't have unbounded memory? Is it making assumptions about the real world that we have to make?

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

> And no real machine can possibly be Turing complete, because they don't have infinite memory

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.

Reply on news.ycombinator.com