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.
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]:
> 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.
> 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.
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).
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.
"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.
I'm also out of the loop but after some research, 0473 seems to be a TikTokism meaning "hug me, please." I would assume that this code uses octal notation, hence GP doing their math in octal, but the sources I've turned up describe codes with digits illegal in octal, so I don't really know.
His Youtube videos are gold. This one, in which he aims to take the imprecision of floating point numbers to extreme applications, such as training neural networks with linear activation functions or even implementing cryptologically-safe functions, is superb.
His paper is #55, “Some upsetting things about shapes”, found on page 342. Its header and contents are not searchable, presumably due to his use of his bespoke typesetting program from a previous SIGBOVIK year. It’s a great read!
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.
A Turing machine is Doom complete?
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]:
Does this mean that all C programs invoke undefined behavior?
All C programs targeting this particular freestanding implementation do.
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.
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).
Ah I see, thanks for clearing that up!
This was my favorite addition as well, I love that satire can be such a great teacher for algorithms.
> 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.
Look I hope one day to go back to school and get my degree in Computational Heresy.
Your cogitators possess value, Citizen. Do not waste them on unsanctioned thought-paths.
The Emperor Protects!
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
"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:
This is not a coincidence. Ignoring the trailing zeros, we have:I don’t understand.
Maybe RFC 9759, which is referenced in the article "HTTP offload is a dumb great idea whose time has come"?
https://www.ietf.org/rfc/rfc9759.html
OP apparently noticed that two weeks is almost 20480 decimal = 050000 octal minutes, just 320 = 0500 minutes in fact.
I'm also out of the loop but after some research, 0473 seems to be a TikTokism meaning "hug me, please." I would assume that this code uses octal notation, hence GP doing their math in octal, but the sources I've turned up describe codes with digits illegal in octal, so I don't really know.
Searched for tom murphy and was not disappointed.
His Youtube videos are gold. This one, in which he aims to take the imprecision of floating point numbers to extreme applications, such as training neural networks with linear activation functions or even implementing cryptologically-safe functions, is superb.
This was harder to find than I would've thought, so for anyone else curious:
https://www.youtube.com/@tom7
https://www.youtube.com/watch?v=Ae9EKCyI1xU
I was.
Is Tom doing anything this year?
His paper is #55, “Some upsetting things about shapes”, found on page 342. Its header and contents are not searchable, presumably due to his use of his bespoke typesetting program from a previous SIGBOVIK year. It’s a great read!
Doesn't he usually submit under a pseudonym?