Jesse Mazer:
I have a vague memory that there was some result showing the algorithmic
> complexity of a string shouldn't depend too strongly on the details of the
> Turing machine--that it would only differ by some constant amount for any
> two different machines, maybe? Does this ring a bell with anyone?
That is correct, but the constant is a multiplicative one, and could be made
arbitrarily large.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Tue Apr 11 2006 - 03:49:49 PDT