Birthday
Happy birthday to BookFinder.com.
Support Bloggers' Rights!
My mom says that the "Forgotten New York" web site shows what I looked at when I was a baby (note, not what I looked like): Hunts Lane in Brooklyn.
Darn, after I said that the comedian made my week with his comment about liking bagels, Peter Junger goes and makes my week again:
It's not so much a matter of believing them as estopping them.
Mary Gardiner has a new policy for her diary. (I've never tried writing a diary policy; maybe I should create a List of the Terms of Service Under Which this Content is Provided to You.) The problem she mentions is an interesting one. I remember that Phil Agre was very unhappy about the Wayback Machine when I mentioned it to him. People who have been Internet users for a long time will be surprised, perhaps unpleasantly, when other people start to learn "ancient history" about their beliefs, activities, or lives.
I decided to draft a Terms of Service for the use of this diary. What do you think?
If I keep reading boing boing, I will have no free time left at all. But Google is having a programming contest where you can get a chance to win the use of your program on the actual Google archive.
Wednesday, on my way to work, I proved that n-input NAND is universal and also that n-input NOR is universal.
Given an n-input NAND, use NAND(x,x,x,...) to get NOT(x). Now use NOT(NAND(a,b,c,...)) to get n-input AND, and NAND(NOT(a,b,c,...)) to get n-input OR. You can get 1 and 0 in various ways, including NAND(x,x,x,...,NOT(x)) or AND(x,x,x,...,NOT(x)). You can get 2-input AND via AND(a,b,1,1,1...), and 2-input OR via OR(a,b,0,0,0,...). With two-input AND, two-input OR, NOT, and n-input AND, it's straightforward to implement any truth table by brute force.
You just write a sum of products, which is to say you start with an enclosing OR (you can get a 2^n input OR by cascading n-input ORs and applying 1 to any unused inputs), and apply it to a series of terms, each of which is an n-input AND which produces a 1 if and only if a condition corresponding to a particular truth table row is met.
For example, with two-input NAND, the brute force implementation of XOR, which has the truth table
A B result
-----------
0 0 0 ("AND(NOT(A), NOT(B))")
0 1 1 ("AND(NOT(A), B)")
1 0 1 ("AND(A, NOT(B)")
0 0 0 ("AND(A, B)")
will be OR(AND(NOT(A), B), AND(A, NOT(B))). This kind of synthesis should be familiar to anyone who has ever done synthesis from a truth table using AND and OR gates.
The brute force implementation of three-input XOR with three-input gates looks like
A B C result
-------------
0 0 0 0 ("AND(NOT(A), NOT(B), NOT(C))")
0 0 1 1 ("AND(NOT(A), NOT(B), C)")
0 1 0 1 ("AND(NOT(A), B, NOT(C))")
0 1 1 0 ("AND(NOT(A), B, C)")
1 0 0 1 ("AND(A, NOT(B), NOT(C))")
1 0 1 0 ("AND(A, NOT(B), C)")
1 1 0 0 ("AND(A, B, NOT(C))")
1 1 1 1 ("AND(A, B, C)")
or OR(AND(NOT(A), NOT(B), C), AND(NOT(A), B, NOT(C)), AND(A, NOT(B), NOT(C)), AND(A, B, C)).
Interestingly, three-input XOR is not universal, because it can be implemented with two-input XOR, and two-input XOR is not universal for two inputs, let alone for three. So we have two examples of gates which are always universal, when scaled up to any size, and two examples of gates which are never universal. (Actually, n-input AND and n-input OR are also not universal. Neither can produce even a single-input NOT.)
Oh, I left out the proof that n-input NOR is universal. OK, if you do NOR(x,x,x,..), you get NOT, and then you use that to get OR, and then you use that to get AND, and you're back in exactly the situation you had with NAND. That's not surprising.
Jim Tyre pointed out what happens if you sue yourself (in case you've ever wondered).
We have considered whether respondent/defendant/beneficiary should be awarded his costs of suit on appeal, which he could thereafter recover from himself. However, we believe the equities are better served by requiring each party to bear his own costs on appeal.The judgment (order) is affirmed. Each party shall bear his own costs.
Oreste Lodi v. Oreste Lodi, 173 Cal.App.3d 628 (1985).
Contact: Seth David Schoen