[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