Non-undecidability of singular questions

By -
The many memorious among youse may remember a tiny problem set I offered as a challenge aeons ago, which included, among others, a question about the decidability of a couple of representative singular questions (singular in the sense of "Is John homicidal?" vs. "Which people named 'John' are homicidal?"). The answer given in my hearing by Prof. Burton Dreben when asked by a student was echoed almost verbatim by Shonk in answer to my challenge.

The same answer may be found in Marvin Minsky, Computation, Finite and Infinite Machines (Prentice-Hall, 1967) regarding the halting problem for one Turing machine; but, interestingly, Minsky goes further: "For a given (T0,t0) it could well be that no one will ever find out whether it halts or not. It could conceivably be that there is no way to find out, in some obscure sense. But it could not be that someone could prove that there is no way to find out...Suppose that it had allegedly been proven that there is no way to find out if (T0,t0) halts or not. Suppose also that a great experimental project were launched, involving the construction and operation of (T0,t0)...Now there are two cases in fact--either (T0,t0) does eventually halt, or it never halts. In the first case, the experimental approach will ultimately succeed, and the question will be settled. This would certainly contradict any proof that the question could never be settled! Hence it must happen that (T0,t0) never stops. In other words, the proof that there is no way to find out can be used to prove that (T0,t0) never halts. Hence we would be able to find out. Contradiction!"

Comments

Post a Comment

Popular posts from this blog

Libertarians, My Libertarians!

By -
Cruel to be kind means that I love you . Because, while I think you are mistaken, your hearts are in the right place -- yes, even you, Silas --  unlike some people . This Breitbart fellow (discussed in the link above), by all appearances, deliberately doctored a video of Shirley Sherrod to make her remarks appear virulently racist, when they had, in fact, the opposite import. I heard that at a recent Austrian conference, some folks were talking about "Callahan's conservative turn." While that description is not entirely inaccurate, I must say that a lot of these people who today call themselves conservative give me the heebie-jeebies.
Read more

"Pre-Galilean" Foolishness

By -
 I am currently reading The Master and His Emissary , which appears to be an excellent book. ("Appears" because I don't know the neuroscience literature well enough to say for sure, yet.) But then on page 186 I find: "Asking cognition, however, to give a perspective on the relationship between cognition and affect is like asking astronomer in the pre-Galilean geocentric world, whether, in his opinion, the sun moves round the earth of the earth around the sun. To ask a question alone would be enough to label one as mad." OK, this is garbage. First of all, it should be pre-Copernican, not pre-Galilean. But much worse is that people have seriously been considering heliocentrism for many centuries before Copernicus. Aristarchus had proposed a heliocentric model in the 4th-century BC. It had generally been considered wrong, but not "mad." (And wrong for scientific reasons: Why, for instance, did we not observe stellar parallax?) And when Copernicus propose...
Read more