According to wikipedia (http://en.wikipedia.org/wiki/%CE%A9-consistent_theory#Definition): "$\Sigma_n$-soundness has the following computational interpretation: if the theory proves that a program C using a $\Sigma_{n-1}$-oracle halts, then C actually halts". Assuming this statement is correct, I have a doubt about the "if" part: Is every $\Sigma_n$ formula of PA semantically equivalent to a statement saying that a given program C using a $\Sigma_{n-1}$-oracle halts? or only some $\Sigma_n$ formulas, but not all of them are? Thanks!

Bonus questions: If there are formulas that are not equivalent to a halting problem, are they equivalent to some other analogy regarding Turing machines? and, are there PA sentences that are not semantically equivalent to any computational analogy?


Yes, by Post's theorem, for every $\Sigma^0_{m+1}$ formula $\phi(x)$ there is an oracle Turing machine $e$ such that, for every $i$, $\phi(i)$ holds if and only if machine $e$ halts on input $i$ when run with oracle $\emptyset^{(m)}$. Here $\emptyset^{(m)}$ is the $m$th Turing jump of the empty set, and is a $\Sigma^0_m$ set.

In general, Post's theorem shows that there is an extremely close connection between the arithmetical hierarchy, computability, and the sets $\emptyset^{(m)}$. The claim in the Wikipedia article is just one part of this connection.

Start with the negation of the twin primes conjecture. The negation is $\Sigma^0_2$ and thus by Post's theorem is equivalent to the claim that some particular oracle machine halts when it is run with $\emptyset'$ an oracle. Since there are no free variables, that machine does the same thing regardless of input - it ignores the input.

In this particular case, what the machine does is to search for the least $k$ such that there is no pair of twin primes greater than $k$, and then halts if it finds such a $k$. The oracle $\emptyset'$ is able to decide the set $$\{ k : \text{ there is a pair of twin primes greater than } k\}$$ because that set is $\Sigma^0_1$ and $\emptyset'$ is $\Sigma^0_1$ complete. So the oracle machine is able to use the oracle $\emptyset'$ to repeatedly test whether each $k$ is in the set and then halt if it finds a $k$ that is not in the set.

The the original twin primes conjecture is then equivalent to the claim that that machine does not halt when run with an oracle for $\emptyset'$. If it never halts, that means it never finds a $k$ such that there is no pair of twin primes greater than $k$, so there are arbitrarily large pairs of twin primes, and vice versa.

  • $\begingroup$ Thanks! It is still confusing to me what would be the interpretation for a φ that doesn't have any free variables. For instance, let us take the twin prime conjecture : ∀k:∃n:n>k∧ϕ(n) with ϕ(n) defined as "n−1 is prime and n+1 is prime". Since ϕ(n) is $\Pi_0^0$, φ is $\Pi_2^0$. So, what would be the statement for Post's theorem for φ? Specifically, I dont know what would play the role of "i" in "for every i, φ (i) holds if and only if machine e halts on input i ". What is "i" if there are no free variables in φ? $\endgroup$ – Wolphram jonny Dec 2 '12 at 22:33
  • $\begingroup$ I appended an explanation to my answer. $\endgroup$ – Carl Mummert Dec 2 '12 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.