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

Right, good observations. I'm being more than a little loose with some of my terminology.

"Undecidable" problems are usually defined in terms of "languages". That is, a language is a set of string, and the problem is to decide whether some particular string is in this set. For certain sets, this is not computable, so they are called undecidable.

However, this is isomorphic to just running any sort of program, so I just took "undecidable" to mean any function from strings to strings that you can't answer with a Turing machine. However, I definitely agree that I could have been far more clear! It seems you can't just read my mind, and I'm not sure if I can really blame you for it.



Yeah, these problems are hard (and fun!) to think about. But I still don't understand how you can go from:

There has to be an infinite number of functions we cannot write programs for!

which is, of course, true, to

So we have managed to show, in a fairly simple way, that there have to exist undecidable problems.

I don't think that you are using "undecidability" in its correct sense, or perhaps I'm missing something. What is your undecidable problem? You wrote

the problem is to decide whether some particular string is in this set

Which set are you talking about? The set of all programs? How does that tie in with your functions defined on integers?


(You can try my description, a sibling to your more-parent comment, to see if that helps.)




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

Search: