On Tue, Oct 21, 2008 at 8:13 PM, Abram Demski <[EMAIL PROTECTED]> wrote: > The wikipedia article Ben cites is definitely meant for > mathematicians, so I will try to give an example.
Yes indeed -- thanks! > The halting problem asks us about halting facts for a single program. > To make it worse, I could ask about an infinite class of programs: > "All programs satisfying Q eventually halt." If Q is some computable > function that accepts some programs and rejects others, it is only "a > little" worse than the halting problem; Call this halting2. If Q is > more difficult to evaluate than that, say if Q is as hard as solving > the halting problem, it's more difficult; call problems like this > halting3. If Q is as hard as halting2, then call that halting4. If Q > is as hard as halting3, then call the resulting class halting4. And so > on. Right -- if I understand correctly, this is equivalent to the line of reasoning I came up when I first saw the proof of the incomputability of the halting problem: suppose you have an oracle that can solve the halting problem, can that answer all questions? No, because by the same logic you can show that to predict the behavior of an oracle requires a super oracle. But I was under the impression this is just the same as the super Omegas? And that you were talking about something beyond that? ------------------------------------------- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?member_id=8660244&id_secret=117534816-b15a34 Powered by Listbox: http://www.listbox.com
