So I am reading part of this and have come to a part where he says,
"“Consider the machine specified as follows. . . . Will this machine ever answer ‘Yes’ to any question?” The dots are to be replaced by a description of some machine in a standard form, which could be something like that used in § 5. When the machine described bears a certain comparatively simple relation to the machine which is under interrogation, it can be shown that the answer is either wrong or not forthcoming. This is the mathematical result: it is argued that it proves a disability of machines to which the human intellect is not subject. "
This is taken from Computing Machinery and Intelligence by A.M Turing 1950.
I am having a hard time figuring out why any digital computer will either be wrong or not forthcoming.
No search of the internet or this board seemed to have an explaination geared toward someone who is just having trouble wrapping their noodle around this question.
thanks!
Ahhh I can’t figure out how to edit my post. To clarify, I am looking for a general answer that probably uses the sentence in question to demonstrate it. I am aware that even I could write a computer program that when asked this question replies with a canned “yes” everytime and would have no problem with this specific quesion.
I don’t have the book in front of me, and you don’t give enough context for me to be absolutely sure, but I think he’s describing the “Halting Problem” (or an early version of it).
Basically, this contrives a computational equivalent to “This statement is a lie:” - it’s the proof that there are problems computationally intractable to a Turning Machine (and hence, if Church’s Thesis is true, to all computers, everywhere).
It is often claimed that human thought isn’t subject to this limitation (usually as part of a claim that human intelligence isn’t computation). That claim isn’t falsifiable by any experiment yet devised, so it’s mostly a religious argument at this point.
Unless the answer to that question is always “yes”, your program would be wrong in some cases. I agree, though, that it would be very helpful to know what the question is.
I realize now that I’m as obscure as the original reference. Let me try again.
Let H be the program you’re writing: it takes another program, P, and returns “Yes” if P will return “Yes” to any possible input. We’ll call the result of that H§.
Now, let’s construct a program S§, like this:
if H§ = “No”, return “Yes”
otherwise return “No”
Now ask the question: What’s the answer to H(S)?
“Yes”: That means S returned “Yes” for some program, but that happens only if if there is no program (including S) that returns “Yes” - contradiction.
“No”: That means S returned “No” - there are no programs for which S returns “Yes”. But H itself is a program that would make S return yes. - contradiction.
So we can argue that H§ can’t be built in the first place.
Yeah I now remember the halting problem, and your description made it very clear. Thanks!
So I gues my next question is in the paper, Turing said that all problems would be of the form described above, not specifically the question stated above. He was vague of much else. here is the paper it is in section 3. Is this question a form of the halting problem? I’m guessing it is.
Turing wasn’t vague about anything–that’s taken from his doctoral dissertation, and everyone knows how picky doctoral committees are.
For Turing machines at least, it’s suitable to restrict your attention to problems for which the answer is either yes or no. Many of those can be answered, but some can’t.
Yeah, what Ultrafilter said.
I sort of reworded the “classic” halting problem on the fly to try and use the sentence you were talking about above. It’s usually stated in the form of a program that either halts (the “yes” answer) or keeps looping forever (the “no” answer above, but more generally the indeterminant case – you can’t know in general if a program that’s still running won’t halt, or just hasn’t yet). Hence the term “Halting Problem.”
As far as the “all problems” issue, consider that anything that produces output on a digital computer is producing a string of bits. So you can reduce any program to a set of binary ones, each of which produces a single bit of your output. Nobody’d actually do this, of course, but then no one would use a Turing machine as a computing environment, except for academic and theoretical use. (Especially since those infinitely long tapes get expensive).
A little off-topic,
Sheperd Wong - what was the egg salad recipe? All I remember is that it would make you plotz!
oh, and one other thing, “Two Wongs don’t make a Wight”