Skip to main content

philosophy/​logic directory


“How the Slowest Computer Programs Illuminate Math’s Fundamental Limits: The Goal of the 'busy Beaver' Game Is to Find the Longest-running Computer Program. Its Pursuit Has Surprising Connections to Some of the Most Profound Questions and Concepts in Mathematics”, Pavlus 2020

“How the Slowest Computer Programs Illuminate Math’s Fundamental Limits: The goal of the 'busy beaver' game is to find the longest-running computer program. Its pursuit has surprising connections to some of the most profound questions and concepts in mathematics”⁠, John Pavlus (2020-12-10; ⁠, ; similar):

“In math, there is a very permeable boundary between what’s an amusing recreation and what is actually important”, said Scott Aaronson⁠, a theoretical computer scientist at the University of Texas, Austin who recently published a survey of progress in “BusyBeaverology.” The recent work suggests that the search for long-running computer programs can illuminate the state of mathematical knowledge, and even tell us what’s knowable. According to researchers, the busy beaver game provides a concrete benchmark for evaluating the difficulty of certain problems, such as the unsolved Goldbach conjecture and Riemann hypothesis⁠. It even offers a glimpse of where the logical bedrock underlying math breaks down. The logician Kurt Gödel proved the existence of such mathematical terra incognita nearly a century ago. But the busy beaver game can show where it actually lies on a number line, like an ancient map depicting the edge of the world.

…For instance, if you’re only allowed one rule, and you want to ensure that the Turing machine halts, you’re forced to include the halt instruction right away. The busy beaver number of an one-rule machine, or BB(1), is therefore 1. But adding just a few more rules instantly blows up the number of machines to consider. Of 6,561 possible machines with two rules, the one that runs the longest—six steps—before halting is the busy beaver. But some others simply run forever. None of these are the busy beaver, but how do you definitively rule them out? Turing proved that there’s no way to automatically tell whether a machine that runs for a thousand or a million steps won’t eventually terminate.

That’s why finding busy beavers is so hard. There’s no general approach for identifying the longest-running Turing machines with an arbitrary number of instructions; you have to puzzle out the specifics of each case on its own. In other words, the busy beaver game is, in general, “uncomputable.” Proving that BB(2) = 6 and that BB(3) = 21 was difficult enough that Radó’s student Shen Lin earned a doctorate for the work in 1965. Radó considered BB(4) “entirely hopeless”, but the case was finally solved in 1983⁠. Beyond that, the values virtually explode; researchers have identified a five-rule Turing machine, for instance, that runs for 47,176,870 steps before stopping, so BB(5) is at least that big. BB(6) is at least 7.4 × 1036,534. Proving the exact values “will need new ideas and new insights, if it can be done at all”, said Aaronson.

…The Goldbach conjecture, for instance, asks whether every even integer greater than 2 is the sum of two primes. Proving the conjecture true or false would be an epochal event in number theory, allowing mathematicians to better understand the distribution of prime numbers. In 2015, an anonymous GitHub user named Code Golf Addict published code for a 27-rule Turing machine that halts if—and only if—the Goldbach conjecture is false. It works by counting upward through all even integers greater than 4; for each one, it grinds through all the possible ways to get that integer by adding two others, checking whether the pair is prime. When it finds a suitable pair of primes, it moves up to the next even integer and repeats the process. If it finds an even integer that can’t be summed by a pair of prime numbers, it halts. Running this mindless machine isn’t a practical way to solve the conjecture, because we can’t know if it will ever halt until it does. But the busy beaver game sheds some light on the problem. If it were possible to compute BB(27), that would provide a ceiling on how long we’d have to wait for the Goldbach conjecture to be settled automatically. That’s because BB(27) corresponds to the maximum number of steps this 27-rule Turing machine would have to execute in order to halt (if it ever did). If we knew that number, we could run the Turing machine for exactly that many steps. If it halted by that point, we’d know the Goldbach conjecture was false. But if it went that many steps and didn’t halt, we’d know for certain that it never would—thus proving the conjecture true…In 2016, Aaronson established a similar result in collaboration with Yuri Matiyasevich and Stefan O’Rear. They identified a 744-rule Turing machine that halts if and only if the Riemann hypothesis is false

…In 2016, he and his graduate student Adam Yedidia specified a 7,910-rule Turing machine that would only halt if ZF set theory is inconsistent. This means BB(7,910) is a calculation that eludes the axioms of ZF set theory. Those axioms can’t be used to prove that BB(7,910) represents one number instead of another, which is like not being able to prove that 2 + 2 = 4 instead of 5…“So much of math can be encoded as a question of, ‘Does this Turing machine halt or not?’” Aaronson said. “If you knew all the busy beaver numbers, then you could settle all of those questions.”

“Why Philosophers Should Care About Computational Complexity”, Aaronson 2011

“Why Philosophers Should Care About Computational Complexity”⁠, Scott Aaronson (2011-08-08; ⁠, ⁠, ⁠, ⁠, ; backlinks; similar):

One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory—the field that studies the resources (such as time, space, and randomness) needed to solve computational problems—leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume’s problem of induction, Goodman’s grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis.

“A Plea for Excuses: The Presidential Address”, Austin 1956

1956-austin.pdf: “A Plea for Excuses: The Presidential Address”⁠, J. L. Austin (1956-10-29; backlinks; similar):

Summary by The Philosogist:

  • Excuses are offered when a person is said to have done something bad or wrong

  • To justify means to admit to performing the action but argue that it was good, right, or permissible, either in general or under the circumstances

    • To justify is to accept responsibility but deny its wrongness
  • To excuse is to admit the action wasn’t good, but assert that there are extenuating circumstances, eg. that it was an accident, or one was forced to do perform the action

    • To make an excuse is to accept its wrongness but deny responsibility
    • Few excuses are entirely exonerating
  • The theory of excuses will have major implications on moral philosophy · To attain a foundation for moral philosophy, it’s necessary to better understand what it means to do an action · Studying excuses, which are a type of abnormal action, will facilitate understanding and classification of actions in general, and clarify the notions of and relationship between freedom and responsibility

    • Doing an action is more complex than merely making a physical movement with the body · It’s misleading to take “doing an action” as a concrete description rather than abstract stand-in for a verb · What constitutes an action is a complex question that can involve difficult questions of motive and classification The theory of excuses has practical implications for ordinary language

    • It is a good thing to have a clear understanding of the words we use and how to use them

    • Excuses present a good field of language for study, due to its rich, subtle, and practical nature, and the fact that it is relatively untouched by traditional philosophy

    • The fact that people may differ in use of terms is no barrier, but actually may help illuminate subtle distinctions

    • Ordinary language is not a perfect or finalized system; it is rather a starting point

  • Some ways to systematically understand excuses are as follows:

    • Dictionary · Law, especially common law, and specifically tort law · Psychology, including anthropology and zoology · These sources will aid in providing a classification, understanding, and definition of many expressions and actions
  • Aim and general lessons to be learned from the study of excuses (numbered as follows):

    1. Normal actions should not be modified by adverbs; adverbs are only used to mark peculiar or abnormal instances of actions
    2. Adverbs generally apply only to a narrow range of verbs
    3. Pairs of words that are ostensibly opposites, like voluntarily/​involuntarily, are not necessarily so, and many words such as “inadvertent” have no clear opposite
    4. Adverbs describe different machineries of action, such as the decision stage, the planning stage, and the executive stage (carrying out the action)
    5. There are unacceptable excuses, but standards for acceptance vary by situation
    6. It’s important to pay attention to subtle differences between similar words (such as “intentionally” and deliberately”)
    7. The 1874 court case of Regina v. Finney, in which a man accidentally scalds a mental patient to death in the bath, is illustrative of the differences in clarity with which excuses can be described
    8. The object of the study of excuses is to clearly distinguish between terms through illuminating examples
    9. It’s necessary to pay attention to the context and expression in which the word is used, not merely to the meaning of the word in isolation
    10. Adverbs may also describe a style of performance, such as a deliberate or careless manner of action
    11. An adequate account of actions, ie. the stages or stretches of an action and what constitutes an action, is vital to the study of excuses (that is, to know what is being excused)
    12. Etymology can help shed light on difficult words like “result” and “intention” · One must avoid the danger of believing that words should fit neatly together into a single conceptual scheme –terms may overlap, conflict, or be disparate · This is a problem in philosophy more generally, in that key terms like “right” and “good” are often assumed to have the potential to fit in an unified framework
    13. Modern science, such as zoology, has revealed gaps in the capacity of language to describe certain actions, such as compulsive behavior

“Symposium: Facts and Propositions”, Ramsey & Moore 1927

1927-ramsey.pdf: “Symposium: Facts and Propositions”⁠, Frank P. Ramsey, G. E. Moore (1927-01-01; ; backlinks)