ata comments on Book Club Update and Chapter 1 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (79)
It occurs to me that Jaynes is missing a desideratum that I might have included. I can't decide if it's completely trivial, or if perhaps it's covered implicitly in his consistency rule 3c; I expect it will become clear as the discussion becomes more formal -- and of course, he did promise that the rules given would turn out to be sufficient. To wit:
One more thing. The footnote on page 12 wonders: Does it follow that AND and NOT (or NAND alone) are sufficient to write any computer program?
Isn't this trivial? Since AND and NOT can together be composed to represent any logic function, and a logic function can be interpreted as a function from some number of bits (the truth values of the variable propositions) to one result bit, it follows that we can write programs with AND and NOT that make any bits in our computer an arbitrary function of any of the other bits. Is there some complication I'm missing?
(Edited slightly for clarity.)
You can use NAND to implement any algorithm that has a finite upper time bound, but not "any computer program", since a logical formula can't express recursion.
Electronic NAND gates have a nonzero time delay. This allows you to connect them in cyclic graphs to implement loops.
You can model such a circuit using a set of logical fomulae that has one logical NAND per gate per timestep. Ata pointed out that you need an infinitely large set of logical formulae if you want to model an arbitrarily long computation this way. Though you can compress it back down to a finite description if you're willing to extend the notation a bit, so you might not consider that a problem.
I agree that you are correct. Thank you.