Back in my first year of University I was enrolled in a course called COMP1917. It was an excellent course taught by Richard Buckland and I enjoyed it very much. It was also the exact course in which they taped the famous YouTube video lectures; I look back on those lectures with pride. The purpose of this course was to introduce students to computer science and teach them about the fundamentals that they simply must know. To that end we were taught C as our primary language (a common choice) but we were also given an emulator for an imaginary microprocessor called a “4917 chip” which I will call a “4917” for short. This blog post is going to focus on that chip.
The imaginary 4917 was a tiny device. It had sixteen nibble sized memory locations and sixteen different instructions. All instructions were either one or two nibbles in size. I hope you notice that this entire machine worked in nibble sized chunks. It also had only two working registers called R0 and R1; it also technically had a program counter that you manipulate with instructions 13-15. The instruction set of this device is here:
Instruction in decimal => What the instruction does
One Byte Instructions:
0 => Halt Program
1 => R0 = R0 + R1
2 => R0 = R0 – R1
3 => R0++
4 => R1++
5 => R0- –
6 => R1- –
7 => Ring Bell (Nothing really [Side Effect])
Two Byte Instructions:
8 x => Print x to the output device; maybe a screen but it did not matter because this device is imaginary.
9 x => Load value at location x into R0
10 x => Load value at location x into R1
11 x => Store value in R0 into location x
12 x => Store value in R1 into location x
13 x => Goto x
14 x => If R0 == 0 Then Goto x
15 x => If R0 != 0 Then Goto x
It is actually quite a nice little instruction set. You can even write a quine in this 4917 machine.
But what am I even getting at I hear you ask? Well it goes like this, Richard Buckland posed a question to us that said:
I have a bonus question for you. For every different length program, I want you to create/write a program that will print out the most characters that you possibly can to the screen and still terminate. That is you cannot write a program like “8 0 13 0” which will print ‘0’ forever. That program is incorrect because it will never terminate.
And with that the battle was on, if you wrote a program in 4917 that printed out the most characters for that program length, that anybody had found yet, then you gained one ‘brownie point’. Brownie points are tallied up at the end of the session and the person with the most wins. (Spoiler Alert: I had the most brownie points at the end of that session; by far.) You should also know that the length of a program is calculated as 16 – NUM_TRAILING_ZEROES. That means that you must count all of the memory spaces that you actually needed to write to.
Those of you that are clever would have realised that Richard was teaching the class a valuable lesson; and also, quietly, having a laugh at our expense – but I mean that only in the best way, right now I am laughing right there with him. The problem with this problem, as it were, is that you cannot write a fast program to find the best program for you. Any algorithm that attempted to do so would need to ensure that it eventually terminated; and to do that you need to solve the Halting Problem. Haha Richard, very funny, try and get the first years to solve an impossible problem so that they learn the value of computing theory; actually it was quite a good move in retrospect. It teaches a good respect of theory.
Hovewer, we are also Engineers, and as with most problems this one can be partially solved using brute force methods. You can write your own emulator, count the number of characters that get printed to the screen, and include a timeout for programs that go for too long and are thus deemed “probably infinite”. And that is what this post is really about; me writing a brute force solver to this problem on a PicMicro device for sentimental value.
Past Results and My New Sentimental Solution
At the time of the course I wrote a brute force solver, using some code (an emulator) written by Brett Phillips, and ran it on my laptop (RIP Dell XPS M1710) and on increasingly large program sizes to find the best finite program. These were my results:
program_size: program bytecode => number of printed digits
4: 3 8 10 15 => 32
5: 4 1 8 10 15 => 62
6: 4 8 8 13 2 15 => 93
7: 1 8 10 14 4 1 15 => 172
8: 1 8 10 14 4 2 4 15 => 482
9: 1 3 8 10 15 1 4 2 15 => 512
10: 1 8 8 15 6 8 13 2 5 15 => 1173
11: 1 3 8 10 8 10 15 1 4 2 15 => 1024
And that earned me 8 brownie points in one hit. I was never able to get a solution for the higher values because it would have required me to leave my laptop on for around a week or two for a program of size 12 and much more for the others; class and the exams would have passed before I had an answer.
However, in recent days, for nostalgic purposes, I have engaged the problem again and I am pleased to say that I have written a number of implementations but the ‘best’ one of all would have to the the Microchip PIC16F688 version which I will display for you now via youtube:
This is awesome and makes me very happy. You can find the code for this device on Github. It should be pretty easy to recreate and pretty cheap to buy the parts for.
I enjoyed my time at University very much and I was very happy to have been there. I loved every minute of it and met amazing people and this little tribute is my offering to my time there. To have something to remember it by. A big thanks to Richard for the awesome course and 4917 problem, and also to all of my peers that made it an awesome time. I hope you enjoy this little project and my story.