1. ## Simple undecidable problems

Hi,

Recently i have been studying about undecidability. And along with this study i saw many examples that involved really complex undecidable problems. And i saw too examples too much far from a concrete idea, like that of the halting problem of the Turing machines.

So, does anyone know a simple example of a undecidable problem and a reference for that problem?

Thank you.

2. It would be best if you told us what are the ones you already saw examples for. Otherwise we'll probably be throwing in here problems that you know about already.

3. Heh. I was just reading up on the halting problem, and I have to say I disagree with the consensus. I read the wiki article, but as usual, it expects the reader to be a little more familiar with the topic than I am. So I found this one: The Halting Problem

The idea is that it's "unsolvable", but that's not actually true. From what I read, I see no reason that the algorithm couldn't be written to be aware of said infinite recursions. In said case, I imagine a third response would be appropriate, e.g., "paradox" rather than "halts" or "loops". Because the algorithm _knows_ it's input -> output doesn't match a simple yes/no, does _not_ mean it doesn't know the answer. If you want to be a stickler about it, and say it _has_ to be yes/no, then that's fine, the answer would be, it loops. Because, it _is_ looping, just outside of the algorithm, rather than in it.

I'm not say there aren't any "undecidable problems", just that the halting problem is a really weak example.

4. The problem states that it is impossible to determine if P halts for an arbitrary P. How does introducing the answer "I don't know" (which is what your "paradox" is) change that? In the formulation of your link, H gives the wrong answer for K. You propose that H instead should give no answer - but you haven't solved the problem.

5. From what I read, I see no reason that the algorithm couldn't be written to be aware of said infinite recursions.
O_o

How? (Keep in mind, we are talking any "P" and any "I". It is easily done for specific "P" and specific "I".) If you've actually solved that, you've gone along way in solving every undecidable problem and trashed all of information theory.

Soma

6. Originally Posted by CornedBee
The problem states that it is impossible to determine if P halts for an arbitrary P. How does introducing the answer "I don't know" (which is what your "paradox" is) change that? In the formulation of your link, H gives the wrong answer for K. You propose that H instead should give no answer - but you haven't solved the problem.
"I don't know" != "paradox". The paradox is that a boolean value simply _can't_ be returned, the very algorithm prevents it. There are certain ways of dealing with it in an accepting way.

But... the reason I think the above reasoning isn't even necessary in the first place is because:
The algorithm is infinity recursive (correct me if I wrong). P = K. K calls H, which calls K again, only, with an inverted I. A logical loop is entered, because P causes H to continue to ask itself for a contradictory answer. When processing an infinite logical loop, I don't see how it's not safe to say, that it never finishes, i.e., "false, it loops". (_even_ in a computationally quantum environment)

Originally Posted by phantomotap
How? (Keep in mind, we are talking any "P" and any "I". It is easily done for specific "P" and specific "I".) If you've actually solved that, you've gone along way in solving every undecidable problem and trashed all of information theory.
I'm not following. What's the relevance of P being "any" or "specific"?

Still on topic (though not dealing with the halting problem anymore), here's a good example of an "undecidable" problem:
(% being modulo)

400 % 0xFF = 145
∞ % 0xFF = ?

7. Originally Posted by Yarin
I'm not following. What's the relevance of P being "any" or "specific"?
If P is self-aware (let's call it P1), you defined a specific "P". But the halting problem exists for "any" P, not just P of the type P1.

All you proved is that the halting problem does not exist for P1. But that isn't the formulation of the problem.

8. Originally Posted by Mario F.
If P is self-aware (let's call it P1), you defined a specific "P". But the halting problem exists for "any" P, not just P of the type P1.

All you proved is that the halting problem does not exist for P1. But that isn't the formulation of the problem.
I didn't think that was the point of the problem, but I see your points nonetheless.
I'm not sure how one would go about testing "normal" algorithms in the first place, so I guess there's not much I can say about that altogether

9. Originally Posted by Yarin
I didn't think that was the point of the problem, but I see your points nonetheless.
It's not my point. It's how the problem is described.

Originally Posted by Yarin
I'm not sure how one would go about testing "normal" algorithms in the first place, so I guess there's not much I can say about that altogether
You can't test the halting problem using technology. Not until we can build a turing machine. Our current computers will throw one form or another of a stack overflow sometime during the loop. However, the problem is real and can can be demonstrated with the help of mathematics which, as you know, can go far beyond our technological limitations. And with mathematics it was also proved to be undecidable. So I agree, there is really not much you can say about it

In any case the halting problem poses a serious threat to any attempts at creating a turing machine: It can either be used as a demonstration of why a turing machine can never be built, or be used to demonstrate why a turing machine would be technologically useless to us.