The set of all (valid) Peano Arithmetic theorems is not computably enumerable- wouldn’t this mean that a listener with a rich hypothesis space doesn’t need to assign a probability to the speaker enumerating them (thereby undermining the argument)?
I guess an important distinction is between computable and computably enumerable- I’m not perfect with CS, but it seems that this proof rests on the PA theorems being computably enumerable, but not computable themselves- is my read on this correct? But it seems to me that one can only enumerate the (valid) theorems by actually computing them
The set of theorems of PA is computably enumerable, but the set of theorems and anti-theorems (things provably false) is not computably separable, IE there is no computation which returns “true” for theorems, “false” for anti-theorems, and always returns some answer (we don’t care specifically what that answer is for anything that’s not a theorem or anti-theorem).
The set of all (valid) Peano Arithmetic theorems is not computably enumerable- wouldn’t this mean that a listener with a rich hypothesis space doesn’t need to assign a probability to the speaker enumerating them (thereby undermining the argument)?
I guess an important distinction is between computable and computably enumerable- I’m not perfect with CS, but it seems that this proof rests on the PA theorems being computably enumerable, but not computable themselves- is my read on this correct? But it seems to me that one can only enumerate the (valid) theorems by actually computing them
The set of theorems of PA is computably enumerable, but the set of theorems and anti-theorems (things provably false) is not computably separable, IE there is no computation which returns “true” for theorems, “false” for anti-theorems, and always returns some answer (we don’t care specifically what that answer is for anything that’s not a theorem or anti-theorem).