[FOM] Computability question

[Kreinovich, Vladik]

While there are many theorems of equivalence of polynomial time class on different computational devices (different types of Turing machines, Kolmogorov-Uspensky algorithms, etc.), the situation with recursive functions is different: they are equivalent from the viewpoint of what is computable, but they are clearly not equivalent when it comes to comparing the number of elementary operations. For example, a standard definition of addition as a recursive function is, in normal mathematical notations, add(n,0)=n and add(n,m+1)= add(n,m)+1. This means that to compute n+m, we need to perform m successor operations (and no fewer is possible, since each operation increases by 1). For m = 2^k, a number represented by k+1 digits, this means that we need the number of computational steps which is exponential in terms of the length of the input. 

-----Original Message-----
From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] On Behalf Of Daniel Schwartz
Sent: Thursday, March 28, 2013 8:01 PM
To: fom at cs.nyu.edu
Subject: [FOM] Computability question

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
************************************************************************
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom