[FOM] Re: Addition with Primality: Decidability and Heuristics

[Zahidi Karim]

Perhaps this is unknown to some people (at leats it hasn't come up in the 
discussion so far) but there is a paper  proving the undecidability of 
addition and primality assuming Schinzel's Hypothesis. It appeared in the 
Journal of Symbolic Logic  in the mid nineties. The authors include Alan 
Woods and Jockusch. The show that, assuming Schinzel's Hypothesis, one 
dcan define the image of a polynomial of degree at least 2 from which the 
undecidability the follows. A slight refinement of their result, due to 
Maurice Boffa only needs the linear case of Schinzel's Hypothesis.

Karim Zahidid