[FOM] Computability question
Kreinovich, Vladik
vladik at utep.edu
Sat Mar 30 23:59:53 EDT 2013
What you describe is Turing computations with UNARY numbers, when people talk about polynomial-time computations they mean binary (or, equivalently, decimal) numbers, in this case, the usual algorithm for addition is linear time (and thus, polynomial time).
In terms of further reading, I suggest M. Sipser, Introduction to the Theory of Computation, this is a good intro book, at our university, we have been using it for a few years.
-----Original Message-----
From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] On Behalf Of Daniel Schwartz
Sent: Saturday, March 30, 2013 8:02 PM
To: fom at cs.nyu.edu
Subject: [FOM] Computability question
Dear Vladik,
Thank you for your reply. Could you tell me where those results you mentioned have been published? I would like to read up on this issue.
I'm not convinced the example you give is really a counter example. To do addition, n+m, on a Turing machine, one would start out with n 1s followed by a blank space followed by m 1s, and the machine would need only to shift each of the m 1s one place to the left. This would take time proportional to m, which is the number of iterations of Successor needed to compute n+m according to the recursive function definition. So both the Turing machine and the recursive definition have the same complexity.
Since no one else has replied, I'm guessing that this is still an open question.
Best regards,
--Dan Schwartz
************************************************************************
Dr. Daniel G. Schwartz Office 850-644-5875
Dept. of Computer Science, MC 4530 CS Dept 850-644-4029
Florida State University Fax 850-644-0058
Tallahassee, FL 32306-4530 schwartz at cs.fsu.edu
U.S.A. http://www.cs.fsu.edu/~schwartz
************************************************************************
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom
More information about the FOM
mailing list