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

EasyChair Preprint no. 3648

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).

Keyphrases: complexity of a mathematical definition, computable set X⊆N, current knowledge on X, explicitly known integer n, impossibility of computations on large integers, infiniteness of X remains conjectured, n bounds X from above when X is finite, no known algorithm decides the finiteness of X, statement that cannot be formalized in ZFC

@Booklet{EasyChair:3648,
  author = {Sławomir Kurpaska and Apoloniusz Tyszka},
  title = {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},
  howpublished = {EasyChair Preprint no. 3648},

  year = {EasyChair, 2020}}