Ken-Soft

This is an implementation of the 2 argument version of the Ackermann Function (i.e. Ackermann-Péter function). In essence, this is an example of a very simple recursive function is an example of a total computable function that is not primitive recursive. Instead of making the internet even more redundant with unnecessary text, just click the above link to view the entire Wikipedia article.
Function’s like these are very fun to play with. I often think about the human brain and how it functions when I see these kinds of functions. Taking input from the environment and processing it, sometimes recursively (like in a thought cycle), then converging to some or many outputs.
C Implentation:
noteThis function grows extremely fast, such that it quickly out grows any primitive type in C, including the largest “unsigned long long” type. Though the program will likely crash with a 0xC0000005 error from too much recursion
It should run fine from A(0,0) to A(4,0) and likely crash while computing A(4,1), which is 65533. A(4,0) is 13, so the number of recursive calls jumps up enormously! I will be working on a custom, larger data type as well as a way around the error caused by too much recursion.

1
2
3
4
5
6
7
8
9
10
11
12

/**
 * Ackermann function - recursive implementation
 */
unsigned long long A(unsigned long long m, unsigned long long n) {
    if(m == 0) {
        return n + 1;
    }else if(n == 0) {
        return A(m - 1, 1);
    } else {
        return A(m - 1, A(m, n - 1));
    }
}

The entire source implentation can be found here
I obtained a list of some of the expected values from this site -> http://www-users.cs.york.ac.uk/susan/cyc/a/ackermnn.htm
Here are some of the values for 0 < m < 5, 0 < n < 6

Some of the patterns formed are very amazing. For example: A(2, n), 0 <= n < infinite, will list odd numbers starting from 3 to infinite.
To demonstrate this just insert the below loop into your code:

1
2
3

for(int n = 0; n < 100; n++) {
      std::cout << "A(2, " << n << ") = " << A(2, n) << std::endl;
}

I was randomly surfing around the internet when I stumbled upon Google Labs Aptitude Test (GLAT)(Found here). I can’t really remember which links I followed from there but I stumbled into a question that asks to find the first 10 consecutive digits of E that are prime. While definitely not a hard task I wrote a small program in C to test whether or not a number is prime.

The core function isPrime() is below

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

long long isPrime(long double n) {
    // is n an integer ?
    if(n / (long long) n != 1.0) {
        return -1;
    }
    // is n even? (half of the numbers)
    if((long long)n % 2 == 0) {
        if(n == 2) {
               return 0;
        }
        return 2;
    }
    long long root = sqrtl(n);
    // is the number divisible by n, such that n > 2 and n <= sqrt(number)?
    // if so then the number is composite
    for(long long i = 3; i <= root; i++) {
        if((long long) n % i == 0) {
            return i;
        }
    }
    return 0; // it is prime!
}

note: I use long long just to allow the calculation of bigger numbers. Though if the number gets to large enough this algorithm can still slow down a bit, as it could potentially have to iterate from 3 to the square root of the number being tested. For most cases this algorithm executes plenty fast enough and it is definitely better than iterating over every number between 1 and N, as many sites do.
the entire implementation is here:main.cpp

I’ve always been interested in AI, evolution simulations, and other interesting problems. But I will never forget one of my all time favorite classics, John Conway’s Game of Life..
This simulation implements a few just a few simple rules, yet relatively complex structures emerge.
The rules are:
1. Any live cell with fewer than two live neighbors dies, as if caused by underpopulation.
2. Any live cell with more than three live neighbors dies, as if by overcrowding.
3. Any live cell with two or three live neighbors lives on to the next generation.
4. Any dead cell with exactly three live neighbors becomes a live cell.

Below are some of the patterns that I found and thought were interesting:

After watching many trails I noticed one thing immediately; The simulation always eventually “dies down”, or reaches some equilibrium state and it is usually comprised of a bunch of simple structures. So I decided to add a mutation factor to the simulation such that upon mutation, A living cell dies and a dead cell comes to life. This significantly increased the life of the simulation. In fact with the right mutation rate the simulation will continue endlessly.

In my quick little simulation I also introduced a “wrap around” feature so that structures can move infinitely in any direction.

The demo is written in C and uses the SDL Library for drawing the points and is in 640×480 resolution. The source can be downloaded here.
To Compile:
g++ main.cpp -o LIFE -lSDL
To Run:
./LIFE

Every thing from mutation rate to cell generation at startup is configurable. Read the ReadMe.txt file included to see what’s configurable.

Screenshots:

Notice that the 3rd Image is a result of changing rule 4 to ” Any dead cell with two or three live neighbors becomes a live cell.” (I made this typo when first writing the program and was surprised by the result :)) Try changing the rules and see what results you find.
I hope to release a more complex version in the future.