Igor Ostrovsky Blogging

As promised at the end of my recent post, I am going to explain how to implement a program that prints itself, in addition to doing other things (like playing Game of Life).

A self-printing program - also called a quine - is a program that prints out its own source code. I will describe one simple way to implement a quine that can be adapted to just about any programming language. The technique does not depend on any unusual language features, but also does not necessarily yield the shortest possible quine in a particular language.

The main idea behind this quine implementation is simple. The quine will consist of two parts: a definition of a string and the program core. The string will contain the source code of the program core. And, what will the program core do? It will print the string twice: once to print the string definition, and again to print the program core.

Continue reading »

Conway’s Game of Life has fascinated computer scientists for decades. Even though its rules are ridiculously simple, Conway’s universe gives rise to a variety of gliders, spaceships, oscillators, glider guns, and other forms of “life”. Self-printing programs are similarly curious, and - rather surprisingly - have an important place in the theory of computation.

What happens when you combine the two? You are about to find out, but one thing is for sure: the geekiness factor should be pretty high.

I wrote a little C# program that contains a Game-of-Life grid. The program advances the game grid to the next generation and prints out a copy of itself, with the grid updated. You can take the output, compile it with a C# compiler, run it, and you’ll get the next generation of the game. You can iterate the process, or change the initial grid state manually.

Continue reading »

Did you know that there are numbers that cannot be computed by any computer program? It is weird, but true.

And by number, I mean just an ordinary real number. As a perhaps unnecessarily simple example, the result of the division 1/7 looks like this:

        0.1428571428571428571428571428571414285714285714285714285714285714…

We can easily implement a program that prints this number. The decimal expansion of 1/7 is infinite, so the program will have to run in an infinite loop to print the “whole” number. Here is a C# implementation:

    static void Main()
    {
        Console.Write(“0.”);
        while (true) Console.Write(“142857″);
    }

Continue reading »