First, the intro video that got me thinking about this in the first place…
i7sm9dzFtEI
For those too lazy to go through that video, this topic is about Ackermann’s function. Literally a function to prove that even computing has its limits. The recursive case in Ackermann’s function is pretty simple and can be written in a few lines of code.
public class ackermann {
public static void main(String[] args){
for(int i = 0; i < 6; i++){
for(int j = 0; j < 6; j++){
System.out.printf("ackerman (%d, %d) is: %d\n", i, j, ack(i, j));
}
}
}
private static int ack(int m, int n){
int ans;
if (m == 0)
ans = n+1;
else if (n == 0)
ans = ack(m-1, 1);
else
ans = ack(m-1, ack(m, n-1));
return ans;
}
}
However, this does a number on processing machines, with A(4,2) taking ages to compute on even the most powerful machines. (With Java, I had to do a bit more to avoid stack overflow errors…) I think before we even think about tackling the universe, I’m actually curious about how deep into Ackmermann’s function we can calculate today before our computer’s die from the processing strain. No matter how much I optimized, we just couldn’t think of a good way to calculate past A(4,2)…
Any thoughts or takers?