[FOM] Computability question
Kreinovich, Vladik
vladik at utep.edu
Fri Mar 29 18:29:00 EDT 2013
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
More information about the FOM
mailing list