Kozdęba, Agnieszka and Tyszka, Apoloniusz (2021) The distinction between existing algorithms and constructively defined algorithms inspires theorems and open problems that concern decidable sets X⊆N and cannot be formalized in mathematics understood as an a priori science as they refer to the current knowledge on X. [Preprint]
 | There is a more recent version of this item available. |
|
Text
ak_at.pdf Download (218kB) | Preview |
Abstract
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). Assuming that the infiniteness of a set X⊆N is false or unproven, we define which elements of X are classified as known. No known set X⊆N satisfies Conditions (1)-(4) and is widely known in number theory or naturally defined, where this term has only informal meaning. *** (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, though so far unproven, that X is infinite. (5) X is naturally defined. The infiniteness of X is false or unproven. X has the simplest definition among known sets Y⊆N with the same set of known elements. *** We define a set X⊆N which satisfies Conditions (1)-(5) except the requirement that X is naturally defined. Let P(n^2+1) denote the set of primes of the form n^2+1. Conditions (2)-(5) hold for X=P(n^2+1). We discuss a conjecture which implies the conjunction of Conditions (1)-(5) for X=P(n^2+1). 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. We present a table that shows satisfiable conjunctions consisting of Conditions (1)-(5) and their negations.
| Export/Citation: | EndNote | BibTeX | Dublin Core | ASCII/Text Citation (Chicago) | HTML Citation | OpenURL |
| Social Networking: |
| Item Type: | Preprint | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Creators: |
|
|||||||||
| Keywords: | conjecturally infinite set X⊆N; constructively defined integer n satisfies card(X)<ω ⇒ X⊆(-∞,n]; current knowledge on a set X⊆N; distinction between existing algorithms and constructively defined algorithms which are currently known; known elements of a set X⊆N whose infiniteness is false or unproven; physical limits of computation; primes of the form n^2+1; X is decidable by a constructively defined algorithm | |||||||||
| Subjects: | Specific Sciences > Mathematics > Foundations Specific Sciences > Mathematics > Logic Specific Sciences > Computation/Information |
|||||||||
| Depositing User: | Apoloniusz Tyszka | |||||||||
| Date Deposited: | 28 Nov 2021 20:17 | |||||||||
| Last Modified: | 28 Nov 2021 20:17 | |||||||||
| Item ID: | 19946 | |||||||||
| Subjects: | Specific Sciences > Mathematics > Foundations Specific Sciences > Mathematics > Logic Specific Sciences > Computation/Information |
|||||||||
| Date: | 26 November 2021 | |||||||||
| URI: | https://philsci-archive.pitt.edu/id/eprint/19946 |
Available Versions of this Item
-
The distinction between existing algorithms and constructively defined algorithms inspires theorems and open problems that concern decidable sets X⊆N and cannot be formalized in mathematics understood as an a priori science as they refer to the current knowledge on X. (deposited 28 Nov 2021 20:17)
[Currently Displayed]
-
The distinction between existing algorithms and constructively defined algorithms inspires theorems and open problems that concern decidable sets X⊆N and cannot be formalized in mathematics understood as an a priori science as they refer to the current knowledge on X. (deposited 10 Dec 2021 17:42)
-
The distinction between existing algorithms and constructively defined algorithms inspires theorems and open problems that concern decidable sets X⊆N and cannot be formalized in mathematics understood as an a priori science as they refer to the current knowledge on X. (deposited 04 Jan 2022 23:45)
- Theorems and open problems that concern decidable sets X⊆N and cannot be formulated in the formal language of classical mathematics as they refer to the current knowledge on X. (deposited 06 Mar 2022 20:25)
-
The distinction between existing algorithms and constructively defined algorithms inspires theorems and open problems that concern decidable sets X⊆N and cannot be formalized in mathematics understood as an a priori science as they refer to the current knowledge on X. (deposited 04 Jan 2022 23:45)
-
The distinction between existing algorithms and constructively defined algorithms inspires theorems and open problems that concern decidable sets X⊆N and cannot be formalized in mathematics understood as an a priori science as they refer to the current knowledge on X. (deposited 10 Dec 2021 17:42)
Monthly Views for the past 3 years
Monthly Downloads for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[feed]](http://philsci-archive.pitt.edu/style/images/feed-icon-32x32.png){kind=icon}