[FOM] Computability question

[Kreinovich, Vladik]

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