Eliezer_Yudkowsky comments on Standard and Nonstandard Numbers - Less Wrong

31 Post author: Eliezer_Yudkowsky 20 December 2012 03:23AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (83)

You are viewing a single comment's thread. Show more comments above.

Comment author: Eliezer_Yudkowsky 20 December 2012 10:21:46PM 7 points [-]

It's even worse than that, the function for the maximum number of nodes you end up before they start going down, if you play using the worst possible strategy, increases faster than any function which Peano arithmetic can prove to be total (i.e., it grows faster than any Turing machine run on various inputs, which Peano arithmetic can prove to halt for any input). To say that this grows faster than the Ackermann function is putting it very mildly.