Thread: 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.

List of undecidable problems - Wikipedia, the free encyclopedia

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.

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

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 = ?

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