A polynomial-time Turing machine algorithm is considered efficient if its run-ti
ID: 648045 • Letter: A
Question
A polynomial-time Turing machine algorithm is considered efficient if its run-time, in the worst-case, is bounded by a polynomial function in the input size. I'm aware of the strong Church-Turing thesis:
Any reasonable model of computation can be efficiently simulated on Turing machines
However, I'm not aware of solid theory for analyzing the computational complexity of algorithms of ?-calculus.
Do we have a notion of computational efficiency for every known model of computation? Are there any models that are only useful for computability questions but useless for computational complexity questions?
Explanation / Answer
As far as I know, the main models of computability are ?-calculus, Turing machines and recursive functions. I am not aware of the situation regarding complexity in recursive functions, they may or may not be useless for complexity.
It may be seen as a fortunate coincidence that Turing machines, which are not so arguably very inefficient machines, are also a very good model of complexity. What made things natural is that there are a lot of transformations involving TMs that are polynomial. (Universal machine, simulation of a n-taped machine with a 1-taped machine, from an arbitrary alphabet to a binary one, simulating a PRAM, ...) and that polynomials are a class of functions stable by arithmetic operations and composition