# The physical impossibility of machine computations on sufficiently large integers inspires an open problem that concerns abstract computable sets X⊆N and cannot be formalized in the set theory ZFC as it refers to our current knowledge on X

**Abstract**

Edmund Landau's conjecture states that the set P(n^2+1) of primes of the form n^2+1 is infinite. Let β=(((24!)!)!)!, and let Φ denote the implication: card(P(n^2+1))<ω ⇒ P(n^2+1)⊆(-∞,β]. We heuristically justify the statement Φ without invoking Landau's conjecture. The set X = {k∈N: (β<k) ⇒ (β,k)∩P(n^2+1) ≠ ∅} satisfies conditions (1)--(4). (1) There are a large number of elements of X and it is conjectured that X is infinite. (2) No known algorithm decides the finiteness/infiniteness of X . (3) There is a known algorithm that for every n∈N decides whether or not n ∈ X. (4) There is an explicitly known integer n such that card(X)<ω ⇒ X⊆(-∞,n]. (5) There is an explicitly known integer n such that card(X)<ω ⇒ X⊆(-∞,n] and some known definition of X is much simpler than every known definition of X \ (-∞,n]. The following problem is open: Is there a set X⊆N that satisfies conditions (1)--(3) and (5)? The set X=P(n^2+1) satisfies conditions (1)--(3). The set X={k∈N : the number of digits of k belongs to P(n^2+1)} contains 10^{10^{450}} consecutive integers and satisfies conditions (1)--(3). The statement Φ implies that both sets X satisfy condition (5).

**Keywords**

computable set X⊆N currently known/unknown theorems about X explicitly known integer n finiteness (infiniteness) of X remains conjectured known algorithm for every n \in N decides whether or not n \in X large number of elements of X mathematical statement that cannot be formalized in ZFC n bounds X, if X is finite no known algorithm decides the finiteness of X

**Categories**

(categorize this paper)

**PhilPapers/Archive ID**

TYSDAS

**Revision history**

References found in this work BETA

Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers.Odifreddi, Piergiorgio

Definability and Decision Problems in Arithmetic.Robinson, Julia

Citations of this work BETA

No citations found.

**Added to PP index**

2017-10-17

**Total views**

723 ( #4,837 of 50,072 )

**Recent downloads (6 months)**

101 ( #4,939 of 50,072 )

How can I increase my downloads?

**Downloads since first upload**

*This graph includes both downloads from PhilArchive and clicks to external links.*