3 ms·

Code might finaly look like with movfuscator (MOV on a intel processor is also turing complete).

giomasce 6y ago
No, it can't. FHE cannot emulate the whole MOV, especially the features that make it Turing-complete.
jchw 6y ago
The reason why Intel mov is so powerful is because the mnemonic actually maps to tons of different things. In particular conditionals are accomplished using indirect memory accesses.
SilasX 6y ago
Movfuscator only works because x86's MOV is like the Swiss Army knife of move instructions. It doesn't just copy bits from one location to another, but has parameters for conditionality and arithmetic, which is what allows it to be so general. That still doesn't address the parent's confusion (that I share) of how you get Turing-completeness just from addition and multiplication.
- dlubarov 6y ago
  True, but there are simpler (abstract) machines that also achieve Turing completeness: https://en.wikipedia.org/wiki/One-instruction_set_computer https://en.wikipedia.org/wiki/One-instruction_set_computer > That still doesn't address the parent's confusion (that I share) of how you get Turing-completeness just from addition and multiplication. I wouldn't say arithmetic circuits are Turing complete since they can only perform bounded computations, but we could say that they're functionally complete. It is known that boolean AND and OR gates are functionally complete, and we can reduce them to multiplication and addition in any finite field: x and y = x * y x or y = ¬(¬x and ¬y) = 1 - (1 - x)(1 - y)
  - giomasce 6y ago
    What does "functionally complete" means for you?
    - dlubarov 6y ago
      Informally, I mean reducible from time-bounded Turing machines. Given a Turing machine TM and a time bound T, a (binary or arithmetic) circuit can be constructed to simulate TM for T steps. Or in other words, a circuit can be constructed to solve any particular instance of FNTIME(T).
- rrobukef 6y ago
  You get bounded-Turing completeness. This is sufficient for all practical applications as we live in a finite universe.
cameron76 6y ago
Personal pet peeve that whenever someone brings up the movfuscator, all the responses seem to of the “well akshhhhuallly...” variety, I’ve never understood it. The responses here are generally incorrect; x86 mov does not have conditionals (that would be ccmov), cannot load the program counter, and can’t do general arithmetic beyond very standard indirect addressing ( the same forms allowed by many RISC architectures). movfuscator actually includes a version that uses only two forms of mov (a load and store form) that would work on nearly any common RISC architecture. So the assertions that “this only works because x86 mov is ___” are generally incorrect, and needlessly dismissive of an interesting idea - the addressing used by movfuscator is just addition/subtraction. Certainly at least, at a broader level, the idea that it may be desirable to reduce general computation to some extremely simple form is interesting.

No, it can't. FHE cannot emulate the whole MOV, especially the features that make it Turing-complete.

jchw 6y ago

The reason why Intel mov is so powerful is because the mnemonic actually maps to tons of different things. In particular conditionals are accomplished using indirect memory accesses.

SilasX 6y ago

Movfuscator only works because x86's MOV is like the Swiss Army knife of move instructions. It doesn't just copy bits from one location to another, but has parameters for conditionality and arithmetic, which is what allows it to be so general. That still doesn't address the parent's confusion (that I share) of how you get Turing-completeness just from addition and multiplication.

dlubarov 6y ago
True, but there are simpler (abstract) machines that also achieve Turing completeness: https://en.wikipedia.org/wiki/One-instruction_set_computer https://en.wikipedia.org/wiki/One-instruction_set_computer > That still doesn't address the parent's confusion (that I share) of how you get Turing-completeness just from addition and multiplication. I wouldn't say arithmetic circuits are Turing complete since they can only perform bounded computations, but we could say that they're functionally complete. It is known that boolean AND and OR gates are functionally complete, and we can reduce them to multiplication and addition in any finite field: x and y = x * y x or y = ¬(¬x and ¬y) = 1 - (1 - x)(1 - y)
- giomasce 6y ago
  What does "functionally complete" means for you?
  - dlubarov 6y ago
    Informally, I mean reducible from time-bounded Turing machines. Given a Turing machine TM and a time bound T, a (binary or arithmetic) circuit can be constructed to simulate TM for T steps. Or in other words, a circuit can be constructed to solve any particular instance of FNTIME(T).
rrobukef 6y ago
You get bounded-Turing completeness. This is sufficient for all practical applications as we live in a finite universe.

cameron76 6y ago

Personal pet peeve that whenever someone brings up the movfuscator, all the responses seem to of the “well akshhhhuallly...” variety, I’ve never understood it. The responses here are generally incorrect; x86 mov does not have conditionals (that would be ccmov), cannot load the program counter, and can’t do general arithmetic beyond very standard indirect addressing ( the same forms allowed by many RISC architectures). movfuscator actually includes a version that uses only two forms of mov (a load and store form) that would work on nearly any common RISC architecture. So the assertions that “this only works because x86 mov is ___” are generally incorrect, and needlessly dismissive of an interesting idea - the addressing used by movfuscator is just addition/subtraction. Certainly at least, at a broader level, the idea that it may be desirable to reduce general computation to some extremely simple form is interesting.