You're replying to a comment by Ikosarakt.

Ikosarakt Permalink
February 04, 2013, 10:37

Now imagine 2nd order Turing machine, which can solve halting problem for normal Turing machine. It is also known as Oracle Turing machine. When it halts itself? There exists 2nd order Busy Beaver function: BB_2(n). Interestingly, it dominates functions like BB(BB(BB(...(BB(n)...) (with BB(n) BB's). Probably even BB_2(6) > BB(BB(BB(BB(BB(BB(6)))))) (although I have no proof at the time being). Actually, BB_2(n) dominates any level of diagonalisation of BB(n) function. In the fast-growing hierarchy BB_2(n) in corresponds to f_((w_1^CK)*2)(n), where w_1^CK is Church-Kleene ordinal.

Naturally, after this follows 3rd order Turing machines, which can solve the halting problem for 2nd order Turing machines. It can calculate BB_2(n) and, of course, BB(n). Now there are BB_3(n) function, which is uncomputable for the 3rd order Turing machine. We can continue with BB_4(n), BB_5(n), BB_6(n), and so on. In general, BB_x(n) grows as fast as f_((w_1^CK)*x)(n).

If you familiar with limit ordinals you can guess that after it follows new, super Turing machine (with order w) that can calculate BB_x(n) for all finite x and n. However, it again can's solve halting problem for itself! We need (w+1)-th order Turing machine for it. More generally, BB_alpha(n) can be solved using Turing machine with order alpha+1. Each such function grows as fast as f_((w_1^CK)*alpha)(n). Now we can turn alpha into w_1^CK itself, and obtain growth rate f_((w_1^CK)^2)(n), and so on. Note: I used w to represent omega, since they are look similar.

Reply To This Comment

(why do I need your e-mail?)

(Your twitter handle, if you have one.)

Type the word "linux_163": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.