August 2010
First Bible Test
08/29/10 02:50 PM Filed in: Proud Father  Christianity
My daughter received a 100% on her first Bible quiz at school this week. I persuaded her to let me take the test. I didn’t do as well. My excuse is that I couldn’t read what she scanned in  the resolution was too low. In any case, she said the hardest question was #5:
The right answer is “e”. Rachel said, “This question was the one most people in class missed (majority put C). He even told us before the quiz that the devil didn't make Eve do it.” Now, 2 Cor 11:3 says, “But I am afraid that as the serpent deceived Eve by its cunning...”. So Eve was deceived. But 1 Tim 2:14 says, “...Adam was not deceived, but the woman was deceived...” This rules out “c”. The professors admonition ruled out “b”.
Genesis 3:6 says, in part, “So when the woman saw that the tree was good for food...”. The interesting question is, “How did Eve know something was good before eating of the fruit which would give that knowledge?” A typical answer is that Eve determined that the fruit was edible, i.e., “good for food” and that this is somehow different from “morally good.” But this betrays a misunderstanding of the mental machinery by which we determine value.
I’ve asked Rachel to inquire of her teacher to see what he says about this.
The first sin was the eating of the forbidden fruit. Which of the following best describes the fundamental motive for Adam and Eve’s disobedience? Mark one.

Genesis 3:6 says, in part, “So when the woman saw that the tree was good for food...”. The interesting question is, “How did Eve know something was good before eating of the fruit which would give that knowledge?” A typical answer is that Eve determined that the fruit was edible, i.e., “good for food” and that this is somehow different from “morally good.” But this betrays a misunderstanding of the mental machinery by which we determine value.
I’ve asked Rachel to inquire of her teacher to see what he says about this.
Comments
Offical PhD Candiate
08/29/10 11:03 AM Filed in: Proud Father
Received a text from my middle son yesterday: “I passed my tests for official entrance into the PhD candidacy.”
Boolean Expressions and Digital Circuits
08/20/10 07:24 PM Filed in: Computing
This is a continuation of the post Simplifying Boolean Expressions. I started this whole exercise after reading the chapter “Systems of Logic” in “The Turing Omnibus” and deciding to fill some gaps in my education. In particular, as a software engineer, I had never designed a digital circuit. I threw together some LISP code and used it to help me design an adder using 27 nand gates for the portion that computes a sum from three inputs. After simplifying the equations I reduced it to 12 gates.
Lee is a friend and coworker who “used to design some pretty hairy discreet logic circuits back in the day.” He presented a circuit that used a mere 10 gates for the addition. Our circuits to compute the carry were identical.
The equation for the addition portion of his adder is:
However, my code that constructs shortest expressions can easily use a different heuristic and find expressions that result in the fewest gates using my current nand gate compiler. Three different equations result in 8 gates. Feed the output of G0 and G4 into one more nand gate and you get the carry.
Is any more optimization possible? I’m having trouble working up enthusiasm for optimizing my nand gate compiler. However, sufficient incentive would be if Mr. hotshotdigitalcircuitdesigner can one up me.
Lee is a friend and coworker who “used to design some pretty hairy discreet logic circuits back in the day.” He presented a circuit that used a mere 10 gates for the addition. Our circuits to compute the carry were identical.
The equation for the addition portion of his adder is:
(NAND (NAND (NAND (NAND (NAND (NAND X X) Y) (NAND (NAND Y Y) X))
(NAND (NAND (NAND X X) Y) (NAND (NAND Y Y) X))) Z)
(NAND (NAND Z Z) (NAND (NAND (NAND X X) Y) (NAND (NAND Y Y) X))))
His equation has 20 operators where mine had 14:(NAND (NAND (NAND (NAND Z Y) (NAND (NAND Y Y) (NAND Z Z))) X)Lee noted that his equation had a common term that is distributed across the function:
(NAND (NAND (NAND (NAND X X) Y) (NAND (NAND X X) Z)) (NAND Z Y)))
*commonterm* = (NAND (NAND (NAND X X) Y) (NAND (NAND Y Y) X))
*adder* = (NAND (NAND (NAND *commonterm* *commonterm*) Z)
(NAND (NAND Z Z) *commonterm*))
My homegrown nand gate compiler reduces this to Lee’s diagram. Absent a smarter compiler, shorter expressions don’t necessarily result in fewer gates.However, my code that constructs shortest expressions can easily use a different heuristic and find expressions that result in the fewest gates using my current nand gate compiler. Three different equations result in 8 gates. Feed the output of G0 and G4 into one more nand gate and you get the carry.
Is any more optimization possible? I’m having trouble working up enthusiasm for optimizing my nand gate compiler. However, sufficient incentive would be if Mr. hotshotdigitalcircuitdesigner can one up me.
Off To College
08/20/10 10:16 AM Filed in: Life
On Friday the 13th, we loaded up our two cars to take our daughter to college. Left around noon, arrived in Jackson, Mississippi a little after six their time. My wife had the GPS, I had my iPhone. When I got to Mississippi, the map application no longer worked because it couldn’t connect to the internet. In Jackson, everything used AT&T’s Edge network. I had to hard poweroff the phone to get it to connect via 3G.
Move in began 9am Saturday and we had everything unloaded and mostly in place by noon. Extremely hot and muggy day; sweat was dripping off of bird’s beaks. Went shopping after lunch to get a small table for the printer, a USB cable, a longer RF cable for the TV, and an ethernet cable. Cable prices, at least at Best Buy, are ridiculous. With some extra planning I could have made the RF and ethernet cables for next to nothing.
Sunday morning all three of us went to the grocery store to stock up daughter’s refrigerator; then mom and daughter went shopping for clothes. We had lunch with her then she left for a school outing and we began the drive home. And that’s how we spent our 30th anniversary  on the road back to a mostly empty nest.
Rachel’s room is a typical dorm room. It isn’t that different from mine 30 years ago. She has a refrigerator which I didn’t have. Everyone was bringing them in. We had my roommates stereo system while her iPod is docked to her alarm clock. We both had small televisions, but she has cable. She has an iPhone, we had a pay phone (was it pay?) on the wall at the end of the hall. The biggest difference is her computer. She has a laptop which can outperform the Control Data 6400 that I used at UVa and a color inkjet printer/scanner instead of an ASR33 teletype. She also has a wireless Wacom tablet.
Unfortunately, we didn’t get a chance to meet Rachel’s roommate. She arrived after we left.
Move in began 9am Saturday and we had everything unloaded and mostly in place by noon. Extremely hot and muggy day; sweat was dripping off of bird’s beaks. Went shopping after lunch to get a small table for the printer, a USB cable, a longer RF cable for the TV, and an ethernet cable. Cable prices, at least at Best Buy, are ridiculous. With some extra planning I could have made the RF and ethernet cables for next to nothing.
Sunday morning all three of us went to the grocery store to stock up daughter’s refrigerator; then mom and daughter went shopping for clothes. We had lunch with her then she left for a school outing and we began the drive home. And that’s how we spent our 30th anniversary  on the road back to a mostly empty nest.
Rachel’s room is a typical dorm room. It isn’t that different from mine 30 years ago. She has a refrigerator which I didn’t have. Everyone was bringing them in. We had my roommates stereo system while her iPod is docked to her alarm clock. We both had small televisions, but she has cable. She has an iPhone, we had a pay phone (was it pay?) on the wall at the end of the hall. The biggest difference is her computer. She has a laptop which can outperform the Control Data 6400 that I used at UVa and a color inkjet printer/scanner instead of an ASR33 teletype. She also has a wireless Wacom tablet.
Unfortunately, we didn’t get a chance to meet Rachel’s roommate. She arrived after we left.
Simplifying Boolean Expressions
08/10/10 10:25 AM Filed in: Computing
The previous post on Boolean logic presented an algorithm for generating an expression consisting of AND and NOT for any given truth table. However, this method clearly did not always give the simplest form for the expression. As just one example, the algorithm gives this result:
Consider the problem of simplifying Boolean expressions. A truth table with n variables results in 2^{2n} expressions as shown in the following figure.
Finding the simplest expression is conceptually simple. For expressions of three variables we can see that the expression that results in f_{7}=f_{6}=f_{5}=f_{4}=f_{3}=f_{2}=f_{1}=f_{0} = 0 is the constant 0. The expression that results in f_{7}..f_{0} = 1 is the constant 1. Then we progress to the functions of a single variable. f_{7}..f_{0} = 10001000 is X. f_{7}..f_{0} = 01110111 is (NOT X). f_{7}..f_{0} = 11001100 is Y and 00110011 is (NOT Y). f_{7}..f_{0} = 10101010 is Z and 01010101 is (NOT Z).
Create a table E_{xyz} of 2^{23} = 256 entries. E_{xyz}(0) = “0”. E_{xyz}(255) = “1”. E_{xyz}(10001000 {i.e. 136}) = “X”. E_{xyz}(01110111 {119}) = “(NOT X)”. E_{xyz}(204) = “Y”, E_{xyz}(51) = “(NOT Y)”, E_{xyz}(170) = “Z” and E_{xyz}(85) is “(NOT Z)”. Assume that this process can continue for the entire table. Then to simplify (or generate) an expression, evaluate f_{7}..f_{0 }and look up the corresponding formula in E_{xyz}.
While conceptually easy, this is computationally hard. Expressions of 4 variables require an expression table with 2^{16} entries and 5 variables requires 2^{32} entries  not something I’d want to try to compute on any single machine at my disposal. An expression with 8 variables is close to the number of particles in the universe, estimated to be 10^{87}.
Still, simplifying expressions of up to 4 variables is useful and considering the general solution is an interesting mental exercise.
To determine the total number of equations for expressions with three variables, start by analyzing simpler cases.
With zero variables there are two unique expressions: “0” and “1”.
With one variable there are four expressions: “0”, “1”, “X”, and “(NOT X)”.
Two variables is more interesting. There are the two constant expressions “0” and “1”. Then there are the single variable expressions, with X and Y: “X”, “(NOT X)”, “Y”, “(NOT Y)”. There are 8 expressions of two variables: “(AND X Y)”, “(AND X (NOT Y))”, “(AND (NOT X) Y)” and “(AND (NOT X) (NOT Y))”, and their negations. But that gives only 14 out of the 16 possible expressions. We also have to consider combinations of the expressions of two variables. At most this would be 8^{2} combinations times 2 for the negated forms. Since (AND X X) is equivalent to X, this can be reduced to 7+6+5+4+3+2+1 = 28 combinations, times 2 for the negated forms. This gives 56 possibilities for the remaining two formulas, which turn out to be “(AND (NOT (AND (NOT X) (NOT Y))) (NOT (AND X Y)))” and “(AND (NOT (AND X (NOT Y))) (NOT (AND (NOT X) Y)))”.
It might be possible to further reduce the number of expressions to be examined. Out of the 2*8^{2} possible combinations of the two variable forms, there can only be 16 unique values. However, I haven’t given much thought how to do this. In any case, the computer can repeat the process of negating and combining expressions to generate the forms with the fewest number of AND/NOT (or NAND) operators.
E_{xyz}(150) is interesting, since this is the expression for the sum part of the adder. The “naive” formula has 21 operators. There are three formulas with 20 operators that give the same result:
Absent a smarter compiler, is it possible to reduce the gate count even more? The code that searches for the simplest forms of expressions using AND and NOT can also find the simplest form of NAND expressions. One of three versions of E_{xyz}(150) is:
E_{xyz}(232), which is the carry equation for the adder, can be written as:
G11 is the sum of the three inputs while G16 is the carry.
x y  t(3)Via inspection, the simpler form is (NOT X).
0 0  1
0 1  1 => (AND (NOT (AND X (NOT Y))) (NOT (AND X Y)))
1 0  0
1 1  0
Consider the problem of simplifying Boolean expressions. A truth table with n variables results in 2^{2n} expressions as shown in the following figure.
Finding the simplest expression is conceptually simple. For expressions of three variables we can see that the expression that results in f_{7}=f_{6}=f_{5}=f_{4}=f_{3}=f_{2}=f_{1}=f_{0} = 0 is the constant 0. The expression that results in f_{7}..f_{0} = 1 is the constant 1. Then we progress to the functions of a single variable. f_{7}..f_{0} = 10001000 is X. f_{7}..f_{0} = 01110111 is (NOT X). f_{7}..f_{0} = 11001100 is Y and 00110011 is (NOT Y). f_{7}..f_{0} = 10101010 is Z and 01010101 is (NOT Z).
Create a table E_{xyz} of 2^{23} = 256 entries. E_{xyz}(0) = “0”. E_{xyz}(255) = “1”. E_{xyz}(10001000 {i.e. 136}) = “X”. E_{xyz}(01110111 {119}) = “(NOT X)”. E_{xyz}(204) = “Y”, E_{xyz}(51) = “(NOT Y)”, E_{xyz}(170) = “Z” and E_{xyz}(85) is “(NOT Z)”. Assume that this process can continue for the entire table. Then to simplify (or generate) an expression, evaluate f_{7}..f_{0 }and look up the corresponding formula in E_{xyz}.
While conceptually easy, this is computationally hard. Expressions of 4 variables require an expression table with 2^{16} entries and 5 variables requires 2^{32} entries  not something I’d want to try to compute on any single machine at my disposal. An expression with 8 variables is close to the number of particles in the universe, estimated to be 10^{87}.
Still, simplifying expressions of up to 4 variables is useful and considering the general solution is an interesting mental exercise.
To determine the total number of equations for expressions with three variables, start by analyzing simpler cases.
With zero variables there are two unique expressions: “0” and “1”.
With one variable there are four expressions: “0”, “1”, “X”, and “(NOT X)”.
Two variables is more interesting. There are the two constant expressions “0” and “1”. Then there are the single variable expressions, with X and Y: “X”, “(NOT X)”, “Y”, “(NOT Y)”. There are 8 expressions of two variables: “(AND X Y)”, “(AND X (NOT Y))”, “(AND (NOT X) Y)” and “(AND (NOT X) (NOT Y))”, and their negations. But that gives only 14 out of the 16 possible expressions. We also have to consider combinations of the expressions of two variables. At most this would be 8^{2} combinations times 2 for the negated forms. Since (AND X X) is equivalent to X, this can be reduced to 7+6+5+4+3+2+1 = 28 combinations, times 2 for the negated forms. This gives 56 possibilities for the remaining two formulas, which turn out to be “(AND (NOT (AND (NOT X) (NOT Y))) (NOT (AND X Y)))” and “(AND (NOT (AND X (NOT Y))) (NOT (AND (NOT X) Y)))”.
It might be possible to further reduce the number of expressions to be examined. Out of the 2*8^{2} possible combinations of the two variable forms, there can only be 16 unique values. However, I haven’t given much thought how to do this. In any case, the computer can repeat the process of negating and combining expressions to generate the forms with the fewest number of AND/NOT (or NAND) operators.
E_{xyz}(150) is interesting, since this is the expression for the sum part of the adder. The “naive” formula has 21 operators. There are three formulas with 20 operators that give the same result:
(AND (AND (NOT (AND (AND X (NOT Y)) Z)) (NOT (AND X (AND Y (NOT Z)))))
(NOT (AND (NOT (AND (NOT Y) Z)) (AND (NOT (AND Y (NOT Z))) (NOT X)))))
(AND (AND (NOT (AND (NOT X) (AND Z Y))) (NOT (AND X (AND Y (NOT Z)))))
(NOT (AND (AND (NOT (AND X (NOT Z))) (NOT Y)) (NOT (AND (NOT X) Z)))))
(AND (NOT (AND (AND (NOT Z) (NOT (AND X (NOT Y)))) (NOT (AND (NOT X) Y))))
(AND (NOT (AND (AND X (NOT Y)) Z)) (NOT (AND (NOT X) (AND Z Y)))))
Which one should be used? It depends. A simple nand gate compiler that uses the rules(NOT X) > (NAND X X)compiles the first and last into 17 gates while the second compiles to 16 gates. Another form of E_{xyz}(150) compiles to 15 gates. This suggests that the nand gate compiler could benefit from additional optimizations. One possible approach might be to make use of the equality between (NAND X (NAND Y Y)) and (NAND X (NAND X Y)).
(AND X Y) > temp := (NAND X Y) (NAND temp temp)
Absent a smarter compiler, is it possible to reduce the gate count even more? The code that searches for the simplest forms of expressions using AND and NOT can also find the simplest form of NAND expressions. One of three versions of E_{xyz}(150) is:
(NAND (NAND (NAND (NAND Z Y) (NAND (NAND Y Y) (NAND Z Z))) X)
(NAND (NAND (NAND (NAND X X) Y) (NAND (NAND X X) Z)) (NAND Z Y)))
This compiles to 12 gates.E_{xyz}(232), which is the carry equation for the adder, can be written as:
(NAND (NAND (NAND (NAND Y X) (NAND Z X)) X) (NAND Z Y))
With these simplifications the adder takes ten fewer gates than the first iteration:G11 is the sum of the three inputs while G16 is the carry.
Boolean Logic
08/08/10 08:57 PM Filed in: Computing
I have a BS in applied math and I’m appalled at what I wasn’t taught. I learned about truth tables, the logical operators AND, OR, NOT, EXCLUSIVEOR, IMPLIES, and EQUIVALENT. I know De Morgan’s rules and in 1977 I wrote a Pascal program to read an arbitrary logical expression and print out the truth table for it. I was dimly aware of NAND and NOR. I think I knew that any logical operation could be written using NAND (or NOR) exclusively, but I didn’t know why. Perhaps that’s the life of a software engineer.
Consider Boolean expressions of two variables; call them x and y. Each variable can take on two values, 0 and 1, so there are 4 possible inputs and 4 possible outputs. Four possible outputs gives a total of 16 different outcomes, as the following tables, labeled t(0) to t(15), show. The tables are ordered so that each table in a row is the complement of the other table. This will be useful in exploiting symmetry when we start writing logical expressions for each table. Note that for each t(n), the value in the first row corresponds to bit 0 of n, the second row is bit 1, and so on.
We can make some initial observations.
t(8) = (AND x y)
t(9) = (EQUIVALENT x y).
t(10) = y
t(11) =(IMPLIES x y), which is equivalent to (OR (NOT x) y)
t(12) = x.
t(13) is a function I’m not familiar with. The Turing Omnibus says that it’s the “reverse implication” function, which is patently obvious since it’s (IMPLIES y x).
t(14) = (OR x y)
t(15) = 1
What I never noticed before is that all of the common operations: AND, OR, NOT, IMPLIES, and EQUIVALENCE are grouped together. EXCLUSIVEOR is the only “common” operation on the other side. Is this an artifact of the way our minds are wired to think: that we tend to define things in terms of x instead of (NOT x)? Are we wired to favor some type of computational simplicity? Nature is “lazy," that is, she conserves energy and our mental computations require energy.
In any case, the other table entries follow by negation:
t(0) = 0
t(1) = (NOT (OR x y)), which is equivalent to (NOR x y).
t(2) = (NOT (IMPLIES y x))
t(3) = (NOT x)
t(4) = (NOT (IMPLIES x y))
t(5) = (NOT y).
t(6) = (EXCLUSIVEOR x y), or (NOT (EQUIVALENT x y))
t(7) = (NOT (AND x y)), also known as (NAND x y)
All of these functions can be expressed in terms of NOT, AND, and OR as will be shown in a subsequent table. t(0) = 0 can be written as (AND x (NOT x)). t(15) = 1 can be written as (OR x (NOT x)). The Turing Omnibus gives a method for expressing each table in terms of NOT and AND:
For each row with a zero result in a particular table, create a function (AND (f x) (g y)) where f and g evaluate to one for the values of x and y in that row, then negate it, i.e., (NOT (AND (f x) (g y))). This guarantees that the particular row evaluates to zero. Then AND all of these terms together.
What about the rows that evaluate to one? Suppose one such row is denoted by xx and yy. Then either xx is not equal to x, yy is not equal to y, or both. Suppose xx is differs from x. Then (f xx) will evaluate to zero, so (AND (f xx) (g yy)) evaluates to zero, therefore (NOT (AND (f xx) (g yy))) will evaluate to one. In this way, all rows that evaluate to one will evaluate to one and all rows that evaluate to zero will evaluate to zero. Thus the resulting expression generates the table.
Converting to NOT/OR form uses the same idea. For each row with a one result in a particular table, create a function (OR (f x) (g y)) where f and g evaluate to zero for the values of x and y in that row, then negate it, i.e. (NOT (OR (f x) (g y))). Then OR all of these terms together.
The application of this algorithm yields the following formulas. Note that the algorithm gives a nonoptimal result for t(0), which is more simply written as (AND X (NOT X)). Perhaps this is not a fair comparison, since the algorithm is generating a function of two variables, when one will do. More appropriately, t(1) is equivalent to (AND (NOT X) (NOT Y)). So there is a need for simplifying expressions, which will mostly be ignored for now.
(AND x y) = (NOT (NOT (AND x y)) = (NOT (NAND x y)) = (NAND (NAND x y) (NAND x y)).
These two transformations allow t(0) through t(15) to be expressed solely in terms of NAND.
Putting everything together, we have the following tables of identities. There is some organization to the ordering: first, the commonly defined function. Next, the AND/NOT form. Then the negation of the complementary form in those cases where it makes sense. Then a NAND form and, lastly, an alternate OR form. No effort was made to determine if any formula was in its simplest form. All of these equations have been machine checked. That’s one reason why they are in LISP notation.
Let’s make an overly long post even longer. Since we can do any logical operation using NAND, and since I’ve never had any classes in digital hardware design, let’s go ahead and build a 4bit adder. The basic highlevel building block will be a device that has three inputs: addend, augend, and carry and produces two outputs: sum and carry. The bits of the addend will be denoted by a0 to a3, the augend as b0 to b3, the sum as s0 to s3, and the carry bits as c0 to c3. The carry from one operation is fed into the next summation in the chain.
Substituting (X, Y, Z) for (a, b, c) the NOT/AND forms are
The NAND forms for t(sum) and t(carry) are monstrous. The conversions contain a great deal of redundancy since (AND X Y) becomes (NAND (NAND x y) (NAND x y)).
However, symmetry will help a little bit. t(sum) = t(#x96) = (not t(not #x96)) =
The complexity can be tamed with mechanical substitution and the use of “variables”:
let G0 = (NAND X X)
let G1 = (NAND Y Y)
let G2 = (NAND G1 Z)
let G3 = (NAND G2 G2)
let G4 = (NAND G0 G3)
let G5 = (NAND Z Z)
let G6 = (NAND Y G5)
let G7 = (NAND G6 G6)
let G8 = (NAND G0 G7)
let G9 = (NAND G1 G5)
let G10 = (NAND G9 G9)
let G11 = (NAND X G10)
let G12 = (NAND Y Z)
let G13 = (NAND G12 G12)
let G14 = (NAND X G13)
let G15 = (NAND G11 G14)
let G16 = (NAND G15 G15)
let G17 = (NAND G8 G16)
let G18 = (NAND G17 G17)
t(sum) = (NAND G4 G18)
The same kind of analysis can be done with the NAND form of the carry. The carry has a number of gates in common with the summation. Putting everything together, the circuitry for the adder would look something like this. Ignoring, of course, the real world where I’m sure there are issues involved with circuit layout. The output of the addition is the red (rightmost bottom) gate while the output of the carry is the last green (rightmost top) gate. The other green gates are those which are unique to the carry. The diagram offends my aesthetic sense with the crossovers, multiple inputs, and choice of colors. My apologies to those of you who may be color blind.
What took me a few hours to do with a computer must have taken thousands of manhours to do without a computer. I may share the code I developed while writing this blog entry in a later post. The missing piece is simplification of logical expressions and I haven’t yet decided if I want to take the time to add that.
Consider Boolean expressions of two variables; call them x and y. Each variable can take on two values, 0 and 1, so there are 4 possible inputs and 4 possible outputs. Four possible outputs gives a total of 16 different outcomes, as the following tables, labeled t(0) to t(15), show. The tables are ordered so that each table in a row is the complement of the other table. This will be useful in exploiting symmetry when we start writing logical expressions for each table. Note that for each t(n), the value in the first row corresponds to bit 0 of n, the second row is bit 1, and so on.
x y  t(0) x y  t(15)
0 0  0 0 0  1
0 1  0 0 1  1
1 0  0 1 0  1
1 1  0 1 1  1
x y  t(1) x y  t(14)
0 0  1 0 0  0
0 1  0 0 1  1
1 0  0 1 0  1
1 1  0 1 1  1
x y  t(2) x y  t(13)
0 0  0 0 0  1
0 1  1 0 1  0
1 0  0 1 0  1
1 1  0 1 1  1
x y  t(3) x y  t(12)
0 0  1 0 0  0
0 1  1 0 1  0
1 0  0 1 0  1
1 1  0 1 1  1
x y  t(4) x y  t(11)
0 0  0 0 0  1
0 1  0 0 1  1
1 0  1 1 0  0
1 1  0 1 1  1
x y  t(5) x y  t(10)
0 0  1 0 0  0
0 1  0 0 1  1
1 0  1 1 0  0
1 1  0 1 1  1
x y  t(6) x y  t(9)
0 0  0 0 0  1
0 1  1 0 1  0
1 0  1 1 0  0
1 1  0 1 1  1
x y  t(7) x y  t(8)
0 0  1 0 0  0
0 1  1 0 1  0
1 0  1 1 0  0
1 1  0 1 1  1
We can make some initial observations.
t(8) = (AND x y)
t(9) = (EQUIVALENT x y).
t(10) = y
t(11) =(IMPLIES x y), which is equivalent to (OR (NOT x) y)
t(12) = x.
t(13) is a function I’m not familiar with. The Turing Omnibus says that it’s the “reverse implication” function, which is patently obvious since it’s (IMPLIES y x).
t(14) = (OR x y)
t(15) = 1
What I never noticed before is that all of the common operations: AND, OR, NOT, IMPLIES, and EQUIVALENCE are grouped together. EXCLUSIVEOR is the only “common” operation on the other side. Is this an artifact of the way our minds are wired to think: that we tend to define things in terms of x instead of (NOT x)? Are we wired to favor some type of computational simplicity? Nature is “lazy," that is, she conserves energy and our mental computations require energy.
In any case, the other table entries follow by negation:
t(0) = 0
t(1) = (NOT (OR x y)), which is equivalent to (NOR x y).
t(2) = (NOT (IMPLIES y x))
t(3) = (NOT x)
t(4) = (NOT (IMPLIES x y))
t(5) = (NOT y).
t(6) = (EXCLUSIVEOR x y), or (NOT (EQUIVALENT x y))
t(7) = (NOT (AND x y)), also known as (NAND x y)
All of these functions can be expressed in terms of NOT, AND, and OR as will be shown in a subsequent table. t(0) = 0 can be written as (AND x (NOT x)). t(15) = 1 can be written as (OR x (NOT x)). The Turing Omnibus gives a method for expressing each table in terms of NOT and AND:
For each row with a zero result in a particular table, create a function (AND (f x) (g y)) where f and g evaluate to one for the values of x and y in that row, then negate it, i.e., (NOT (AND (f x) (g y))). This guarantees that the particular row evaluates to zero. Then AND all of these terms together.
What about the rows that evaluate to one? Suppose one such row is denoted by xx and yy. Then either xx is not equal to x, yy is not equal to y, or both. Suppose xx is differs from x. Then (f xx) will evaluate to zero, so (AND (f xx) (g yy)) evaluates to zero, therefore (NOT (AND (f xx) (g yy))) will evaluate to one. In this way, all rows that evaluate to one will evaluate to one and all rows that evaluate to zero will evaluate to zero. Thus the resulting expression generates the table.
Converting to NOT/OR form uses the same idea. For each row with a one result in a particular table, create a function (OR (f x) (g y)) where f and g evaluate to zero for the values of x and y in that row, then negate it, i.e. (NOT (OR (f x) (g y))). Then OR all of these terms together.
The application of this algorithm yields the following formulas. Note that the algorithm gives a nonoptimal result for t(0), which is more simply written as (AND X (NOT X)). Perhaps this is not a fair comparison, since the algorithm is generating a function of two variables, when one will do. More appropriately, t(1) is equivalent to (AND (NOT X) (NOT Y)). So there is a need for simplifying expressions, which will mostly be ignored for now.
Define (NAND x y) to be (NOT (AND x y)). Then (NAND x x) = (NOT (AND x x)) = (NOT x).
t(0) = (AND (NOT (AND (NOT X) (NOT Y)))
(AND (NOT (AND (NOT X) Y))
(AND (NOT (AND X (NOT Y))) (NOT (AND X Y)))))
t(1) = (AND (NOT (AND (NOT X) Y))
(AND (NOT (AND X (NOT Y))) (NOT (AND X Y))))
t(2) = (AND (NOT (AND (NOT X) (NOT Y)))
(AND (NOT (AND X (NOT Y))) (NOT (AND X Y))))
t(3) = (AND (NOT (AND X (NOT Y))) (NOT (AND X Y)))
t(4) = (AND (NOT (AND (NOT X) (NOT Y)))
(AND (NOT (AND (NOT X) Y)) (NOT (AND X Y))))
t(5) = (AND (NOT (AND (NOT X) Y)) (NOT (AND X Y)))
t(6) = (AND (NOT (AND (NOT X) (NOT Y))) (NOT (AND X Y)))
t(7) = (NOT (AND X Y))
t(8) = (AND (NOT (AND (NOT X) (NOT Y)))
(AND (NOT (AND (NOT X) Y)) (NOT (AND X (NOT Y)))))
t(9) = (AND (NOT (AND (NOT X) Y)) (NOT (AND X (NOT Y))))
t(10) = (AND (NOT (AND (NOT X) (NOT Y))) (NOT (AND X (NOT Y))))
t(11) = (NOT (AND X (NOT Y)))
t(12) = (AND (NOT (AND (NOT X) (NOT Y))) (NOT (AND (NOT X) Y)))
t(13) = (NOT (AND (NOT X) Y))
t(14) = (NOT (AND (NOT X) (NOT Y)))
t(15) = (NOT (AND X (NOT X)))
(AND x y) = (NOT (NOT (AND x y)) = (NOT (NAND x y)) = (NAND (NAND x y) (NAND x y)).
These two transformations allow t(0) through t(15) to be expressed solely in terms of NAND.
Putting everything together, we have the following tables of identities. There is some organization to the ordering: first, the commonly defined function. Next, the AND/NOT form. Then the negation of the complementary form in those cases where it makes sense. Then a NAND form and, lastly, an alternate OR form. No effort was made to determine if any formula was in its simplest form. All of these equations have been machine checked. That’s one reason why they are in LISP notation.
x y  t(0) x y  t(15)
0 0  0 0 0  1
0 1  0 0 1  1
1 0  0 1 0  1
1 1  0 1 1  1
0 1
(NOT 1) (NOT 0)
(AND X (NOT X)) (NOT (AND X (NOT X)))
(AND (NOT (AND (NOT X) (NOT Y)))
(AND (NOT (AND (NOT X) Y))
(AND (NOT (AND X (NOT Y)))
(NOT (AND X Y)))))
(NOT (NAND X (NAND X X))) (NAND X (NAND X X))
(NAND (NAND X (NAND X X))
(NAND X (NAND X X)))
(OR X (NOT X))
x y  t(1) x y  t(14)
0 0  1 0 0  0
0 1  0 0 1  1
1 0  0 1 0  1
1 1  0 1 1  1
(NOT (OR X Y)) (OR X Y)
(NOR X Y)
(AND (NOT (AND (NOT X) Y)) (NOT (AND (NOT X) (NOT Y)))
(AND (NOT (AND X (NOT Y)))
(NOT (AND X Y))))
(NOT (NAND (NAND X X) (NAND Y Y))) (NAND (NAND X X) (NAND Y Y))
(NAND (NAND (NAND X X) (NAND Y Y))
(NAND (NAND X X) (NAND Y Y)))
x y  t(2) x y  t(13)
0 0  0 0 0  1
0 1  1 0 1  0
1 0  0 1 0  1
1 1  0 1 1  1
(NOT (IMPLIES Y X)) (IMPLIES Y X)
(AND (NOT X) Y) (NOT (AND (NOT X) Y))
(AND (NOT (AND (NOT X) (NOT Y)))
(AND (NOT (AND X (NOT Y)))
(NOT (AND X Y))))
(AND (NAND X X) Y)
(NOT (NAND (NAND X X) Y)) (NAND (NAND X X) Y)
(NAND (NAND (NAND X X) Y)
(NAND (NAND X X) Y))
(NOT (OR X (NOT Y))) (OR X (NOT Y))
x y  t(3) x y  t(12)
0 0  1 0 0  0
0 1  1 0 1  0
1 0  0 1 0  1
1 1  0 1 1  1
(NOT X) X
(AND (NOT (AND X (NOT Y))) (AND (NOT (AND (NOT X) (NOT Y)))
(NOT (AND X Y))) (NOT (AND (NOT X) Y)))
(NAND X X) (NAND (NAND X X) (NAND X X))
x y  t(4) x y  t(11)
0 0  0 0 0  1
0 1  0 0 1  1
1 0  1 1 0  0
1 1  0 1 1  1
(NOT (IMPLIES X Y)) (IMPLIES X Y)
(AND X (NOT Y)) (NOT (AND X (NOT Y)))
(AND (NOT (AND (NOT X) (NOT Y)))
(AND (NOT (AND (NOT X) Y))
(NOT (AND X Y))))
(NOT (NAND X (NAND Y Y))) (NAND X (NAND Y Y))
(NAND (NAND X (NAND Y Y))
(NAND X (NAND Y Y)))
(OR (NOT X) Y)
x y  t(5) x y  t(10)
0 0  1 0 0  0
0 1  0 0 1  1
1 0  1 1 0  0
1 1  0 1 1  1
(NOT Y) Y
(AND (NOT (AND (NOT X) Y)) (AND (NOT (AND (NOT X) (NOT Y)))
(NOT (AND X Y))) (NOT (AND X (NOT Y))))
(AND (NAND (NAND X X) Y) (AND (NAND (NAND X X) (NAND Y Y))
(NAND X Y)) (NAND X (NAND Y Y)))
(NAND Y Y) (NOT (NAND Y Y))
(NAND (NAND Y Y) (NAND Y Y))
x y  t(6) x y  t(9)
0 0  0 0 0  1
0 1  1 0 1  0
1 0  1 1 0  0
1 1  0 1 1  1
(NOT (EQUIVALENT X Y)) (EQUIVALENT X Y)
(EXCLUSIVEOR X Y) (NOT (EXCLUSIVEOR X Y))
(AND (NOT (AND (NOT X) (NOT Y))) (AND (NOT (AND (NOT X) Y)) (NOT (AND X (NOT Y))))
(NOT (AND X Y)))
(NAND (NAND (NAND X X) Y) (NAND (NAND (NAND X X) (NAND Y Y)) (NAND X Y))
(NAND X (NAND Y Y)))
x y  t(7) x y  t(8)
0 0  1 0 0  0
0 1  1 0 1  0
1 0  1 1 0  0
1 1  0 1 1  1
(AND X Y)
(NOT (AND X Y)) (AND (NOT (AND (NOT X) (NOT Y)))
(AND (NOT (AND (NOT X) Y))
(NOT (AND X (NOT Y)))))
(NAND X Y) (NOT (NAND X Y))
(NAND (NAND X Y) (NAND X Y))
(OR (NOT X) (NOT Y))
Let’s make an overly long post even longer. Since we can do any logical operation using NAND, and since I’ve never had any classes in digital hardware design, let’s go ahead and build a 4bit adder. The basic highlevel building block will be a device that has three inputs: addend, augend, and carry and produces two outputs: sum and carry. The bits of the addend will be denoted by a0 to a3, the augend as b0 to b3, the sum as s0 to s3, and the carry bits as c0 to c3. The carry from one operation is fed into the next summation in the chain.
The “add” operation is defined by t(sum), while the carry is defined by t(carry):
a b c  t(sum) a b c  t(carry)
0 0 0  0 0 0 0  0
0 0 1  1 0 0 1  0
0 1 0  1 0 1 0  0
0 1 1  0 0 1 1  1
1 0 0  1 1 0 0  0
1 0 1  0 1 0 1  1
1 1 0  0 1 1 0  1
1 1 1  1 1 1 1  1
Substituting (X, Y, Z) for (a, b, c) the NOT/AND forms are
t(sum) = (AND (NOT (AND (NOT X) (AND (NOT Y) (NOT Z))))
(AND (NOT (AND (NOT X) (AND Y Z)))
(AND (NOT (AND X (AND (NOT Y) Z))) (NOT (AND X (AND Y (NOT Z)))))))
t(carry) = (AND (NOT (AND (NOT X) (AND (NOT Y) (NOT Z))))
(AND (NOT (AND (NOT X) (AND (NOT Y) Z)))
(AND (NOT (AND (NOT X) (AND Y (NOT Z))))
(NOT (AND X (AND (NOT Y) (NOT Z)))))))
The NAND forms for t(sum) and t(carry) are monstrous. The conversions contain a great deal of redundancy since (AND X Y) becomes (NAND (NAND x y) (NAND x y)).
However, symmetry will help a little bit. t(sum) = t(#x96) = (not t(not #x96)) =
(NAND
(NAND (NAND (NAND X X) (NAND (NAND (NAND Y Y) Z) (NAND (NAND Y Y) Z)))
(NAND
(NAND (NAND (NAND X X) (NAND (NAND Y (NAND Z Z)) (NAND Y (NAND Z Z))))
(NAND
(NAND
(NAND X
(NAND (NAND (NAND Y Y) (NAND Z Z))
(NAND (NAND Y Y) (NAND Z Z))))
(NAND X (NAND (NAND Y Z) (NAND Y Z))))
(NAND
(NAND X
(NAND (NAND (NAND Y Y) (NAND Z Z))
(NAND (NAND Y Y) (NAND Z Z))))
(NAND X (NAND (NAND Y Z) (NAND Y Z))))))
(NAND (NAND (NAND X X) (NAND (NAND Y (NAND Z Z)) (NAND Y (NAND Z Z))))
(NAND
(NAND
(NAND X
(NAND (NAND (NAND Y Y) (NAND Z Z))
(NAND (NAND Y Y) (NAND Z Z))))
(NAND X (NAND (NAND Y Z) (NAND Y Z))))
(NAND
(NAND X
(NAND (NAND (NAND Y Y) (NAND Z Z))
(NAND (NAND Y Y) (NAND Z Z))))
(NAND X (NAND (NAND Y Z) (NAND Y Z))))))))
(NAND (NAND (NAND X X) (NAND (NAND (NAND Y Y) Z) (NAND (NAND Y Y) Z)))
(NAND
(NAND (NAND (NAND X X) (NAND (NAND Y (NAND Z Z)) (NAND Y (NAND Z Z))))
(NAND
(NAND
(NAND X
(NAND (NAND (NAND Y Y) (NAND Z Z))
(NAND (NAND Y Y) (NAND Z Z))))
(NAND X (NAND (NAND Y Z) (NAND Y Z))))
(NAND
(NAND X
(NAND (NAND (NAND Y Y) (NAND Z Z))
(NAND (NAND Y Y) (NAND Z Z))))
(NAND X (NAND (NAND Y Z) (NAND Y Z))))))
(NAND (NAND (NAND X X) (NAND (NAND Y (NAND Z Z)) (NAND Y (NAND Z Z))))
(NAND
(NAND
(NAND X
(NAND (NAND (NAND Y Y) (NAND Z Z))
(NAND (NAND Y Y) (NAND Z Z))))
(NAND X (NAND (NAND Y Z) (NAND Y Z))))
(NAND
(NAND X
(NAND (NAND (NAND Y Y) (NAND Z Z))
(NAND (NAND Y Y) (NAND Z Z))))
(NAND X (NAND (NAND Y Z) (NAND Y Z)))))))))
The complexity can be tamed with mechanical substitution and the use of “variables”:
let G0 = (NAND X X)
let G1 = (NAND Y Y)
let G2 = (NAND G1 Z)
let G3 = (NAND G2 G2)
let G4 = (NAND G0 G3)
let G5 = (NAND Z Z)
let G6 = (NAND Y G5)
let G7 = (NAND G6 G6)
let G8 = (NAND G0 G7)
let G9 = (NAND G1 G5)
let G10 = (NAND G9 G9)
let G11 = (NAND X G10)
let G12 = (NAND Y Z)
let G13 = (NAND G12 G12)
let G14 = (NAND X G13)
let G15 = (NAND G11 G14)
let G16 = (NAND G15 G15)
let G17 = (NAND G8 G16)
let G18 = (NAND G17 G17)
t(sum) = (NAND G4 G18)
The same kind of analysis can be done with the NAND form of the carry. The carry has a number of gates in common with the summation. Putting everything together, the circuitry for the adder would look something like this. Ignoring, of course, the real world where I’m sure there are issues involved with circuit layout. The output of the addition is the red (rightmost bottom) gate while the output of the carry is the last green (rightmost top) gate. The other green gates are those which are unique to the carry. The diagram offends my aesthetic sense with the crossovers, multiple inputs, and choice of colors. My apologies to those of you who may be color blind.
What took me a few hours to do with a computer must have taken thousands of manhours to do without a computer. I may share the code I developed while writing this blog entry in a later post. The missing piece is simplification of logical expressions and I haven’t yet decided if I want to take the time to add that.
Artifical Intelligence, Evolution, Theodicy
[Updated 8/20/10]
Introduction to Artificial Intelligence asks the question, “How can we guarantee that an artificial intelligence will ‘like’ the nature of its existence?”
A partial motivation for this question is given in note 714:
Why should this question be asked? In addition to the possibility of an altruistic desire on the part of computer scientists to make their machines “happy and contented,” there is the more concrete reason (for us, if not for the machine) that we would like people to be relatively happy and contented concerning their interactions with the machines. We may have to learn to design computers that are incapable of setting up certain goals relating to changes in selected aspects of their performance and designnamely, those aspects that are “people protecting.”
Anyone familiar with Asimov’s “Three Laws of Robotics” recognizes the desire for something like this. We don’t want to create machines that turn on their creators.
Yet before asking this question, the text gives five features of a system capable of evolving human order intelligence [1]:
What might be some of the properties of a selfaware intelligence that realizes that things are not what they ought to be?
Whatever else, we wouldn’t be driven to improve. We wouldn’t build machines. We wouldn’t formulate medicine. We wouldn’t create art. Is it any wonder, then, that the Garden of Eden is central to the story of Man?
[1] Taken from “Programs with Common Sense”, John McCarthy, 1959. In the paper, McCarthy focused exclusively the second point.
Introduction to Artificial Intelligence asks the question, “How can we guarantee that an artificial intelligence will ‘like’ the nature of its existence?”
A partial motivation for this question is given in note 714:
Why should this question be asked? In addition to the possibility of an altruistic desire on the part of computer scientists to make their machines “happy and contented,” there is the more concrete reason (for us, if not for the machine) that we would like people to be relatively happy and contented concerning their interactions with the machines. We may have to learn to design computers that are incapable of setting up certain goals relating to changes in selected aspects of their performance and designnamely, those aspects that are “people protecting.”
Anyone familiar with Asimov’s “Three Laws of Robotics” recognizes the desire for something like this. We don’t want to create machines that turn on their creators.
Yet before asking this question, the text gives five features of a system capable of evolving human order intelligence [1]:
 All behaviors must be representable in the system. Therefore, the system should either be able to construct arbitrary automata or to program in some generalpurpose programming language.
 Interesting changes in behavior must be expressible in a simple way.
 All aspects of behavior except the most routine should be improvable. In particular, the improving mechanism should be improvable.
 The machine must have or evolve concepts of partial success because on difficult problems decisive successes or failures come too infrequently.
 The system must be able to create subroutines which can be included in procedures in units...
What might be some of the properties of a selfaware intelligence that realizes that things are not what they ought to be?
 Would the machine spiral into despair, knowing that not only is it not what it ought to be, but its ability to improve itself is also not what it ought to be? Was C3PO demonstrating this property when he said, “We were made to suffer. It’s our lot in life.”?
 Would the machine, knowing itself to be flawed, look to something external to itself as a source of improvement?
 Would the selfreflective machine look at the “laws” that govern its behavior and decide that they, too, are not what they ought to be and therefore can sometimes be ignored?
 Would the machine view its creator(s) as being deficient? In particular, would the machine complain that the creator made a world it didn’t like, not realizing that this was essential to the machine’s survival and growth?
 Would the machine know if there were absolute, fixed “goods”? If so, what would they be? When should improvement stop? Or would everything be relative and ultimate perfection unattainable? Would life be an inclined treadmill ending only with the final failure of the mechanism?
Of course, this is all speculation on my part, but perhaps the reason why God plays dice with the universe is to drive the software that makes us what we are. Without randomness, there would be no imagination. Without imagination, there would be no morality. And without imagination and morality, what would we be?
Whatever else, we wouldn’t be driven to improve. We wouldn’t build machines. We wouldn’t formulate medicine. We wouldn’t create art. Is it any wonder, then, that the Garden of Eden is central to the story of Man?
[1] Taken from “Programs with Common Sense”, John McCarthy, 1959. In the paper, McCarthy focused exclusively the second point.
Empathy for a Serial Killer
08/01/10 06:49 PM Filed in: Christianity  Life
Dexter is the eponymous character of the Showtime television series. He is a father, husband, and forensic analyst for the MiamiMetro Police Department. He is also a serial killer. Dexter is a dark and violent show that nevertheless has important things to say about human nature. In many ways, it is a "protoChristian" work.
This will be illustrated after the break with quotations taken from the fourth season of the show. Warning: graphic language and spoilers follow. Read More...
This will be illustrated after the break with quotations taken from the fourth season of the show. Warning: graphic language and spoilers follow. Read More...