On 4/24/07, Orr Dunkelman <[EMAIL PROTECTED]> wrote:
Actually, courtesy of Galois we know functions which are well defined, that can be easily verified and not computed efficiently - the roots of general polynomials over R of degree > 4. Specifically, to incorporate this problem to the Turing model, you must assume that the machine can work with real numbers (over bits), which is not the case. But when you define a "Real-number turing machine" you get that for this machine P is not equal to NP.
I haven't thouht much about deterministic infinite-numbers turing machines. I don't know how consistent such a theory can be. I assume any theory or field of numbers can prove itself to be inconsistent, if it can express something like "this sentence is true if and only if this sentence is false". But if such a turing machine exists even in theory (and I don't think it does), it appears to be a very strong computation system to me. It can solve all the problems in the universe in one single step, compute an infinite number of decision functions as once. Uri. ================================================================= To unsubscribe, send mail to [EMAIL PROTECTED] with the word "unsubscribe" in the message body, e.g., run the command echo unsubscribe | mail [EMAIL PROTECTED]
