Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

That would be a correction to tikhonj's terminology -- indeed, the usual formal way of dealing with the kind of issue he described uses the term "language" just as you describe -- but my (perhaps wrong) interpretation was that he was meaning to say something more startling than "there exist undecidable languages" with that definition of "language", and it wasn't his terminology that I was trying to correct.

I'm not sure what question you think I was begging. I was saying (partly implicitly) the following: (1) When you [= tikhonj] say "there are undecidable problems" you may well be thinking of, and will almost certainly be taken to mean, that there are actual questions you could ask a computer program that it can't answer. (2) The cardinality argument doesn't show that there are undecidable problems in that sense. (3) What the cardinality argument shows is of course true, but less interesting than the existence of concrete questions (or families of questions, parameterized by the input) that a computer can't answer. (4) There do exist such questions, but to prove that you need a more complicated argument.

I don't see any circularity there. Perhaps there's some other thing I could have meant that is question-begging, in which case I apologize for not making my meaning clearer. If you still think I begged the question after my attempt at clarification, please let me know so I can fix either my reasoning, my exposition or your reasoning, whichever is at fault :-).



The circularity I am looking at is that my ability to have "actual questions you could ask a computer program that it can't answer" is reliant on my ability to generate them and verify the results (as in, that they answered the question correctly or not) using algorithms, which inherently limits the cardinality of the set of possible questions to the cardinality of the set of possible answers, but I feel only because we are starting from inside of the algorithmic box.

To me, it is very similar to claiming (which many do; I won't, btw, go so far as to say that it is a poor way of looking at the world: this may be more practical) that there is no such thing as a set that has infinite cardinality (whether we are talking countably, uncountably, or something even more infinite than that) because no one would be able to count how many elements are in the set, nor would the set have been able to be constructed in the first place.

Maybe "circular" isn't the right term, but it does seem to rely on an assumption of the result (hence my usage of "begging"). My goal, then, in switching from "problem" to the more specified "language" is that, if you believe in the concept of "infinity" in the first place, I feel justified in my ability to prove that the set of languages is uncountably infinite, and the fact that I can't enumerate (or possibly even choose) elements from that set is not relevant.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: