[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
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
************************************************************************
More information about the FOM
mailing list