Published in Volume XXXV, Issue 2, 2025, pages 211–249, doi:10.47743/SACS.2025.2.211
Author: C.A. Middelburg
Abstract
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.
References
[1] Jos C. M. Baeten, Bas Luttik, and Paul van Tilburg. Reactive Turing machines. Information and Computation, 231:143–166, 2013. doi: 10.1016/j.ic.2013.08.010.
[2] Andreas Blass and Yuri Gurevich. Ordinary interactive small-step algorithms, I. ACM Transactions on Computational Logic, 7(2):363– 419, 2006. doi:10.1145/1131313.1131320.
[3] Manfred Broy. Computability and realizability for interactive computations. Information and Computation, 241:277–301, 2015. doi: 10.1016/j.ic.2014.12.019.
[4] Edsger W. Dijkstra. A Short Introduction to the Art of Programming, volume 316 of EWD. Technische Hogeschool Eindhoven, 1971.
[5] Robert W. Floyd. Nondeterministic algorithms. Journal of the ACM, 14(4):636–644, 1967. doi:10.1145/321420.321422.
[6] Dina Q. Goldin, Scott A. Smolka, Paul C. Attie, and Elaine L. Sonderegger. Turing machines, transition systems, and interaction. Information and Computation, 194(2):101–128, 2004. doi:10.1016/j.ic.2004.07.002.
[7] Cliff B. Jones. Systematic Software Development Using VDM. Prentice- Hall, second edition, 1990.
[8] Stephen Cole Kleene. Mathematical Logic. John Wiley and Sons, New York, 1967.
[9] Donald E. Knuth. The Art of Computer Programming: The Fundamental Algorithms. Addison Wesley Longman, Redwood City, CA, third edition, 1997.
[10] Anatoly Ivanovich Mal’cev. Algorithm and Recursive Functions. Wolters- Noordhoff, Groningen, NL, 1970.
[11] Cornelis A. Middelburg. On the formalization of the notion of an algorithm. In Ana Cavalcanti and James Baxter, editors, The Practice of Formal Methods: Essays in Honour of Cliff Jones, Part II, volume 14781 of Lecture Notes in Computer Science, pages 23–44. Springer- Verlag, 2024. doi:10.1007/978-3-031-66673-5_2.
[12] Hartley Rogers. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.
[13] Jan van Leeuwen and Jiří Wiedermann. Beyond the Turing limit: Evolving interactive systems. In Leszek Pacholski and Peter Ružička, editors, SOFSEM 2001, volume 2234 of Lecture Notes in Computer Science, pages 90–109. Springer-Verlag, 2001. doi:10.1007/3-540-45627-9_8.
[14] Elaine J. Weyuker. Modifications of the program scheme model. Journal of Computer and System Sciences, 18(3):281–293, 1979. doi:10.1016/0022-0000(79)90036-9.
Bibtex
@article{sacscuza:Middelburg2025fnniia,
title={Formalizing the Notions of Non-Interactive and Interactive Algorithms},
author={C.A. Middelburg},
journal={Scientific Annals of Computer Science},
volume={35},
number={2},
organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
year={2025},
pages={211-249},
publisher={Alexandru Ioan Cuza University Press, Ia\c si},
doi={10.47743/SACS.2025.2.211}
}