= 27d567bc2d48d9f40e9ccc20ea370b15)
cousin_it comments on No one knows what Peano arithmetic doesn't know - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (52)
The post wasn't talking about Turing machines that accept standard integers as input, it was talking about Turing machines with no arguments. If such a machine halts, then PA has a proof that just enumerates all the steps the machine takes before halting.
Ah thanks, it seems I misread the whole "is there an integer N such that T takes N steps" as "is there an integer N such that T takes some number of steps then halts", sorry about that - brain malfunction I guess. Though now that I see what you mean rather than what I thought you meant, good post! Not old news to me, but them I'm relatively new to computability theory.