[FOM] Computability question

[Daniel Schwartz]

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
************************************************************************