Talk:Post's theorem

Comments 2006-10-25

The article has been sitting in a half-finished state for a while. I expanded it and set it up for further improvement.

• This article needs to be at an undergraduate level at the highest
• More references, especially at the undergrad level, are needed
• The notation should be kept as simple as possible (but not more simple than that).
• I think that a proof would be nice, and the proof is elementary anyway.
• More corollaries would be good.

CMummert 13:42, 25 October 2006 (UTC)

Quantifier Blocks

I believe the 'alternative' definition I added using quantifier blocks and bounded quantifiers should probably be the primary definition. However, I don't remember and need to get back to working on my thesis.Logicnazi (talk) 02:46, 24 November 2007 (UTC)

Definition of $\Sigma _{m}^{0}$

The definition of $\Sigma _{m}^{0}$ differs from the traditional one for $m=0$ since it would not allow bounded quantifiers. Since Post theorem doesn't say anything about $\Sigma _{0}^{0}$ relation this doesn't affect the theorem, but it seems misleading. Catrincm (talk) 13:34, 30 September 2014 (UTC)

T halts on input n at time n₁ at most if and only if $\varphi (n,n_{1})$ is satisfied

What does it mean: "at most if and only if"? Is it equivalence or one-direction consequence?

Eugepros (talk) 10:08, 6 October 2018 (UTC)