News for hackers. Stuff that matters.
Re:Does infinity exist? by tikhonj on Saturday September 15, 2012 @01:09PM (#4526592)
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.

Re:Does infinity exist? by ced on Saturday September 15, 2012 @01:43PM (#4526706)
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?

Re:Does infinity exist? by saurik on Saturday September 15, 2012 @02:42PM (#4526897)
(You can try my description, a sibling to your more-parent comment, to see if that helps.)