Clarity on Universal Machines

[kinsomicrote]

Hello Sandy, first I must appreciate you for taking the time to write the book you have on your blog. I write technical articles, so I know it's not an easy feat - writing a book is much more. Reading your book has helped unblock in a book (Computer Science Distilled) I was reading. I created this issue to seek clarity on what you have on Universal Machines, where you wrote about combining logic gates.

I've been having a hard time figuring out how you arrived at the outputs for the combined logic gates below;

Since I was a beginner on this topic I decided to learn more in order to fill up necessary gaps so I could understand what you were doing. However, that didn't help me arrive at the same result you had. Here is what I was able to come up with.

I was wondering if you could help explain or point me to what I am missing or give me some sort of hints.

Thanks.

[isovector]

I think you might have found an error in the book; I was trying to write a chapter a day, and, IIRC, that section had some issues I never got around to fixing (assuming, apparently incorrectly, that nobody would ever read this thing.)

As it happens, I'm actively working on an entire rewrite of the book; building the entire machine, and with a computer-verified implementation to ensure problems like these don't spring up.

Thanks for reading, and for the bug report --- sorry to have wasted your time trying to understand a mistake in the source text!

[isovector]

I find it hard to think about this stuff, so I ran the examples through my new verifier, and I get these results. For the first machine (first' notGate >>> andGate >>> notGate), the truth table is

(1, 0) -> 1
(1, 1) -> 1
(0, 1) -> 0
(0, 0) -> 1

and for the one with not gates on either input wire (both notGate >>> andGate >>> notGate):

(1, 1) -> 1
(1, 0) -> 1
(0, 0) -> 0
(0, 1) -> 1

which means the tables as given in the book are correct. So what's going on?

In your first diagram, we get the same truth tables. In the second, you are forgetting a not gate where Z is :)

[kinsomicrote]

Yeah, that's true, I'm forgetting the last not gate. Thanks for pointing that out.

However, in the first composed logic gates, it looks like your truth table swaps the output of 1, 1 with the output of 0, 1. This is different from what you have in the response you have above, where the output of 1, 1 is 1 and the output of 0, 1 is 0. Is that correct?

[kinsomicrote]

Also, I'm curious to know if/how I can help out in the current rewrite. The linked repo seems to use Haskell, I have no experience with it though.

[isovector]

I don't see the discrepancy you're trying to point me towards, sorry! In this table:

in the leftmost column, there are crossed out values with an arrow towards new values. The crossed out values are the inputs as they were before introducing the not gate on the A input. After putting the not gate there, the rest of the circuit stays the same; all that changes is the "effective" A input to the circuit. This new effective input is described with an arrow pointing at the NOT of the old value.

That is to say, if we're looking at ~1~ -> 0, the effective input to the circuit is 0.

In the table I gave above:

(1, 0) -> 1
(1, 1) -> 1
(0, 1) -> 0
(0, 0) -> 1

I unwisely decided to use the same arrow notation to mean something different. Here, this should be read as (A, B) -> Output. When looking at this truth table, it's the same as both the table given in the book (when looking at the effective input A), and it's also the same as your truth table (though our rows are in different orders.)

Does that help? Am I still missing something?

[isovector]

I'm curious to know if/how I can help out in the current rewrite.

That's an extremely generous offer, thank you @kinsomicrote! At this point in time, you are more familiar with the book as it exists today than I am; perhaps the most help you can be right now is to file bugs for anything that isn't immediately clear. If a concept or paragraph takes more than 5 minutes to do, it's probably because I am bad at writing, and that's the sort of stuff I can't check for myself. I'm extremely grateful for this bug report, and for any others you might think to send my way!

The linked repo seems to use Haskell, I have no experience with it though.

If you're looking for a life-changing experience, learning Haskell will dramatically change the way you think about software.