# Simon’s Halting Problem Gist

You can easily turn every statement into a program. If the program stops, or “halts”, then the statement is true, and if it never stops, or “loops”, the statement is false.

Like, for example, the following program corresponds to the statement: “There’s at least one even number that cannot be expressed as the sum of two primes” (this is the negation of the so-called “Goldbach Conjecture”):

So, if we can figure out if any program will halt or not halt, we can prove everything! Can we do that, though?

# Too Many Twos Solution Proof

Simon has come up with an equation to solve the Too many Twos, the puzzle mode of the Add ‘Em Up game:

x is the number of twos I used to clear out just a single two at a time

y is the number of twos I used to clear out six twos at once.

We have two pieces of information. At the beginning, the twos are arranged in a pattern with 40 twos in it. And the number of twos I can use to clear out the whole grid is 25.

x + 6y = 40

x + y = 25

We thought we solved it, but no! The reason why is because of the way the twos are arranged there were spots where there were exactly 6 twos neighbouring an empty cell. And there was only one spot where there wee more than 6. Our equation says that there must be 3 of those. the way I solved this problem was by considering a third variable, z = the number of twos that I place without clearing any twos in the grid. So now our two equations look like this:

x + 6y – z = 40

x + y + z = 25

With a little bit of cleverness though, we know that these are all integers. You don’t have 2.7 twos! That doesn’t exist! Which means that we can use some number theory to narrow it doen. After solving these equations we get: x = 25 – y – z and y = 3 + 2z/5

We’ve got a fraction. We need to carefully choose the z for this to result in an integer! This is only true if z is divisible by 5.

I don’t want to check infinitely many solutions. Luckily, we know one more quite obvious thing: all of our variables must be positive. So if z gets too large, x will become negative. How large? Let’s just be lazy and use trial and error. Let’s draw a table. In our table we now only have four solutions that we need to check. The first one, with 0 z‘s, clearly doesn’t work.

# Solving Logical Puzzles

The end of 2019 was packed with logic. Simon even started programming an AI that would solve logical puzzles, here is the beginning of this unfinished project (he switched to programming a chess AI instead). In the two vids below, he explains the puzzle he used as an example and outlines his plan to build the AI (the puzzles come from Brilliant.org):

And here are some impressions of Simon working on the puzzles and showing them to his sis:

# Simon building an 8-bit Computer from scratch. Parts 1 & 2.

Parts 1 and 2 in Simon’s new series showing him attempting to build an 8-bit computer from scratch, using the materials from Ben Eater’s Complete 8-bit breadboard computer kit bundle.

Simon is learning this from Ben Eater’s playlist about how to build an 8-bit computer. these little black things are an inverter (6 in one pack), AND gate and OR gate (4 AND and OR gates in one pack) this schematic represents the clock of the future 8-bit computer Simon and Neva thought the register with its LED lights resembled a birthday cake

# Simon has been bitten by the hardware bug again!

It’s all Ben Eater‘s fault! Simon is more of a software and pure math champion, but Ben Eater’s videos have sparked Simon’s interest in logic and electronics, anew. Back in mid July (yes, I know, I’m a little behind with the blog), while waiting for his Complete 8-bit breadboard computer kit bundle to arrive from the US, Simon was playing with virtual circuits that he built on two wonderful platforms: Circuitverse.org and Logic.ly. You can view Simon’s page on Circuitverse at https://circuitverse.org/users/7241

Simon’s favourite was building the Master-Slave JK Flip-Flop https://circuitverse.org/simulator/edit/20037

Simon gave me a whole lecture on the differences between Sequential and Combinational Logic: in the former, there’s a presence of a feedback loop (the output actually goes back to somewhere else in the circuit), and the latter has everything going in one direction (the inputs come in and the outputs go out).

It’s a little bit like the difference between a Feed Forward neural network where the output only depends on the input and a recurrent neural network where the output also depends on what the output was previously,

Simon explained.

Here’s a problem with sequential logic circuits: they go crazy like this very often (confused NOR gate). That’s why most sequential logic circuits have a clock in them. A clock acts like a delay so that it won’t go crazy.

That’s the power of sequential logic: you can have the same input but a different output. This is useful for storing data: I release the input, but the data is stored. It can only be archived in sequential logic.

The delay comes in error detection (on the rising edge of the square wave).

The following circuits are buit in Logicly https://logic.ly/demo

# MathsJam 19 March 2019

What a monstrous logic problem, this was just too much to crack.    