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 ⇐ n states that belong to family T’ must be at least 2^(-k’-1) for all n >= k’.
Now let’s start running all programs and as we go along let’s keep track of whether, for each value of n, a proportion greater than or equal to 1 − 2^(-k’-1) of programs of length ⇐ n have halted in fewer than f(n) steps. Eventually this will be true for some n >= k’. At that point, we check to see whether one of the programs in T’ has halted. If not, then none of the programs in T’ can halt, and neither can T.
Therefore, such a function f could be used to solve the halting problem.
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 ⇐ n states that belong to family T’ must be at least 2^(-k’-1) for all n >= k’.
Now let’s start running all programs and as we go along let’s keep track of whether, for each value of n, a proportion greater than or equal to 1 − 2^(-k’-1) of programs of length ⇐ n have halted in fewer than f(n) steps. Eventually this will be true for some n >= k’. At that point, we check to see whether one of the programs in T’ has halted. If not, then none of the programs in T’ can halt, and neither can T.
Therefore, such a function f could be used to solve the halting problem.