[HN Gopher] Subtraction is functionally complete
___________________________________________________________________
Subtraction is functionally complete
Author : orlp
Score : 184 points
Date : 2023-10-07 08:35 UTC (14 hours ago)
(HTM) web link (orlp.net)
(TXT) w3m dump (orlp.net)
| Recursing wrote:
| Reminds me of this wonderful video:
| https://www.youtube.com/watch?v=5TFDG-y-EHs , where he builds
| computation using only IEEE-754 NaN and infinity
| emilfihlman wrote:
| "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]
| jgrahamc wrote:
| You've missed the word "different". Your examples talk about
| the same sign.
| emilfihlman wrote:
| Direct 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 wrote:
| > 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 wrote:
| Direct 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 wrote:
| > Direct 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.
|
| The first sentence is referring to _addition_ , with
| _addends_ , not subtraction. x - y is not an addition, it
| is a subtraction, so the first sentence does not directly
| apply. It _does_ apply however if you treat x - y as the
| sum x + (-y), which the second sentence clarifies.
|
| In other words, the first sentence applies directly to
| additions, and applies to subtractions if you flip the sign
| of the second argument. The second sentence applies to
| subtractions directly without any sign flips, but obviously
| does not apply to additions.
|
| > 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.
|
| No, x=-3 and y=-6 both have the same sign, they're both
| negative.
| [deleted]
| AgentOrange1234 wrote:
| Cute. 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 wrote:
| This 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 wrote:
| Kind of like https://github.com/xoreaxeaxeax/movfuscator
| [deleted]
| LukeShu wrote:
| You may be interested in
|
| - Using IEEE floating-point error for ML transfer functions
| http://tom7.org/grad/
|
| - Using IEEE NaN and infinity to build logic gates and a whole
| CPU http://tom7.org/nand/
| bakuninsbart wrote:
| Second one is possibly my favourite YouTube video of all
| time.
| kibwen wrote:
| I'm certain that at least 20% of all the people who clicked
| on this comments section did so specifically to post this
| link.
| teaearlgraycold wrote:
| One day as we were getting coffee a coworker just casually
| drops that his buddy from school made some programs called
| learnfun and playfun for a YouTube video (which is my
| favorite Tom7 video). Tech is a surprisingly small world.
| RagnarD wrote:
| 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?)
| Epa095 wrote:
| 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.
| SuchAnonMuchWow wrote:
| 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/malwar
| e/spring20...)
|
| - homomorphic encryption systems are functionally complete but
| not Turing complete (since looping leaks the number of
| operations done, break the encryption)
| uxp8u61q wrote:
| 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.
| kweingar wrote:
| > 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
| Scarblac wrote:
| 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.
| uxp8u61q wrote:
| ... 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"?
| gdprrrr wrote:
| You don't need jmp, a faulting mov works as well, like mov
| CS, eax.
|
| https://github.com/xoreaxeaxeax/movfuscator#notes
| mmarx wrote:
| From the truth table, subtraction is clearly truth-preserving, so
| it cannot actually be functionally complete. What am I missing?
| johnday wrote:
| Subtraction 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 wrote:
| The sign bit is the only bit involved here. What "subtractive
| bits" are you referring to?
| Epa095 wrote:
| I 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
| Joker_vD wrote:
| Truth-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).
| stavros wrote:
| What does "truth-preserving" mean in this context? That it will
| never produce false if either of the arguments is true?
| gliptic wrote:
| Why would truth preservation prevent it from being functionally
| complete? How can you even tell a truth table is truth
| preserving? A truth table is not a logical argument.
| danbruc wrote:
| Truth-preserving in this context means that the function
| value is true if all function arguments are true. If you only
| have truth-preserving functions available, then you can not
| output false if all inputs are true, hence you can not build
| all possible functions. An analog argument applies to
| falsehood-preserving functions.
| gliptic wrote:
| I see. I wasn't familiar with that term in this context,
| thanks.
| tromp wrote:
| Below the truth table for implication (with arguments reversed)
| they claim
|
| > It turns out this truth table is functionally complete [1]
|
| yet the linked Wikipedia article clearly states that
|
| > every two-element set of connectives containing NOT and one
| of { AND, OR, IMPLY } is a minimal functionally complete subset
| of { NOT, AND, OR, IMPLY, IFF }. I.e. IMPLY by itself is not
| functionally complete.
|
| [1] https://en.wikipedia.org/wiki/Functional_completeness
| Epa095 wrote:
| The article kind of took for granted that you could include
| the number 0 as well, and with "-0" he got bottom, so its the
| 2-element set {-->, _|_}.
| gliptic wrote:
| The unstated assumption is that you also have FALSE.
| orlp wrote:
| To be entirely precise, it is functionally complete in
| combination with access to the constant false (-0.0). If not
| given access to this constant it is not functionally complete,
| unlike e.g. NAND which can produce false from any value. I
| shall clarify that in the article.
|
| The point of the article was more to illustrate that using
| nothing but signed zeros and floating point subtraction you can
| simulate arbitrary circuits, and 'functionally complete' was
| the most concise term for that I could think of, even if it is
| bending the rules a little bit when strictly looking at the
| truth table.
| codeflo wrote:
| It's a matter of definitions, but it always bothered me that
| functional completeness is defined so that it only requires
| the ability to produce any _non-nullary_ function, not any
| function including nullary ones. That is, the set { NAND } is
| considered functionally complete, even though it can only
| produce a function that maps any input x to TRUE, and can 't
| produce the value TRUE itself. As soon as you care about
| constants, which I think you should, { NAND, FALSE } or
| whatever isn't any more magical than { AND, NOT } or { XOR,
| TRUE }.
| thaumasiotes wrote:
| > { NAND } is considered functionally complete, even though
| it can only produce a function that maps any input x to
| TRUE, and can't produce the value TRUE itself.
|
| When you're reducing formulas, those are the same thing.
| p p [?] !p p !p [?] 1 !1 [?] 0
|
| So then you're happy to say (p (p p))
| (p (p p)) [?] (p !p) (p !p)
| [?] 1 1 [?] 0
|
| The expression "(p (p p)) (p (p p))" is just a
| particularly longwinded name for the constant "0".
|
| I don't see why you're comparing {NAND, FALSE} to {AND,
| NOT} - how do you produce TRUE from {AND, NOT} by a
| standard that {NAND} by itself doesn't also meet? The
| normal way to produce TRUE from {AND, NOT} is
| NOT (p AND (NOT p))
|
| but you seem to have already rejected that?
| codeflo wrote:
| Yeah, listing {AND, NOT} was a mistake -- you're right,
| you do need a constant.
|
| My problem with p !p [?] 1 is simply that you need some
| (arbitrary) value p from somewhere. It's not 1, it's a
| unary function that returns 1. That just bothers me.
| deadbeeves wrote:
| When I'm aiming for elegance, I like to define NAND as an
| N-ary function:
|
| nand() = false
|
| nand(x, ...) = !(x && !nand(...))
|
| That eliminates the problem of needing arbitrary
| constants.
| danbruc wrote:
| If you want to be able to implement nullary functions, then
| you need a nullary function to begin with. You are not
| really implementing anything besides maybe negating the
| constant you got. You would also have to extend { AND, NOT
| } with a constant. The best you could do would change from
| one binary function to one binary function and a constant.
| pwdisswordfishc wrote:
| So { -: F2 - F } is not functionally complete, but { -: F2 -
| F, -0: F0 - F } is.
| p4bl0 wrote:
| Hey, not related to the post but since you're here: your
| domain name has an AAAA IPv6 record but the server doesn't
| respond to IPv6 requests. The problem most probably is that
| the web server is not binded to the IPv6 address of the
| system.
| orlp wrote:
| Thanks for letting me know. I just double-checked and the
| AAAA IPv6 record does have the right IP, port 80 is open in
| the VPS firewall for both IPv4 and v6 and my nginx config
| does listen on both as well: listen 80;
| listen [::]:80;
|
| I'm by no means a networking expert, so I'm a bit puzzled.
| I'll investigate more in a couple of days, not particularly
| excited to mess with the system while serving a post on the
| front page.
| p4bl0 wrote:
| That's the HTTP config, but the website is served over
| HTTPS and the HTTP version redirects to it. My bet would
| be that the HTTPS settings does not bind to IPv6.
|
| Do you have: listen [::]:443 ssl;
|
| somewhere in the server {} block where the certificate is
| declared?
|
| My mobile phone carrier uses IPv6 so I cannot access your
| website from my phone (except if I connect to a wifi
| network that uses IPv4).
| orlp wrote:
| Yep, I have listen [::]:443 ssl;
| listen 443 ssl;
|
| in the server block.
| p4bl0 wrote:
| Maybe the second line should be "listen 443 ssl;"
| (without the colon, like in the non-HTTPS version)?
| That's how it is in my config.
|
| EDIT: orlp updated their comment above, this one is not
| relevant anymore.
| orlp wrote:
| > Maybe the second line should be "listen 443 ssl;"
| (without the colon, like in the non-HTTPS version)?
| That's how it is in my config.
|
| That's a clerical error while copying to Hacker News, it
| is without the colon in my config as well. I've edited
| the post.
|
| I think I figured it out, Hetzner lists
| 2a01:4f8:c012:175e::/64 as the IPv6 for my VPS, so I put
| 2a01:4f8:c012:175e:: in the DNS record. However it seems
| it only actually listens on 2a01:4f8:c012:175e::1.
| Probably just me being an idiot and fundamentally
| misunderstanding how IPv6 addresses work. I've updated
| it, although it will probably take some time before the
| DNS cache refreshes.
| MayeulC wrote:
| > Hetzner lists 2a01:4f8:c012:175e::/64 as the IPv6 for
| my VPS
|
| Yup, that's the address prefix, 64 bit long as indicated
| by the /64. Your VPS can therefore be configured with
| 2^(128-64)=2^64 IP addresses, as long as they start with
| that prefix.
|
| The actual IP is chosen by your VPS itself, so I guess it
| has assigned itself prefix::1. You can see that address
| with `ip -6 a`. And add new ones if you want: `ip -6
| address add 2a01:4f8:c012:175e::2 dev yournetworkcard0`.
| You can technically add one IP address per service and
| bypass the reverse proxy by having the services listen on
| their dedicated IPs. That makes it easy to migrate
| services to another host (change the AAAA record).
| p4bl0 wrote:
| It works! :)
| mmarx wrote:
| Ah, thanks, that was indeed what I was missing.
| dzaima wrote:
| Somewhat related:
| 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 wrote:
| > integer implementation done in software, using only floating
| point ops
|
| so basically any attempt to use JavaScript 's number as int
| DonHopkins wrote:
| Why did it take mathematicians and logicians so long to figure
| out their differences?
| bitwize wrote:
| Reminds me of how a single instruction -- "subtract and branch if
| negative" -- is Turing complete.
| Izkata wrote:
| Abuse 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/
| dweekly wrote:
| A 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_Ref...
| [deleted]
___________________________________________________________________
(page generated 2023-10-07 23:00 UTC)