My knowledge of computability is far from extensive so please forgive me if this is a stupid question.
Does an oracle being able to determine if a statement is provable in Peano arithmetic necessarily be capable of proving that all of the Turing machines that halt for standard integers do in fact halt? Or to put it another way, is there a Turing machine that operates on some standard integer that cannot be proved in Peano arithmetic?
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.
My knowledge of computability is far from extensive so please forgive me if this is a stupid question.
Does an oracle being able to determine if a statement is provable in Peano arithmetic necessarily be capable of proving that all of the Turing machines that halt for standard integers do in fact halt? Or to put it another way, is there a Turing machine that operates on some standard integer that cannot be proved in Peano arithmetic?
Thanks.
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.