There’s an interesting corollary of semi-decidable languages that sounds like the kind of cool fact you would teach in class, but somehow I’ve never heard or read it anywhere.
A semi-decidable language is a set L⊆Σ∗ over a finite alphabet Σ such that there exists a Turing machine T such that, for any x∈Σ∗, if you run T on input x, then [if x∈L it halts after finitely many steps and outputs ‘1’, whereas if x∉L, it does something else (typically, it runs forever)].
The halting problem is semi-decidable. I.e., the language L of all bit codes of Turing Machines that (on empty input) eventually halt is semi-decidable. However, for any n∈N, there is a limit, call it f(n), on how long Turing Machines with bit code of length at most n can run, if they don’t run forever.[1] So, if you could compute an upper-bound u(n) on f(n), you could solve the halting problem by building a TM that
Computes the upper bound u(n)
Simulates the TM encoded by x for u(n) steps
Halts; outputs 1 if the TM halted and 0 otherwise
Since that would contradict the fact that L is not fully decidable, it follows that it’s impossible to compute an upper bound. This means that the function f not only is uncomputable, but it grows faster than any computable function.
An identical construction works for any other semi-decidable language, which means that any semi-decidable language determines a function that grows faster than any computable function. Which seems completely insane since 2^^^x is computable .
This just follows from the fact that there are only finitely many such Turing Machines, and a finite subset {T1,...,Tk} of them that eventually halt, so if Ti halts after pi steps, then the limit function is defined by f(n):=max{pi|1≤i≤k}.
There’s an interesting corollary of semi-decidable languages that sounds like the kind of cool fact you would teach in class, but somehow I’ve never heard or read it anywhere.
A semi-decidable language is a set L⊆Σ∗ over a finite alphabet Σ such that there exists a Turing machine T such that, for any x∈Σ∗, if you run T on input x, then [if x∈L it halts after finitely many steps and outputs ‘1’, whereas if x∉L, it does something else (typically, it runs forever)].
The halting problem is semi-decidable. I.e., the language L of all bit codes of Turing Machines that (on empty input) eventually halt is semi-decidable. However, for any n∈N, there is a limit, call it f(n), on how long Turing Machines with bit code of length at most n can run, if they don’t run forever.[1] So, if you could compute an upper-bound u(n) on f(n), you could solve the halting problem by building a TM that
Computes the upper bound u(n)
Simulates the TM encoded by x for u(n) steps
Halts; outputs 1 if the TM halted and 0 otherwise
Since that would contradict the fact that L is not fully decidable, it follows that it’s impossible to compute an upper bound. This means that the function f not only is uncomputable, but it grows faster than any computable function.
An identical construction works for any other semi-decidable language, which means that any semi-decidable language determines a function that grows faster than any computable function. Which seems completely insane since 2^^^x is computable .
This just follows from the fact that there are only finitely many such Turing Machines, and a finite subset {T1,...,Tk} of them that eventually halt, so if Ti halts after pi steps, then the limit function is defined by f(n):=max{pi|1≤i≤k}.