This blog is about Simon, a young gifted mathematician and programmer, who had to move from Amsterdam to Antwerp to be able to study at the level that fits his talent, i.e. homeschool. Visit https://simontiger.com
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?
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.
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 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,
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).