5 ms·
The halting problem, for instance: whether or not a e.g. Turing machined will halt on a given input or loop endlessly.
by ihodes 16y ago
The halting problem, for instance: whether or not a e.g. Turing machined will halt on a given input or loop endlessly.
- kanak 16y agoSorry if i wasn't being clear. I mean problems that remain undecidable even when you have an oracle for the Halting Problem.
- robinhouston 16y agoI don't know whether you‘re going to like it, but the most obvious example of a problem that is undecidable even given an oracle for the halting problem is the next halting problem up: i.e. given a Turing machine that has an oracle for the halting problem, does it halt?
- wlievens 16y agoTurtles all the way down.