Subtraction is functionally complete
orlp.net
orlp.net
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.
The mov trick is akin to OISC, the "one instruction set computer". Here instead it's building logic circuits.
- 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/
This is a proof by construction that the Intel MMU's fault handling mechanism is Turing complete. We have constructed an assembler that translates 'Move, Branch if Zero, Decrement' instructions to C source that sets up various processor control tables. After this code has executed, the CPU computes by attempting to fault without ever executing a single instruction. Optionally, the assembler can also generate X86 instructions that will display variables in the VGA frame buffer and will cause control to be transferred between the native (display) instructions and 'weird machine' trap instructions.
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.
(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)
> 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.
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.
When you're reducing formulas, those are the same thing.
p 🡑 p ≡ ¬p
p 🡑 ¬p ≡ 1
¬1 ≡ 0
(p 🡑 (p 🡑 p)) 🡑 (p 🡑 (p 🡑 p)) ≡ (p 🡑 ¬p) 🡑 (p 🡑 ¬p)
≡ 1 🡑 1
≡ 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))
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.
nand() = false
nand(x, ...) = !(x && !nand(...))
That eliminates the problem of needing arbitrary constants.
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.
listen 80;
listen [::]:80;
Do you have:
listen [::]:443 ssl;
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).
listen [::]:443 ssl;
listen 443 ssl;
EDIT: orlp updated their comment above, this one is not relevant anymore.
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.
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).
> 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.
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)
> 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.
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.
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.
[0] https://github.com/xoreaxeaxeax/movfuscator/blob/90a49f31219...
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)
}so basically any attempt to use JavaScript 's number as int
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.
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.
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.
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.
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.