The physical limits of computation inspire an open problem that concerns decidable sets X⊆N and cannot be formalized in ZFC as it refers to the current knowledge on X

Download Edit this record How to cite View on PhilPapers
Let f(1)=2, f(2)=4, and let f(n+1)=f(n)! for every integer n≥2. Edmund Landau's conjecture states that the set P(n^2+1) of primes of the form n^2+1 is infinite. Landau's conjecture implies the following unproven statement Φ: card(P(n^2+1))<ω ⇒ P(n^2+1)⊆[2,f(7)]. Let B denote the system of equations: {x_i!=x_k: i,k∈{1,...,9} ∪ {x_i⋅x_j=x_k: i,j,k∈{1,...,9}}. We write down some system U⊆B of 9 equations which has exactly two solutions in positive integers x_9,...,x_9, namely (1,...,1) and (f(1),...,f(9)). No known system S⊆B with a finite number of solutions in positive integers x_1, . . . , x_9 has a solution (x_1,. . .,x_9)∈(N\{0})^9 satisfying max(x_1,..., x_9)>f (9). We write down some system A of 8 equations. Let Λ denote the statement: if the system A has at most finitely many solutions in positive integers x_1,...,x_9, then each such solution (x_1,...,x_9) satisfies x_1,...,x_9≤f(9). The statement Λ is equivalent to the statement Φ. This heuristically proves the statement Φ . This proof does not yield that card(P(n^2+1))=ω. Algorithms always terminate. We explain the distinction between existing algorithms (i.e. algorithms whose existence is provable in ZFC) and known algorithms (i.e. algorithms whose definition is constructive and currently known to us). Conditions (1)-(5) concern sets X⊆N. (1) A known algorithm with no input returns an integer n satisfying card(X)<ω ⇒ X⊆(-∞,n]. (2) A known algorithm for every k∈N decides whether or not k∈X. (3) No known algorithm with no input returns the logical value of the statement card(X)=ω. (4) There are many elements of X and it is conjectured that X is infinite. (5) X has the simplest definition among known sets Y⊆N with the same set of known elements. It seems that conditions (1)-(5) imply that the set X is naturally defined, where this term has only informal meaning. The open problem of the title asks: Is there a set X⊆N which satisfies conditions (1)-(5)? The set X= P(n^2+1) satisfies conditions (2)-(5). Condition (1) remains unproven for X= P(n^2+1). The set X={k∈N: (f(7)<k) ⇒ (f(7),k)∩P(n^2+1)≠∅} satisfies conditions (1)-(4) and does not satisfy condition (5). No set X⊆N will satisfy conditions (1)-(4) forever, if for every algorithm with no input, at some future day, a computer will be able to execute this algorithm in 1 second or less. The physical limits of computation disprove this assumption. The statement Φ implies that conditions (1)-(5) hold for X=P(n^2+1).
PhilPapers/Archive ID
Upload history
First archival date: 2017-10-17
Latest version: 195 (2021-03-30)
View other versions
Added to PP index

Total views
914 ( #4,542 of 58,310 )

Recent downloads (6 months)
131 ( #4,217 of 58,310 )

How can I increase my downloads?

Downloads since first upload
This graph includes both downloads from PhilArchive and clicks on external links on PhilPapers.