Top all-time · #2848
Something Something Programming
Personal blog · nickdrozd.github.io · on HN as nickdrozdprogrammingmath
Something Something Programming is a personal blog at nickdrozd.github.io about programming and math. Since 2018, 25 different Hacker News readers have linked it 98 times, most often “Turing Machine Notation and Normal Form”. It is still writing: the last post was on 2026-10-20, and you can follow it by feed.
Too few sampled comments (11) to say how often HN recommends it.?
Why HN links it
HN readers link these posts for explanations of Busy Beaver Turing machines, canonical Turing machine notation and the spaghetti code conjecture. They are cited as references in threads on busy beaver results.
Summarised by Claude from a sample of 11 HN comments that link here. Each comment is marked recommending, critical or neutral (citing without judging); how this works.
Mostly thoughts about programming. Maybe other stuff too.
Most-linked posts?
- Turing Machine Notation and Normal Form4 people · 4 mentions · first linked 2020-10-04
- A New Record in Self-Cleaning Turing Machines3 people · 3 mentions · first linked 2021-07-12
- Signed Char Lotte3 people · 3 mentions · first linked 2021-03-30
- I Got a Knuth Check for 0x$3.003 people · 3 mentions · first linked 2019-05-18
- Maybe the spaghetti code conjecture is false2 people · 4 mentions · first linked 2021-09-25
- Halt, Quasihalt, Recur2 people · 2 mentions · first linked 2021-01-15
- Beeping Busy Beavers2 people · 2 mentions · first linked 2020-08-14
- Are Turing Machines Programmable?2 people · 2 mentions · first linked 2020-09-15
- Basic Web Scraping with Emacs2 people · 2 mentions · first linked 2018-10-20
- Emacs Lisp Challenge: flaky-if2 people · 2 mentions · first linked 2019-11-24
What Hacker News says?
Ha, the funny thing is, there are conjectures both ways! Some people think winners get noisier and noisier, the spaghetti code conjecture. Others actually think the winners get cleaner and cleaner, the clean code conjecture. Personally, I am slightly leaning towards clean code being more powerful. Chaos is hard to control. https://nickdrozd.github.io/2022/03/12/formal-theory-of-spag...
Comment linking /2022/03/12/formal-theory-of-spaghetti-code.html
on “With fifth busy beaver, researchers approach computation's limits”Submitted Signed Char Lotte as a story · 677 points
HN discussionI found this quite helpful: https://nickdrozd.github.io/2020/10/04/turing-machine-notati... Despite a CS undergrad I don’t recall really learning any of these canonical representations of TMs before.
Comment linking /2020/10/04/turing-machine-notation-and-normal-form.html
on “BB(3, 4) > Ack(14)”Submitted I Got a Knuth Check for 0x$3.00 as a story · 469 points
HN discussionCounting the number of distinct TMs is not a simple task. The way you count it is the most broad (the count of all tables of values where each cell can have any (symbol, direction, state) combination). But this is a significant overcount of the bits needed to describe an arbitrary TM. for the BB(3, 4) case, there are only about 600B distinct TMs using the Tree Normal Form aka Brady's algorithm ( https://nickdrozd.gi…
Comment linking /2022/01/14/bradys-algorithm.html
on “BB(3, 4) > Ack(14)”Submitted Maybe the spaghetti code conjecture is false as a story · 111 points
HN discussion> streetlamp effect I agree completely, all of these kinds of conjectures are shaped by what is detectable. If there are any "dark matter" programs out there, they by definition will be difficult to find. That said, I find it entirely plausible that the champions will win by exploiting complex and exotic mathematical facts, while the implementations of the math do not themselves need to be complex or exotic at the c…
Comment linking /2021/09/25/spaghetti-code-conjecture-false.html
on “BB(3, 4) > Ack(14)”Submitted New Ways to Be Told That Your Python Code Is Bad as a story · 102 points
HN discussionDependent types are very cool and very frustrating. Once you get it, it opens up a whole new way to express program behavior; but until then, it all seems like pointless busywork. The Little Typer is somewhat tougher to get through than other Little books because the benefits of the paradigm it explains aren't apparent until you understand everything. For anyone struggling to make sense of it, I suggest looking at t…
Comment linking /2019/08/01/little-typer.html
on “The Little Typer (2018)”Submitted A Formal Theory of Spaghetti Code as a story · 99 points
HN discussionThe OEIS is an amazing tool. I recently came across a sequence from an unusual source and then made the shocking discovery that the sequence already existed. It turned out to be a wild coincidence. Write-up here: https://nickdrozd.github.io/2021/04/12/math-fact-busy-beaver...
Comment linking /2021/04/12/math-fact-busy-beaver.html
on “The On-Line Encyclopedia of Integer Sequences”Submitted A Busy Beaver champion derived from scratch as a story · 99 points
HN discussionEWW is a little too austere for general browsing IMO, but it's more than useful enough to make up for it in a few situations. 1. Copying large sections of text. Say I'm reading a tutorial or something with code blocks, and I want to run them. If I'm in a "real" browser, I have to click and drag to copy the text to my editor, and clicking and dragging sucks. Instead, I can open the page in EWW, then set the mark and…
Comment linking /2018/10/17/web-scraping.html
on “EWW: Emacs Web Wowser”Submitted Another new record in self-cleaning Turing machines as a story · 90 points
HN discussionHe is still working on it and the latest check I know about was from a few months ago: https://nickdrozd.github.io/2019/05/17/knuth-check.html but I still agree with your first sentence.
Comment linking /2019/05/17/knuth-check.html
on “Request Node lib used by 48k modules is now deprecated”Submitted Basic Web Scraping with Emacs as a story · 62 points
HN discussionTo know whether you'd enjoy it (which is the only measure of “worth it” I can think of in relation to this book), you could start with one of the recent sections on combinatorial algorithms (Volume 4A and part of Volume 4B have been published so far): http://www.cs.utsa.edu/~wagner/knuth/ For example, 7.2.1.2 on generating all permutations ( http://www.cs.utsa.edu/~wagner/knuth/fasc2b.pdf ) has a lot of cool mathema…
Comment linking /2019/05/17/knuth-check.html
on “Ask HN: Is the “The Art of Computer Programming” Worth the Investment?”Submitted The Story of XEmacs (2019) as a story · 48 points
HN discussion> Down here at BB(6) you can feel fairly sure the machine doesn't express anything inherently problematic because it's just too simple. One of the shocking results of Busy Beaver research is that this is actually false. Even with as few as four states there are machines that are complicated and difficult to understand. Turing machine "states" are really GOTO targets, and with six states it's possible to create contr…
Comment linking /2021/09/25/spaghetti-code-conjecture-false.html
on “Busy Beaver Updates: Now Even Busier”Submitted Turing Machine Notation and Normal Form as a story · 28 points
HN discussionthis is a cool link, not an ELI5, but https://nickdrozd.github.io/2020/10/04/turing-machine-notati...
Comment linking /2020/10/04/turing-machine-notation-and-normal-form.html
on “Cryptids”Submitted A better Turing machine tape model as a story · 23 points
HN discussionThe machines used in the article don't have to halt whereas the busy beaver only admits Turing machines that halt. For the purpose of this article the Turing machine either has to halt or has to enter some kind of degenerate state where it can still technically run forever but is in some sense stuck in a trivial infinite loop. The precise details of this degenerate state are explained in this article: https://nickdr…
Comment linking /2021/01/14/halt-quasihalt-recur.html
on “A Busy Beaver champion derived from scratch”Submitted Chinese Characters and Dictionaries as a story · 19 points
HN discussionGreat writeup! I ended up following a few of the links and came across perhaps my favorite hand waving of all time for the validity of "The Spaghetti Code Conjecture"[1]. Basically: For N=0,1: the problem is trivaial/degenerate. For N=2: the Turing machine must go back and forth between states or else it'd just be stuck in one state forever, which wouldn't be very busy beaverish. For N=n+1: well we just proved it up…
Comment linking /2021/01/26/spaghetti-code-conjecture.html
on “A Busy Beaver champion derived from scratch”Submitted Some Advice for How to Make Emacs Tetris Harder (2019) as a story · 14 points
HN discussionThis should help: https://nickdrozd.github.io/2020/10/04/turing-machine-notati...
Comment linking /2020/10/04/turing-machine-notation-and-normal-form.html
on “Striking new Beeping Busy Beaver champion”Submitted Idris Algebra as a story · 11 points
HN discussionIt turns out that a different post has a good answer! https://nickdrozd.github.io/2021/09/25/spaghetti-code-conjec...
Comment linking /2021/09/25/spaghetti-code-conjecture-false.html
on “Another new record in self-cleaning Turing machines”Submitted The Shape of a Turing Machine as a story · 5 points
HN discussion
