ata comments on Book Club Update and Chapter 1 - Less Wrong

15 Post author: Morendil 15 June 2010 12:30AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (79)

You are viewing a single comment's thread. Show more comments above.

Comment author: cata 16 June 2010 05:47:08AM *  1 point [-]

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:

  • The robot should not assign plausibilities arbitrarily. If the robot has plausibilities for propositions A and B such that the plausibility of A is independent of the plausibility of B, and the plausibility of A is updated, then the degree of plausibility for B should remain constant barring other updates.

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

Comment author: ata 16 June 2010 08:14:19AM *  5 points [-]

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?

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.

Comment deleted 16 June 2010 03:04:14PM [-]
Comment author: pengvado 16 June 2010 04:18:28PM *  1 point [-]

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.

Comment author: cata 16 June 2010 01:28:43PM 0 points [-]

I agree that you are correct. Thank you.