Russell, The wikipedia article Ben cites is definitely meant for mathematicians, so I will try to give an example.
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. This is a somewhat odd way of constructing it, but I hope it is understandable. Other references: http://en.wikipedia.org/wiki/Hypercomputation http://en.wikipedia.org/wiki/Arithmetical_hierarchy --Abram On Tue, Oct 21, 2008 at 2:27 PM, Russell Wallace <[EMAIL PROTECTED]> wrote: > On Tue, Oct 21, 2008 at 4:53 PM, Abram Demski <[EMAIL PROTECTED]> wrote: >> As it happens, this definition of >> meaning admits horribly-terribly-uncomputable-things to be described! >> (Far worse than the above-mentioned super-omegas.) So, the truth or >> falsehood is very much not computable. >> >> I'm hesitant to provide the mathematical proof in this email, since it >> is already long enough... let's just say it is "available upon >> request". > > Now I'm curious -- can these horribly-terribly-uncomputable-things be > described to a non-mathematician? If so, consider this a request. > > > ------------------------------------------- > 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/?&; > Powered by Listbox: http://www.listbox.com > ------------------------------------------- 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
