7 ms·
Subtraction is functionally complete
- RagnarD 3y agoIf 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?)
- Epa095 3y agoTo 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.
- SuchAnonMuchWow 3y agoNo, 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/spring2017/papers/mov-is-turing-complete.pdf 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)
- uxp8u61q 3y agoYou 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.
- kweingar 3y ago> 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 https://en.wikipedia.org/wiki/Turing_completeness
- uxp8u61q 3y ago... 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"?
- kweingar 3y agoYou 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.
- Scarblac 3y agoAnd 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.
- Dylan16807 3y agoWhat makes you say a physical computer doesn't have unbounded memory? Is it making assumptions about the real world that we have to make?
- kweingar 3y ago
- gdprrrr 3y agoYou don't need jmp, a faulting mov works as well, like mov CS, eax. https://github.com/xoreaxeaxeax/movfuscator#notes https://github.com/xoreaxeaxeax/movfuscator#notes
- LegionMammal978 3y agoHowever, 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/90a49f312199a34075da0cc59c995e9ede642b8a/movfuscator/movfuscator.c#L2785 https://github.com/xoreaxeaxeax/movfuscator/blob/90a49f31219...
- bsder 3y agoClose. "Subtract and branch if less than or equal to zero" is single instruction Turing complete. https://en.wikipedia.org/wiki/One-instruction_set_computer https://en.wikipedia.org/wiki/One-instruction_set_computer
- mmarx 3y agoFrom the truth table, subtraction is clearly truth-preserving, so it cannot actually be functionally complete. What am I missing?
- johnday 3y agoSubtraction is truth preserving on the sign bit. It's not truth-preserving in the actual subtractive bits. (I disagree with their claim that the subtractive bit is functionally complete on its own - you're right, since it's truth-preserving, it clearly is not functionally complete)
- gliptic 3y agoThe sign bit is the only bit involved here. What "subtractive bits" are you referring to?
- Epa095 3y agoI dont really know what you mean by truth-preserving here, but maybe a hint is thats its not ONLY subtraction which is functionally complete, it's subtraction and the constant symbol 0. From subtraction and 0 he makes false (as -0.0), and then he has the functionally complete set found in wikipedia [1] as {->, _|_ } (my attempt at rendering rightarrow and bottom). 1: https://en.wikipedia.org/wiki/Functional_completeness https://en.wikipedia.org/wiki/Functional_completeness
- Joker_vD 3y agoTruth-preserving means that it maps T to T. In fact, the Wikipedia's article you link to has Post's theorem about five Post's classes of Boolean functions with all of their definitions: monotonic, affine (which has a funny definition in this article: I was taught the definiton via ANF, "is just a XOR of (some) of variables"), self-dual, truth- and false-preserving. They're all closed but functionally incomplete (in fact, they're functionally pre-complete: adding any single function outside of a class to that class produces a functionally complete set, — and there are no other pre-complete classes).
- 3y ago
- Recursing 3y agoReminds me of this wonderful video: https://www.youtube.com/watch?v=5TFDG-y-EHs https://www.youtube.com/watch?v=5TFDG-y-EHs , where he builds computation using only IEEE-754 NaN and infinity
- caseyohara 3y agoThat whole channel (suckerpinch / Tom 7) is incredible. Extremely nerdy, thoughtful and funny content, and I just love his delivery. I cannot recommend it enough, especially to the HN crowd.
- DonHopkins 3y agoWhy did it take mathematicians and logicians so long to figure out their differences?
- deleted 3y ago[deleted]
- emilfihlman 3y ago"If both of the addends have the same sign, the output must have that sign. However, for x−y that means if x and y have different signs the output must have the sign of x." This is trivially wrong, or mixing two different meanings of "signs". Given variables x and y with values 5 and 10, ie both having the same positive sign, x-y will produce a result -5, that has negative sign. Even if we assume that the sign of the y variable is actually inverted, it's still trivial by choosing say -3 and -6, the latter which has now inverted to 6, and the result is +3, which has different sign than x.
- deleted 3y ago[deleted]
- jgrahamc 3y agoYou’ve missed the word “different”. Your examples talk about the same sign.
- emilfihlman 3y agoDirect your attention to the first line "If both of the addends have the same sign, the output must have that sign" This is absolutely not true, as already shown. x=5 y=10 z=x-y=-5, which has different sign from x. If we assume sign of y inverts because of the operation, then direct your attention to the second line "However, for x−y that means if x and y have different signs the output must have the sign of x" x=-3 y=-6=>6 these now have different sign, so result should have sign of x, but z=x+y=3, which again has different sign from x.
- orlp 3y ago> Given variables x and y with values 5 and 10, ie both having the same positive sign, x-y will produce a result -5, that has negative sign. If x and y both have a positive sign the condition "for x−y that means if x and y have different signs" is not met. With -3 and -6, again, x and y both have the same sign and the condition is not met for subtraction.
- emilfihlman 3y ago
- AgentOrange1234 3y agoCute. Next steps? If you fill out your soft-hardware instruction set in the straightforward way, you could rig up a compiler to target it. (There’s probably no practical use beyond obfuscation like hiding malware from decompilers.)
- jeroenhd 3y agoThis is the kind of weird (ab)use of floating point instructions that I can imagine some DRM solution using as a means to obfuscate a VM of some kind. The next step would be to use these properties to write a compiler to run normal source code as floating point integers, maybe with some kind of FFI to call regular OS APIs.
- legobmw99 3y agoKind of like https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator
- bonzini 3y agoA lot more like https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-into-nso-zero-click.html https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-i... The mov trick is akin to OISC, the "one instruction set computer". Here instead it's building logic circuits.
- deleted 3y ago[deleted]
- LukeShu 3y agoYou may be interested in - Using IEEE floating-point error for ML transfer functions http://tom7.org/grad/ http://tom7.org/grad/ - Using IEEE NaN and infinity to build logic gates and a whole CPU http://tom7.org/nand/ http://tom7.org/nand/
- bakuninsbart 3y agoSecond one is possibly my favourite YouTube video of all time.
- kibwen 3y agoI'm certain that at least 20% of all the people who clicked on this comments section did so specifically to post this link.
- dzaima 3y agoSomewhat related: https://dougallj.wordpress.com/2020/05/10/bitwise-conversion-of-doubles-using-only-floating-point-multiplication-and-addition/ https://dougallj.wordpress.com/2020/05/10/bitwise-conversion... That implements conversion from an IEEE-754 double to a pair of two such doubles whose values are integers of the low and high 32 bits of the bitwise representation of the argument double, implemented only with double add/sub/mul.
- valyagolev 3y ago> integer implementation done in software, using only floating point ops so basically any attempt to use JavaScript 's number as int
- deleted 3y ago[deleted]
- Izkata 3y agoAbuse of the sign bit in similar ways was a major clue that a true AI was loose in the wild in the short story Coding Machines. https://www.teamten.com/lawrence/writings/coding-machines/ https://www.teamten.com/lawrence/writings/coding-machines/
- dweekly 3y agoA wonderful story, though the concept was clearly heavily borrowed from Ken Thompson's classic On Trusting Trust: https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...
- bitwize 3y agoReminds me of how a single instruction -- "subtract and branch if negative" -- is Turing complete.
- xXx_uwu_xXx 3y agoThe post uses <del> instead of <s>. Is this not wrong? IMO it is. Off-topic? Perhaps but oh-so-very important.
- khangaroo 3y agoI posted this on the thread in /r/programming a while ago, but I might as well post this here too. It's possible to implement the adder in "only" 11 subtractions: fn adder(a: Bit, b: Bit, c: Bit) -> (Bit, Bit) { let r0 = c - b; let r1 = c - r0; let r2 = ZERO - r0; let r3 = b - r1; let r4 = r2 - r3; let r5 = a - r4; let r6 = r4 - a; let r7 = ZERO - r5; let r8 = r7 - r1; let r9 = r7 - r6; let r10 = ZERO - r8; (r9, r10) }
- MauranKilom 3y agoSo can you implement soft floating point math in soft integer math in floating point math?