The paper "Making Turing machines useful (Or, how I got Doom to run on a Turing machine)" builds a Turing machine to run Doom (duh), by implementing a RISC-V (RV32I) emulator. While in Sigbovik fashion the utility of the exercise is far outshined by its complexity, there's a number of interesting choices regarding much of what are usually handwaved away regarding tape and state management. To be fair, TM have far less utility as real programming languages than lambda-calculi do, so it's common for professors to dismiss any attempt to optimize TM programs -- which is a root of evil. Since evil is also the source of doom, everything converges here.

> In this paper, we introduce NEURALATEX, which we believe to be the first deep learning library written entirely in LATEX.

Right, that's enough computers everyone. Back to books.

ccdoom is delightfully impressive. It's a compiler compliant with the C standard, which outputs DOOM (the word, and the game) for all programs.

> ccdoom is a freestanding C implementation, as distinct from hosted implementations. The difference is that freestanding implementations need not support the full standard library, and may specify an alternative name and signature for main [2, Section 5.1.2.2].

> int math_errhandling(int argc, char* argv[]);

> Since math_errhandling is the program entry point and therefore always implicitly used, any program that fails to define it then contains a use of an undefined identifier, which is undefined behaviour [2, Section 6.9.1p5].

> On the other hand, any program which does define math_errhandling also has undefined behaviour. Per the standard [2, Section 7.12p20]:

I'm surprised that the recent advances in applying typography to engineering problems [1, 2] are not published at SIGBOVIK but are apparently going to a more serious journal.

[1] https://www.researchgate.net/publication/390635826_Structura...

[2] https://www.youtube.com/watch?v=azDaPm13CT8

The paper by Craig Gidney:

> Falling with Style: Factoring up to 255 “with” a Quantum Computer

is brilliant in a straightforward way, and I also learned something about Shor's algorithm. The first paragraph of intro and the abstract say:

> Historically, most papers that claimed they “ran Shor’s algorithm” didn’t run Shor’s algorithm. It’s unfortunately common to run circuits inspired by Shor’s algorithm, but with key pieces replaced by trivial pieces.

> In this paper, I explain how I factored all numbers up to 255 using Shor’s algorithm on a real quantum computer. I performed exactly the classical preprocessing specified by Shor’s algorithm, exactly the quantum circuit requested by Shor’s algorithm, and exactly the post-processing specified by Shor’s algorithm.

and this is true! He used IBM's quantum service (https://quantum.ibm.com/services/resources?tab=systems) with:

> my circuit for factoring 15 weighs in at 44405 two-qubit gates. And my circuit for factoring 253 weighs in at 245750 two-qubit gates. Amazingly, despite the fact that they vastly exceed the allowed size, the system accepted these ridiculous circuits.

What's the catch? Well, it's that:

> I’ll quickly review the classical and quantum steps of Shor’s algorithm. Before talking to a quantum computer, Shor’s algorithm performs some classical preprocessing. First, it checks if n (the number to factor) is even, because even numbers would cause trouble later. If so, it succeeds by returning the factor 2. Second, it checks if n is prime. Prime numbers can’t be factored, so in this case the method returns an error saying no factor exists. Third, the algorithm picks a random number g between 2 and n − 2, and computes the greatest common divisor (gcd) of g and n. If gcd(g, n) ≠ 1, then it happens to be a factor of n and so is returned as the result. Fourth, it’s finally time to actually use the quantum computer (whether it be real, simulated, or replaced by a random number generator). This is the expensive step, and the step that I’m counting in order to compare the different samplers. A quantum circuit based on g and n is generated, and executed, producing a sample m. Fifth, Shor’s algorithm classically computes the fraction that’s closest to m/4^{⌈log_2(n)⌉}, limiting the fraction’s denominator d to be at most n. Sixth, a candidate factor is generated by computing gcd(n, 1 + g^{⌊d/2⌋} mod n). If the candidate is actually a factor of n, it’s returned as the answer. Otherwise the algorithm restarts.

because of which:

> In other words, for small numbers, Shor’s algorithm succeeds quickly regardless of how well your quantum computer works.

It also cites a serious 2013 paper in Nature that made the same point: Oversimplifying quantum factoring, DOI 10.1038/nature12290.

"Introducing Neuro-Semantic Exclusivity: A Novel Approach to Gatekeeping Knowledge" (starting on page 12) credits one of their co-authors as "Chad Geppetto" with a footnote clarifying that he is ChatGPT.

I think that name is going to live in my head, as the kids say, rent-free.

as for the rest of their paper, I have some quibbles with the methodology, but overall I think it's an interesting result and look forward to seeing it replicated.

Oh hell yeah, hopefully this means we get a new Tom7 video soon!

I got distracted following the references to RFCs and noticed a nice number:

  2*7*24*60 = 047300 # two weeks, in minutes

This is not a coincidence. Ignoring the trailing zeros, we have:

  5*7*011 = 5*077 = 5*0100 - 5 = 0473

Searched for tom murphy and was not disappointed.

Is Tom doing anything this year?

Glad you liked it.

Note the 2013 paper wasn't making the same point. They weren't pointing out that Shor's algorithm succeeds quickly regardless of how well the quantum computer works when factoring small numbers. They proved the period-matching "precompilation" tricks experimentalists were doing at the time weren't okay, because those tricks could turn any factoring problem into a trivial two qubit circuit (and were equivalent to knowing the factors).

This was my favorite addition as well, I love that satire can be such a great teacher for algorithms.