Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uwm.edu!csd4.csd.uwm.edu!litow
From: litow@csd4.csd.uwm.edu (Bruce E Litow)
Newsgroups: comp.theory
Subject: Shannon-de Leeuw theorem
Message-ID: <1232@uwm.edu>
Date: 28 Nov 89 17:23:24 GMT
Sender: news@uwm.edu
Reply-To: litow@csd4.csd.uwm.edu (Bruce E Litow)
Organization: University of Wisconsin-Milwaukee
Lines: 5

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 ?


Brought to you by Super Global Mega Corp .com