Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.20432 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912603834417152 |
|---|---|
| author | Lau, Desmond |
| author_facet | Lau, Desmond |
| contents | We modify Gurevich's definition of sequential algorithms, so that it becomes amenable to computation with arbitrarily large sets on a sufficiently intuitive level. As a result, two classes of abstract algorithms are obtained, namely generalised sequential algorithms (GSeqAs) and generalised sequential algorithms with parameters (GSeqAPs). We derive from each class a relative computability relation on sets which is analogous to the Turing reducibility relation on reals. We then prove that the relative computability relation derived from GSeqAPs is equivalent to the relative constructibility relation in set theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20432 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Relative Constructibility via Generalised Sequential Algorithms Lau, Desmond Logic in Computer Science 68Q09 (Primary) 03D60 (Secondary) F.1.1; F.1.3; F.4.1 We modify Gurevich's definition of sequential algorithms, so that it becomes amenable to computation with arbitrarily large sets on a sufficiently intuitive level. As a result, two classes of abstract algorithms are obtained, namely generalised sequential algorithms (GSeqAs) and generalised sequential algorithms with parameters (GSeqAPs). We derive from each class a relative computability relation on sets which is analogous to the Turing reducibility relation on reals. We then prove that the relative computability relation derived from GSeqAPs is equivalent to the relative constructibility relation in set theory. |
| title | Relative Constructibility via Generalised Sequential Algorithms |
| topic | Logic in Computer Science 68Q09 (Primary) 03D60 (Secondary) F.1.1; F.1.3; F.4.1 |
| url | https://arxiv.org/abs/2412.20432 |