Formalizing the notions of non-interactive and interactive algorithms
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912696546361344 |
|---|---|
| author | Middelburg, C. A. |
| author_facet | Middelburg, C. A. |
| contents | An earlier paper gives an account of a quest for a satisfactory formalization of the classical informal notion of an algorithm. That notion only covers algorithms that are deterministic and non-interactive. In this paper, an attempt is made to generalize the results of that quest first to a notion of an algorithm that covers both deterministic and non-deterministic algorithms that are non-interactive and then further to a notion of an algorithm that covers both deterministic and non-deterministic algorithms that are interactive. The notions of an non-interactive proto-algorithm and an interactive proto-algorithm are introduced. Non-interactive algorithms and interactive algorithms are expected to be equivalence classes of non-interactive proto-algorithms and interactive proto-algorithms, respectively, under an appropriate equivalence relation. On both non-interactive proto-algorithms and interactive proto-algorithms, three equivalence relations are defined. Two of them are deemed to be bounds for an appropriate equivalence relation and the third is likely an appropriate one. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_19037 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Formalizing the notions of non-interactive and interactive algorithms Middelburg, C. A. Computational Complexity Data Structures and Algorithms Logic in Computer Science F.1.1; F.1.2; F.2.0 An earlier paper gives an account of a quest for a satisfactory formalization of the classical informal notion of an algorithm. That notion only covers algorithms that are deterministic and non-interactive. In this paper, an attempt is made to generalize the results of that quest first to a notion of an algorithm that covers both deterministic and non-deterministic algorithms that are non-interactive and then further to a notion of an algorithm that covers both deterministic and non-deterministic algorithms that are interactive. The notions of an non-interactive proto-algorithm and an interactive proto-algorithm are introduced. Non-interactive algorithms and interactive algorithms are expected to be equivalence classes of non-interactive proto-algorithms and interactive proto-algorithms, respectively, under an appropriate equivalence relation. On both non-interactive proto-algorithms and interactive proto-algorithms, three equivalence relations are defined. Two of them are deemed to be bounds for an appropriate equivalence relation and the third is likely an appropriate one. |
| title | Formalizing the notions of non-interactive and interactive algorithms |
| topic | Computational Complexity Data Structures and Algorithms Logic in Computer Science F.1.1; F.1.2; F.2.0 |
| url | https://arxiv.org/abs/2405.19037 |