I am pleased to announce that I was able to add a new feature to the Rust Clippy linter. Namely: the use_self lint will now notify that the Self keyword can be used in recursive type definitions. This feature is now officially available in the Nightly release. Hip hip hooray.| Something Something Programming
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 Busy Beaver question asks how long a Turing machine program of a fixed length can run before halting (or more generally, reaching some particular condition). The question was first posed in 1962. It didn’t take long for researchers to realize that solving this question for any non-trivial case would require the use of computers. Sometimes they named the specific hardware they used. This post is a list of all the computers I have seen mentioned in the literature.| 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
Suppose someone claims that a particular Turing machine program halts when run on the blank tape. How can this claim be verified? The obvious answer is to run it on the blank tape and see if it halts. But what if the program in fact does not halt? The verifier will be stuck running a non-halting program, waiting forever for a halt that will never come.| Something Something Programming
🚰 This post is a continuation of “Halt, Quasihalt, Recur”. 🚰| Something Something Programming
The goal of the Busy Beaver contest is to find n-state k-color Turing machine programs that run for as long as possible before halting. It’s basically an optimization problem: what is the longest finite computation that can squeezed out of a program of a certain length? Or from the flip-side: how much description can be packed into a program of a certain length?| Something Something Programming
The Busy Beaver problem asks: among n-state halting Turing machine programs, which one runs the longest? The function BB(n) is famously uncomputable, since calculating it in general would require solving the halting problem. It grows with spectacular speed:| Something Something Programming
Turing machine programs are sometimes represented as directed graphs. The vertices of the graph are the program’s states and the edges are transitions between states. The program’s print and shift instructions are relegated to being labels for the edges. Here’s an example:| Something Something Programming
I have to admit it’s getting better A little better all the time – Lennon-McCartney| 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
Mostly thoughts about programming. Maybe other stuff too.| Something Something Programming
The aim of the Busy Beaver game is to find the longest running Turing machine program of n states and k colors. Busy Beaver programs could in principle be written by hand, but nobody has ever succeeded in doing so. Instead, these programs are discovered through exhaustive search. This is done by a two-stage process:| Something Something Programming
In the Busy Beaver game we ask: what is the longest that a Turing machine program of N states and K colors can run before halting when started on the blank tape? Answering this question requires enumerating every such program and checking whether or not it halts. But there is a big problem: there are just too many to check. The number of programs grows multiple-exponentially with N and K, O(nknk). Yikes!| Something Something Programming
In the classic Busy Beaver game we ask: what is the longest that a Turing machine program of N states and K colors can run before halting when started on the blank tape? The basic approach to solving this problem is to generate a list of candidate programs, then subject each program to a sequence of deciders, where a decider is a function that takes a program as input and returns a result of type Option. This result is interpreted as follows:| Something Something Programming
I have some Rust code that does a bunch of pure computation. A lot of it. To solve basically an elaborate combinatorial problem.| Something Something Programming
The other day I found a cool new 3-state 3-color Turing machine program. Here it is:| Something Something Programming
Mypy is a typechecker for Python. It’s not the official typechecker for Python. There is no official typechecker. But Mypy seems to be the official-est. I use it, and it’s mostly pretty great.| Something Something Programming
when i use haptpt i dont make any effort to dlean up the tesxt i just taype the baer minimum amount of information needed to communicate what i need. i leave in all the typos, dont bothwe with caps, very little pucnutation. franktly the text looks like shit.| Something Something Programming
Print debugging is the technique of debugging by inserting print statements into code and watching their output. For example, if my program seems to be getting stuck somewhere, I might put in some print statements like this:| Something Something Programming
Multiplication is repeated addition: 2 * 5 is defined as 2 + 2 + 2 + 2 + 2.| Something Something Programming