[FOM] Complexity of (Universal) Turing Machines

Ilya Tsindlekht eilya497 at 013.net
Tue Apr 22 02:38:55 EDT 2008


On Tue, Apr 22, 2008 at 10:30:07AM +1000, Steve Gardner wrote:
> function. For any UTM T and finite string D (regarded here as the data),  
> there is guaranteed to be a shortest program of length L which outputs D  
> when input to T. 
L is called Kolmogorov complexity of D, you might like to look up the
literature on it.


More information about the FOM mailing list