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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---

Reply via email to