• 47 Posts
  • 1.04K Comments
Joined 2 years ago
cake
Cake day: June 27th, 2023

help-circle



  • I’ve noticed the occasional joke about how new computer technology, or LLMs specifically, have changed the speaker’s perspective about older science fiction. E.g., there was one that went something like, “I was always confused about how Picard ordered his tea with the weird word order and exactly the same inflection every time, but now I recognize that’s the tea order of a man who has learned precisely what is necessary to avoid the replicator delivering you an ocelot instead.”

    Notice how in TNG, everyone treats a PADD as a device that holds exactly one document and has to be physically handed to a person? The Doylist explanation is that it’s a show from 1987 and everyone involved thought of them as notebooks. But the Watsonian explanation is that a device that holds exactly one document and zero distractions is the product of a society more psychologically healthy than ours…



  • Having now refreshed my vague memories of the Feynman Lectures on Computation, I wouldn’t recommend them as a first introduction to Turing machines and the halting problem. They’re overburdened with detail: You can tell that Feynman was gleeful over figuring out how to make a Turing machine that tests parentheses for balance, but for many readers, it’ll get in the way of the point. Comparing his discussion of the halting problem to the one in The Princeton Companion to Mathematics, for example, the latter is cleaner without losing anything that a first encounter would need. Feynman’s lecture is more like a lecture from the second week of a course, missing the first week.









  • Regarding the last bullet point, there’s always the argument from authority, i.e., appealing to a book with Feynman on the byline.

    Now when mathematicians first addressed these problems, their interest was more general than the practical limits of computation; they were interested in principle with what could be proved. The question spawned a variety of approaches. Alan Turing, a British mathematician, equated the concept of “computability” with the ability of a certain type of machine to perform a computation. Church defined a system of logic and propositions and called it effective calculability. Kleene defined certain so-called “general recursive propositions” and worked in terms of these. Post had yet another approach (see the problem at the end of this chapter), and there were still other ways of examining the problem. All of these workers started off with a mathematical language of sorts and attempted to define a concept of “effective calculability” within that language. Thankfully for us, it can be shown that all of these apparently disparate approaches are equivalent, which means that we will only need to look at one of them.

    From p. 54 of the Feynman Lectures on Computation, by Feynman, Hey and Allen (the latter two being the editors who turned the tape recordings of the lectures into a book several years after Feynman died). There’s a pretty lengthy discussion of Turing machines in chapter 3 that does introduce the halting problem.