Turing’s library June 19, 2016Posted by Ezra Resnick in Computer science, Logic.
Tags: Halting problem
add a comment
You are in an infinite library, containing the code of every possible computer program. In the library’s central space there is a computer that can be used for running the programs: you enter the code of the program you wish to run, along with the program’s input, then you push the Run button. A red light indicates that the program is running. Some output may be printed, and when the program’s execution is complete the light goes off. For some programs and inputs the run ends almost immediately, but for others the light stays on for a long time. If you get tired of waiting for the computer to halt, you can always press the Abort button to stop the current run.
Some programs in the library are short and simple, like this one:
Program M [input: two numbers, a and b]
Print the sum of a and b.
Unsurprisingly, running Program M with the numbers 2 and 3 as input prints “5”, denoted M[2, 3] = 5. Some programs are much more complex, of course. There is a program that translates English text to Japanese; a program that computes the shortest route between any two cities on a map; a program that, given the state of the board in a checkers game, finds the optimal next move.
Some programs take a long time to run, but you notice that some programs are guaranteed to never halt, at least for some inputs. For example:
Program N [input: a number, n]
As long as n equals 0, keep printing “0”.
For any nonzero input, Program N halts immediately; but N gets stuck in an infinite loop, printing zeros forever (or until you hit the Abort button).
Unfortunately, you find that for many programs you cannot easily tell just by examining their code whether or not they will run forever. If a program is still running after a week, or a year, should you give up and abort? Perhaps it only needs a minute more, or an hour, or a day — or, it might be stuck in an infinite loop that will never end. It occurs to you that it would be nice to know in advance, before running a program, whether it will eventually halt (for a given input), or whether it is destined to run forever. Surely, you think, there must be a program somewhere in the library that can answer that question! After all, a computer program is just text, so there’s no reason why the code of one program cannot serve as the input for another. The special program you are seeking, call it Program H, would take as its input the code of the program to be evaluated (p), along with that program’s proposed input (i); Program H would then print “True” (i.e., H[p, i] = True) in cases where p[i] would halt, or “False” (i.e., H[p, i] = False) in cases where p[i] would run forever. You spend a long time searching the library for Program H.
One day you happen upon someone who introduces himself as the librarian. Excited, you describe Program H, and ask where in the library it can be found. The librarian smiles. The library is infinite, he says, containing every possible computer program — but none of them is Program H. You ask how he can be certain, since by his own admission the library is infinite. Let me prove it to you, he says. If Program H existed in the library, there must also exist Program G, defined as follows:
Program G [input: the code of a computer program, x]
Use the same method as Program H to determine whether program x will halt when running with the code of program x as its input. If so (i.e., H[x, x] = True), then loop forever; otherwise (i.e., H[x, x] = False), halt.
Now, says the librarian, ask yourself: What will happen if we run Program G with its own code as input? Will G[G] run forever or halt? We ought to be able to compute the answer using Program H. Let’s first assume that H[G, G] = True, which means that G[G] will halt. But, based on the definition of Program G, G[G] would only halt if Program H reports that G[G] will not halt, i.e., H[G, G] = False — contradicting our assumption. Let’s assume, then, that H[G, G] = False, which means that G[G] will not halt. But, based on the definition of Program G, G[G] would only fail to halt if Program H reports that G[G] will halt, i.e., H[G, G] = True — also a contradiction!
We therefore have no choice but to conclude that Program H is like a square circle: it cannot logically exist. The library is infinite, containing every possible computer program — but none of them is Program H: some problems are impossible to solve.
Look on the bright side, says the librarian, sensing your disappointment. What’s that, you ask. The librarian smiles: At least you won’t waste any more time searching for something that isn’t there.
Playing by the rules November 15, 2014Posted by Ezra Resnick in Game theory, Logic.
add a comment
“Sure! But first we need to agree on the rules.”
“Of course. I propose that we take turns proposing rules.”
“Agreed, and since you just proposed the first rule, I guess I get to propose the next one.”
“Wait a minute: I didn’t propose a rule for the game itself — I merely proposed a rule for how we ought to go about proposing the game rules.”
“Apologies; yours was indeed a meta-rule. In that case, let me propose a meta-rule of my own: Any disagreement about a proposed game rule will be decided by flipping a coin.”
“I’m not sure I agree with that.”
“Well, we haven’t yet agreed on a method for resolving disagreements about meta-rules. Do you have a suggestion?”
“How about we take turns: one of us gets to decide the first disagreement, the other decides the next disagreement, and so on.”
“OK, then: following your meta-meta-rule, I now get to decide our meta-rule disagreement about how to resolve disagreements about game rules.”
“Hold on: Who said you get to decide the first meta-rule disagreement?”
“Well, I let you determine the meta-meta-rule on how to decide meta-rule disagreements, so now it’s my turn.”
“Nice try, but we never agreed on how to resolve disagreements about meta-meta-rules. You can’t just make unilateral assumptions.”
“Well, how come you got to propose the first meta-rule to begin with? If you get to propose the first meta-rule then I should get to decide the first meta-rule disagreement.”
“Then I get to propose the first game rule.”
“First, I propose the following meta-rule: If the first rule proposal is challenged and loses the coin flip, the challenger must propose the following as his next rule: ‘The winner is whoever proposed playing the game.'”
“I don’t agree to that!”
“Noted, but according to our meta-meta-rule, it’s my turn to decide in case of disagreement on a meta-rule. And now for my first proposed game rule: The winner is whoever proposed playing the game.”
“Even if I disagree I still lose. Nicely played.”
“Thanks! That was fun.”
“Indeed. But maybe we should play a different game next time?”
“Sure! As long as we can agree on the rules…”
Three philosophers March 22, 2014Posted by Ezra Resnick in Logic, Philosophy, Puzzles.
add a comment
Three philosophers are sitting on a bench.
- The homophobic philosopher is a deontologist.
- The free will libertarian subscribes to the Copenhagen interpretation of quantum mechanics.
- The consequentialist is addicted to heroin.
- The philosopher sitting next to the antisemite is a virtue ethicist.
- The hard determinist is sitting next to the cocaine addict.
- The philosopher sitting in the middle subscribes to the many-worlds interpretation of quantum mechanics.
- The sexist philosopher is a free will compatibilist.
- The philosopher subscribing to Bohm’s interpretation of quantum mechanics is not the methamphetamine addict.
- The antisemitic philosopher is not sexist, the sexist philosopher is not homophobic, and the homophobic philosopher is not antisemitic.
- No philosopher is addicted to more than one substance.
What is the antisemitic philosopher’s position on free will?
By way of contradiction May 5, 2013Posted by Ezra Resnick in Logic, Math.
An indirect proof (or proof by contradiction) establishes the truth of a proposition by showing that the proposition’s negation implies a contradiction. For example, we can indirectly prove that the square root of 2 is irrational (i.e., it cannot be expressed as a ratio a/b where a and b are integers) by assuming the opposite — that √2 can be expressed as a ratio of integers — and showing that such an assumption leads to a contradiction (e.g., that b is both even and odd).
Some people find indirect proofs unsatisfying, or even a bit suspicious: it feels like we’ve been cheated out of understanding why the proposition is true. Direct proofs seem more intuitive and dependable. This raises the question: Does every proposition that can be proved indirectly have a direct proof as well? Or are there propositions that can be proved indirectly, for which no direct proof exists?
Before attempting to answer that question, let us first consider this humble proposition:
(p) This proposition cannot be proved directly.
We can prove proposition p is true — indirectly. Start by assuming the opposite, that is, assume there exists a direct proof of p. In particular, that means p is true. But p states that there is no direct proof of p — contradicting our assumption. So our assumption must be false; hence p is true.
Let us now attempt to prove the following proposition:
(q) Not all propositions that can be proved indirectly can also be proved directly.
We shall prove the truth of proposition q (you guessed it) indirectly. Assume the opposite: that is, assume any proposition that can be proved indirectly can also be proved directly. Then, since p can be proved indirectly (as demonstrated above), there must also exist a direct proof of p. However, the existence of such a proof contradicts (the proven) proposition p! So our assumption must be false — and q is true.
Ah, but the question remains: Can q be proved directly?
Conflicting messages August 13, 2011Posted by Ezra Resnick in Language, Logic.
add a comment
I came across this somewhat paradoxical signpost in Cambridge, Massachusetts:
A logician in hell (the prequel) July 23, 2011Posted by Ezra Resnick in Logic.
add a comment
I was arrested for breaking the laws of logic — accused of poisoning a well (while also intending to drink from it). The trial was held in an old circus tent, before a random jury. The prosecutor delivered the following speech:
“Ladies and gentlemen of the jury: let me begin by pointing out that the defendant is extremely ugly.
“You should also know that I have been chief prosecutor for over 100 years, and am well-respected as a leading authority on all criminal matters.
“Believe me, therefore, when I tell you that the defendant’s guilt in this case is quite certain: not only does he have no alibi for the time of the crime, he has offered no alternative suspect whatsoever — claiming that he ‘doesn’t know’ who did it! Surely, such a shameless admission of abject ignorance speaks for itself.
“As if that weren’t enough, there is solid statistical evidence against the defendant as well: meticulous studies performed over many years have consistently shown that a majority of those indicted for similar crimes were, in fact, guilty. Moreover, the last five suspects we arrested turned out to be innocent, so for this defendant to be innocent as well would be unlikely in the extreme.
“Finally, I ask you to consider the consequences of finding the defendant not guilty. First of all, such an outcome would imply that those responsible for upholding the law around these parts are incompetent — and who among you would want to live in such a society? Additionally: be assured that if this case does not end in conviction, very soon we will be unable to convict any criminals at all, so that murderers and rapists will walk our streets with impunity.
“In conclusion, ladies and gentlemen of the jury: let me remind you that the defendant is really very ugly, and smells bad, too. Thank you for your attention.”
The jury applauded and the prosecutor took a bow. Just as I stood up to speak in my own defense, the jury left for lunch. Upon their return, it was announced that the jury had reached a decision: my guilt would be determined by the outcome of three sporting contests to be held between the prosecutor and myself.
In the first contest, each of us had to fight our way through an army of dummy soldiers. But while my dummies were made of iron, the prosecutor’s were made of straw. He finished first.
Next was an archery contest. I aimed carefully, and my arrow lodged only slightly below the center of the target. But when I looked over at my opponent’s attempt, I saw that he had shot at a blank wall — where a young boy was now quickly painting a target around his arrow.
For the final contest, we had to hit a ball between designated goalposts. The prosecutor succeeded with no trouble; but whenever I swung, the goalposts (which were actually flamingos) moved out of the ball’s way.
Back in court, I was asked if I had anything to say for myself; but all I could do was beg the question. Shortly thereafter, I was informed that I had been found guilty. I was sentenced to be hanged unexpectedly within the week…
If by whiskey July 17, 2011Posted by Ezra Resnick in Equality, Logic, Religion.
add a comment
Richard Elliot Friedman and Shawna Dolansky have written a book called The Bible Now, reviewed by Adam Kirsch for The New Republic:
They have set out to explain “what the Bible has to say about the major issues of our time,” in particular “five current controversial matters: homosexuality, abortion, women’s status, capital punishment, and the earth.”
What, for instance, does the Bible have to say about homosexuality? Leviticus (20:13) seems pretty clear: “And if a man lie with mankind, as with womankind, both of them have committed abomination: they shall surely be put to death: their blood shall be upon them.” Well, that’s what it says, but what does it really mean?
Friedman and Dolansky use [other ancient Near Eastern texts] to establish “the wider cultural context” of Leviticus, from which it follows that “what the authors of Leviticus … may be prohibiting is not homosexuality as we would construe the category today but, rather, an act that they understood to rob another man of his social status by feminizing him.” Why, then, does Leviticus, uniquely among ancient Near Eastern law codes, prescribe death for both partners in homosexual acts? Friedman and Dolansky argue, quoting another Bible scholar, that it is because Leviticus “emphasizes the equality of all. It does not have the class distinctions that are in the other cultures’ laws.”
This is a remarkable performance. Before you know it, a law that unambiguously prescribes death for gay men has been turned into an example of latent egalitarianism. Friedman and Dolansky imply that it was not homosexuality the Bible wanted to condemn, but the humiliation of the passive partner. And since we no longer think of consensual sex acts as humiliating, surely the logic of the Bible itself means that homosexuality is no longer culpable: “The prohibition in the Bible applies only so long as male homosexual acts are perceived to be offensive.”
But of course, one of the main reasons why people still perceive male homosexual acts as offensive is because the Bible declares them an abomination. Though I’m sure that will now change, as soon as “the wider cultural context” is more widely known…
Speaking of controversial matters: in 1952, Mississippi lawmaker Noah S. “Soggy” Sweat gave a speech on the floor of his state legislature, explicating his position on the prohibition of alcoholic beverages:
My friends, I had not intended to discuss this controversial subject at this particular time. However, I want you to know that I do not shun controversy. On the contrary, I will take a stand on any issue at any time, regardless of how fraught with controversy it might be. You have asked me how I feel about whiskey. All right, here is how I feel about whiskey:
If when you say whiskey you mean the devil’s brew, the poison scourge, the bloody monster, that defiles innocence, dethrones reason, destroys the home, creates misery and poverty, yea, literally takes the bread from the mouths of little children; if you mean the evil drink that topples the Christian man and woman from the pinnacle of righteous, gracious living into the bottomless pit of degradation, and despair, and shame and helplessness, and hopelessness, then certainly I am against it.
But, if when you say whiskey you mean the oil of conversation, the philosophic wine, the ale that is consumed when good fellows get together, that puts a song in their hearts and laughter on their lips, and the warm glow of contentment in their eyes; if you mean Christmas cheer; if you mean the stimulating drink that puts the spring in the old gentleman’s step on a frosty, crispy morning; if you mean the drink which enables a man to magnify his joy, and his happiness, and to forget, if only for a little while, life’s great tragedies, and heartaches, and sorrows; if you mean that drink, the sale of which pours into our treasuries untold millions of dollars, which are used to provide tender care for our little crippled children, our blind, our deaf, our dumb, our pitiful aged and infirm; to build highways and hospitals and schools, then certainly I am for it.
This is my stand. I will not retreat from it. I will not compromise.
(via Why Evolution is True)
A logician in hell June 14, 2011Posted by Ezra Resnick in Logic.
1 comment so far
The following is true.
I was arrested for breaking the laws of logic, and sentenced to be hanged unexpectedly within the week.
As I sat in my cell trying to reason my way out of my predicament, I saw the local executioner passing by. He looked like a logical fellow (and rather familiar), so I attempted to strike up a conversation: I asked whether he hanged all the condemned outlaws around these parts. “All those who don’t hang themselves,” he answered grimly. (I decided not to ask what would happen if he himself were sentenced to be hanged…)
I tried to bribe my way to freedom by offering the executioner a heap of gold coins; but he was not persuaded by my argument that zero coins constitute a heap.
Instead, he offered to set me free if I could guess the natural number he was thinking of. After an uncountable number of incorrect guesses, I gave up. (It turned out that he was thinking of the smallest natural number not definable in under eleven words.)
When the guards came (unexpectedly!) to take me to the gallows, I protested that I was insane and therefore unfit to be executed; but the executioner pointed out that insanity defenses are never accepted because anyone pleading for his own life must be sane.
As the rope was placed around my neck, I broke down and told the executioner that due to time travel gone wrong, I was actually his grandfather — so by killing me he would be undoing his own birth.
“I sure hope it works this time,” he said, and pulled the lever.
By the way, the first sentence of this post is false.
Yeti or square circle? March 18, 2011Posted by Ezra Resnick in Logic, Philosophy, Religion.
Tags: Anthony Grayling, Jerry Coyne
1 comment so far
Is evidence for the existence of God even possible? Biologist Jerry Coyne has published an email exchange with philosopher Anthony C. Grayling on this question. While both are atheists, Coyne maintains that the existence of God is an empirical question, and that it is conceivable (though highly unlikely) that convincing evidence for God might turn up some day. Grayling thinks not, because the very concept of God is incoherent:
on the standard definition of an infinite, omniscient, omnipotent, benevolent etc being — on inspection such a concept collapses into contradiction and absurdity; as omnipotent, god can eat himself for breakfast…as omniscient it knows the world it created will cause immense suffering through tsunamis and earthquakes, and therefore has willed that suffering, which contradicts the benevolence claim…etc etc…to say nothing of local suspension of the laws of nature for arbitrary reasons e.g. in answer to personal prayer, which makes a nonsense of the idea that the world or the deity is rationally comprehensible: and if either or both are non-rational then there is nothing to talk about anyway…
The point is that ‘god’ is not like ‘ether’ — it is not amenable to empirical investigation, and does not occupy a slot in some systematic framework of thinking about the world that might be improved on in the light of better theory or observation. It does no work because it purportedly does all work; like a contradiction it entails anything whatever; it is consistent with all evidence and none. These considerations constitute the proof that it is an empty concept. — If you treat the word ‘god’ as a name for a putative entity that might or might not exist and such that something might count as evidence for or against its existence, as you do, then you are committed to agnosticism about everything that can be given an apparent name. But ‘god’ is not like ‘yeti’ (which might — so to say: yet? — be found romping about the Himalayas), it is like ‘square circle’. Trying to explain to someone who thinks that ‘god’ is like ‘yeti’ (namely, you) let alone to someone who thinks ‘god’ is like ‘Barack Obama’ (names an actual being, as Christians and Muslims do) that it is actually not like ‘yeti’ but like ‘square circle’ and that nothing can count as evidence for square circles, is harder work for ‘god’ than ‘square circle’ only because religious folk have been squaring the circle for so long!
Coyne disagrees in principle:
I reject Anthony’s assertion that God is not amenable to empirical investigation, since one can empirically investigate claims about how God interacts with the world. The efficacy of prayer is one of these. I believe Grayling is referring here to a deistic god, since theistic gods need not be “consistent with all evidence.” The existence of earthquakes, for example, is not consistent with a benevolent theistic god. I still maintain that if one claims that a god interacts with the world in certain ways, then those claims can be investigated empirically. To me the existence of a deity is not a matter that can be ruled out by philosophy or logic from the get-go; it’s a matter for empirical observation and testing.
While I find this discussion interesting, I must admit that I don’t find it especially consequential. Even if the God concept can be made coherent, no remotely convincing evidence for the existence of a God has ever been offered, and there is no reason to expect it ever will (as Coyne would agree). The God hypothesis is dead. The existence of such an entity (certainly one that meets the description of any of our obviously man-made religions) is about as plausible as the existence of witches or the belief that suicide bombers really get 72 virgins in the afterlife.
Furthermore: religious people seem to think that if God does exist, then it’s obvious that we ought to obey his every command — but that doesn’t follow. Whether God is a yeti or a square circle, nothing can absolve us of the responsibility to think for ourselves, and to rationally decide how we ought to live our lives.