[FOM] Computability question

Daniel Schwartz schwartz at cs.fsu.edu
Sat Mar 30 22:02:06 EDT 2013

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

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

More information about the FOM mailing list