I, along with maybe 25 other people on the planet, have a Google Pixel Watch 2. I didn't expect this, but I love the new feature that pauses my phone's podcast when the system detects I've fallen asleep.

Maybe now I'll dig into the Phoebe Reads archive. https://open.spotify.com/show/4aqOirMxxorVMFcVRvDusi

There is a one-tape probabilistic Turing machine M that recognizes P_λ with bounded error probability and runs faster for infinitely many inputs than any one-tape deterministic Turing machine that recognizes P_λ.

how do they achieve faster computation of strings with certain width requirements, a fact specifically chosen to mimic the harsh memory requirements necessary to overcome modular exponentation?

let's return back to the "BPP" paper from john gill at stanford:

THEOREM 4.1. Suppose that λ is a rational number such that 0 < λ < 1.

[context: a rational number means λ = p/q, p,q in integers. they have just constructed an input string with a definition that states purely how far apart certain symbols are from each other in the input. they assume a turing machine processes string inputs serially and in order, because their "automata" are completely incapable of doing anything remotely more useful than that.

doing parsing theory better than their bullshit is how i met turing.]

download this pdf and really observe the framing https://www.sciencedirect.com/science/article/pii/S0019995863902900 before any other content, top left:

INFORMATION AND CONTROL 6, 230-245 (1963)

then you go down and see immediately some sort of large asterisk, typeset with its own glyph:

Probabilistic automata *

no, there's no errata:

* Most of the results in this paper were established while the author was visiting Bell Telephone Laboratories, Murray-Hill, in the summer of 1960. This paper was presented as an invited address at the Annual SIAM Meeting at California Institute of Technology, March 1962.

the author just wanted to mention where all the literal eugenicists were gathering [i'm referring to caltech]

Aside from the mathematical interest in pursuing this natural generalization of finite automata, the results also bear on questions of reliability of sequential circuits.

so maybe if you're not clued into literal eugenicists in your mathematics you won't get this, but the word "generalize" is a threat

P.a. are, in general, stronger than deterministic automata
(Theorem 2).

it's typeset so the new machine he created was lying on a bed of parenthesized references to his own "theorem" (not one, but two)

By studying the way we may want to use p.a. we are led to introduce the concept of isolated cut-point (the Reduction Theorem 3).

all of these people are like this all the time. this is why academic cryptography is a complete fucking joke

and note how the author uses a special serif semibold font for when they type their literal slop facsimile: "p.a.".

[which they created because they hate that alan turing created a field other mathematicians could actually comprehend and challenge hiim at].

It is interesting to note that in passing from a minimal deterministic automaton to an equivalent p.a. we can sometimes save states (Section VII).

they don't save states, they just take over the entire fucking computer and piss and shit all over the tape that allows other mathematicians to actually reason about the behavior of rabin's fucked up colonizer structures and systems

finally note the use of roman numerals, which is intentional

you'd think i'd like deadloch considering i think get crackin is top shelf comedy gold, but i didn't enjoy deadloch at all - you win some, you lose some, not everything can be a banger!