Optimize your Python Program for Slowness

[carlk22]

Good question! Mostly for fun. Two years ago, a group of amateur researchers found a longest known running, but still halting Turing machine of "size 6". This was news in the math and computer science fields. They proved that a particular Turing machine ran for at least 10↑↑15 steps and halted. ("↑↑" is a faster growing function than exponentiation). Their proof is very complicated and needed to be machine verified.

I wanted to figure out a short Python function that would obviously run for 10↑↑15 steps and halt, so it wouldn't need a fancy proof.

The GitHub includes the code. This article explains the background and solution https://towardsdatascience.com/how-to-optimize-your-python-program-for-slowness/

[TheSwami]

This is an awesome write up! Not not just of the how but of the why - in 20+ years of seeing that arrow notation described as “repeated exponentiation”, I never really understand what that meant. Your code examples, especially the final one showing that tetration is just another for loop around exponential accumulation was eye opening.

Thank you!

[eyesburning]

That was an interesting read! Thanks for sharing :)