Pictures of Theories: The Entscheidungsproblem

The Entscheidungsproblem, Computer Science:

This one was a doozy. But the main reason I started this website was to champion intelligence in a fun way, in the angry face of the stupidity that seems to be swallowing America.  Well, trying to understand the Entscheidungsproblem sure as heck was fun. I emerged a little smarter even if I don’t totally get it. (In my own defense, I would like to add that I am dangerously sleep deprived and am trying to understand everything including the Entscheidungsproblem while at least one child is screaming at me and pulling on my leg, often two. That makes it harder to understand the Entscheidungsproblem. But I would still recommend at least trying!)

So back to the Entscheidungsproblem, which is German, surprise surprise, for “decision problem.” I would love to quote the right person saying the right thing here, but time is lacking, so here is what Wikipedia has to say:

In mathematics and computer science, the Entscheidungsproblem (pronounced [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm], German for “decision problem”) is a challenge posed by David Hilbert in 1928. The problem asks for an algorithm that takes as input a statement of a first-order logic (possibly with a finite number of axioms beyond the usual axioms of first-order logic) and answers “Yes” or “No” according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms. By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced from the axioms, so the Entscheidungsproblem can also be viewed as asking for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic.

In 1936, Alonzo Church and Alan Turing published independent papers showing that a general solution to the Entscheidungsproblem is impossible, assuming that the intuitive notion of “effectively calculable” is captured by the functions computable by a Turing machine (or equivalently, by those expressible in the lambda calculus). This assumption is now known as the Church–Turing thesis.

And more colorful quote from Douglas Hofstadter:

Excuse me; I think I’ll go get some more punch. There is a probelm once you start getting into infinite regresses composed of other infinite regresses – the whole thing just never stops, and it becomes a bore. Or not exactly a bore, but a very complex and confusing and confusing thing, whose reality and relevance become ever more questionable. And yet, when you bring it back to the domain of sphexishness, it becomes the very real and very relevant question of how to build a machine that can sense unanticipated patterns in its own behavior.

This is related to a classic problem in the theory of computability, called the halting problem: It is the question of whether there is exists any computer program that can inspect other programs before they run, and reliably predict whether or not they will go into infinite loops (“going into an infinite loop” means, of course, never coming to a halt – and conversely, “halting” means avoiding an infinite loop). The answer turns out to be “Definitely not”, and for elegant, deep reasons. (Recall Chapter 21.) Of course, the thing hinges on getting this halting inspector to try to predict its own behavior when looking at itself trying to predict its own behavior when… Excuse me; I think I’ll go get some more punch.

-Douglas Hofstadter, Metamagical Themas: Questing for the Essence of Mind and Pattern (534-535)

So… I drew a picture of a Turing Machine trying to choose an ice cream flavor. And now excuse me; I think I’ll go get some more punch.

 

Are you now, or have you ever been, a graduate student or professor? Are you an anomalous undergraduate who is really “into” theory? Send me your theories at devonisadevon@gmail.com or via facebook, and I will draw them. Esoteric terminology also accepted but will be evaluated on a case-by-case basis. Oh, and follow me on Instagram while you’re at it – devon_isadevon.

More theories here.