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
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at

Reply via email to