But strictly stronger in consistency strength, of course. (Consistency strength turns out to be more fundamental than logical strength simpliciter.)
Question: Is there is a computable function f(n) such that g(f)(n) goes to 1 as n goes to infinity.
Well, let’s say we want to know whether Turing machine T halts. Say T has k states. Can’t we use T’s program to find a family of programs T’ which are essentially the same as T except they consist of a common prefix followed by arbitrary suffix? Let k’ be the number of states in the ‘prefix’. The proportion of programs with less than n states that belong to family T’ must tend to 2^(-k’) as n goes to infinity. If we choose n such that g(f)(n) > 1 − 2^(-k’) then we just need to run all members of T’ for f(n) steps. If none of them have halted then T does not halt.
Therefore, such a function f could be used to solve the halting problem.
But strictly stronger in consistency strength, of course. (Consistency strength turns out to be more fundamental than logical strength simpliciter.)
Well, let’s say we want to know whether Turing machine T halts. Say T has k states. Can’t we use T’s program to find a family of programs T’ which are essentially the same as T except they consist of a common prefix followed by arbitrary suffix? Let k’ be the number of states in the ‘prefix’. The proportion of programs with less than n states that belong to family T’ must tend to 2^(-k’) as n goes to infinity. If we choose n such that g(f)(n) > 1 − 2^(-k’) then we just need to run all members of T’ for f(n) steps. If none of them have halted then T does not halt.
Therefore, such a function f could be used to solve the halting problem.