[Alta-Logic] Peripatetic seminar Wed 26th

[Robin Cockett]

Speaker: Pavel Hrubes
Place: ICT 616
Time: Wed. 26th Jan 2011, 3:30pm

Title:    On twin non-computable functions (continued)

Abstract:
Assume that we have a set X and a total recursive function f such that 
for every n, X differs from the n-th r.e. set W_n in the point f(n). 
Then X is strong enough to compute the Halting problem 0'. A similar 
observation applies when we replace "n-th r.e. set" by "n-th 
arithmetical set" and 0' by 0^{\omega}. We investigate what happens, if 
instead of being given a single point where X and W_n differ, we are 
given a finite list of candidates to choose from.