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.

Article Navigation

Comments (79)
Tags: study_group

Comments (79)

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

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.

Powered by Reddit Powered by Reddit