# Reducing threshold questions to finiteness questions

It is usually simpler to reason about calculus where the limitation is finiteness of computation rather than a threshold like "computable in polynomial amount of time".

In formal languages theory for example, rather to use the $\exists n. x^{n+1} = x^n$ to characterize aperiodic monoïd, it is easier to use profinite words so that $x^{\omega+1} = x^{\omega}$.

In complexity theory, the only technic I know which is linked to that is the padding trick for example linking the problem of P vs NP to EXPTIME vs NEXPTIME. But the natural infinite equivalent of complexity questions would be computability ones'.

Are there some results that link complexity to computability questions using some encoding such that the resource threshold of complexity theory becomes a finiteness question of computation in computability theory ?

• Your example of profinite words is reminiscent of nonstandard arithmetic and analysis. From this viewpoint, one can view polynomial versus super-polynomial as the following finiteness question (I realize this is sort of a hack, but I think it's similar to the profinite word trick): Let $T(n)$ be the max runtime of Turing machine $M$ on inputs of length $n$. Then $M$ runs in polynomial time iff $\limsup_{n \to \infty} \log T(n) / n$ is finite. Probably this can be turned into a strange "profinite" model of computation in which the preceding expression really is the "runtime" in that model. – Joshua Grochow Jul 30 '13 at 17:58

Sipser proved that no infinite parity can be computed by an (infinite) circuit of any constant depth, which you can view as a warm-up to the result that PARITY is not in $AC^0$.
The fields of descriptive complexity, and implicit complexity could be viewed as taking this kind of approach. They both turn a resource constraint (like $P$ or $NP$) into expressibility of the problem in a logical formalism (for descriptive complexity) or in a specific programming language (for implicit complexity).