How long can a Turing machine program run when started on the blank tape before the tape becomes blank again? Of course, this will depend on the length of the program – how many states and colors it has. Even given these parameters, it is logically impossible to calculate how long a self-cleaning Turing machine can run. Any values that can be known have to be discovered empirically.| Something Something Programming
The classic Busy Beaver game asks how long an n-state k-color Turing machine program can run before executing a halt instruction. The phrase “executing a halt instruction” is not normally used in stating the problem; instead, people just say “halting”. But executing a halt instruction is just one way for a program to signal that it is finished. From the point of view of a programmer trying to maximize machine steps, it’s about the worst termination signal possible because it require...| Something Something Programming
SCENARIO: It’s 1950, and a brand new Turing machine, the first of its kind, has been installed at a research facility. Lots of people want to use it, but the machine has just one tape. A program’s execution can be affected in undesirable ways by data left over on the tape from a previous program run, and so as a matter of etiquette the convention is adopted among the machine’s users that the tape is to be wiped clean after each use. Rather than cleaning the tape manually after program e...| Something Something Programming
🚰 This post is a continuation of “Halt, Quasihalt, Recur”. 🚰| Something Something Programming
Recently I found an interesting Turing machine program. When started on a blank tape, it runs for more than 101565 steps before halting. Here it is1:| Something Something Programming