[FOM] Computability question
Daniel Schwartz
schwartz at cs.fsu.edu
Thu Mar 28 22:01:16 EDT 2013
Dear FOM list,
I am new to this list and so don't know if this issue has previously been
discussed, but I have a question:
Is the property of polynomial time computability invariant among the
various models of computation?
In particular, suppose we define the complexity of a recursive function
definition as the number of applications of elementary functions (successor,
zero, projection) required to evaluate the definition for a given argument.
Then a question is: Is there a one-to-one correspondence between polynomial
time recursive function definitions and polynomial time Turing machines?
I haven't been able to find any indication that anyone has worked on this
problem. Would you know of any, and of any results along these lines?
Thanks and 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