Good programmers use their brains, but good guidelines save us having to think out every case.
I am doing a startup!
Cross-browser testing from your browser!
I have written my fourth book!
Be faster than Larry Wall in the shell!
You're viewing a comment by Ikosarakt and its responses.
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.
(why do I need your e-mail?)
It would be nice if you left your e-mail address. Sometimes I want to send a private message, or just thank for the great comment. Having your e-mail really helps.
I will never ever spam you.
(Your twitter handle, if you have one.)
* use <pre>...</pre> to insert a plain code snippet.
* use <pre lang="lang">...</pre> to insert a syntax highlighted code snippet.
For example, <pre lang="python">...</pre> will insert Python highlighted code.
* use <code>...</code> to highlight a variable or a single shell command.
* use <a href="url" nospam>title</a> to insert links.
<a href="url" nospam>title</a>
* use other HTML tags, such as, <b>, <i>, <blockquote>, <sup>, <sub> for text formatting.
Type the word "floppy_163": (just to make sure you're a human)
Please preview the comment before submitting to make sure it's OK.
Peter Krumins' blog about programming, hacking, software reuse, software ideas, computer security, browserling, google and technology.
Reach me at:
Or meet me on:
Subscribe through an RSS feed:
(what is rss?)
Subscribe through email:
Enter your email address:
Delivered by FeedBurner
I love to read science books. They make my day and I get ideas for awesome blog posts, such as Busy Beaver, On Functors, Recursive Regular Expressions and many others.
Take a look at my Amazon wish list, if you're curious about what I have planned reading next, and want to surprise me. :)
See all top articles
See all downloads
See more detailed list of recent articles
See more detailed category information
See more detailed list of all articles