Hacker News Reader

Comment by mmarx | Hacker News Reader

From the truth table, subtraction is clearly truth-preserving, so it cannot actually be functionally complete. What am I missing?

View on HN

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.

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

> { 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?

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.

> It’s not 1, it’s a unary function that returns 1.

How do you know it's a unary function? For all you know, the function in question is f(p,q,r,s,t) = p 🡑 ¬p.

In fact it's a nullary function, because you don't need any input. There is no difference between the functions f(p,q,r,s,t) = p 🡑 ¬p and f(p,q,r,s,t) = r 🡑 ¬r. They have exactly the same behavior in every respect. And for the same reason, there is also no difference between those functions and the functions f(p) = p 🡑 ¬p, f(q) = p 🡑 ¬p [sic], and f() = p 🡑 ¬p.

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.

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.

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.

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.

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

Yep, I have

    listen [::]:443 ssl;
    listen 443 ssl;

in the server block.

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.

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

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

It works! :)

This has got to the most HN comment I've ever read. I love this site

So { −: F² → F } is not functionally complete, but { −: F² → F, −0: F⁰ → F } is.

Ah, thanks, that was indeed what I was missing.

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

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

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)

The sign bit is the only bit involved here. What "subtractive bits" are you referring to?

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

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 {-->, _|_}.

The unstated assumption is that you also have FALSE.

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.

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.

I see. I wasn't familiar with that term in this context, thanks.

What does "truth-preserving" mean in this context? That it will never produce false if either of the arguments is true?

Reply on news.ycombinator.com