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.
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.
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.
Does that mean that digital-eletronic NANDs which could be used to build flip-flops, registers, etc. cannot be expressed in a logical formula?
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.