On the formalization of the notion of an interactive algorithm

Autor:	Middelburg, C. A.
Rok vydání:	2024
Předmět:	Computer Science - Computational Complexity Computer Science - Data Structures and Algorithms Computer Science - Logic in Computer Science F.1.1 F.2.0
Druh dokumentu:	Working Paper
Popis:	An earlier paper gives an account of a quest for a satisfactory formalization of the classical informal notion of an algorithm. In this paper, an attempt is made to generalize the results of that quest to the informal notion of an interactive algorithm. The notion of an interactive proto-algorithm is introduced. Interactive algorithms are expected to be equivalence classes of interactive proto-algorithms under an appropriate equivalence relation. As in the non-interactive case, 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. Comment: 17 pages, corrected errors in Section 4 and updated reference
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2405.19037 Zobrazit plný text záznamu View this record from Arxiv