[comp.theory] Shannon-de Leeuw theorem

litow@csd4.csd.uwm.edu (Bruce E Litow) (11/29/89)

The Shannon-de Leeuw theorem says that if a set,S,is enumerated with
positive probability by  a Turing machine that uses a random binary
string as additional resource,then S is R.E. Solovay has given a
sharper version of this. Does this cease to hold if R.E. is replaced
various notions of sub-recursive enumerability ?