# Basic interactive algorithms: Preview

arXiv: https://arxiv.org/abs/2508.05798 · HTML: https://mlsanity.com/paper/2508.05798/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 24 references that are in the map.
- First posted on arXiv 7 Aug 2025.

## Builds on (most cited first, 3 of 3)

- [Evolving Algebras 1993: Lipari Guide](https://mlsanity.com/paper/1808.06255/) (2018)
- [Unconstrained Church-Turing thesis cannot possibly be true](https://mlsanity.com/paper/1901.04911/) (2019)
- [Software science view on quantum circuit algorithms](https://mlsanity.com/paper/2209.13731/) (2022)

## Abstract (arXiv)

This dialog paper offers a preview and provides a foretaste of an upcoming work on the axiomatization of basic interactive algorithms. The modern notion of algorithm was elucidated in the 1930s--1950s. It was axiomatized a quarter of a century ago as the notion of ``sequential algorithm'' or ``classical algorithm''; we prefer to call it ``basic algorithm" now. The axiomatization was used to show that for every basic algorithm there is a behaviorally equivalent abstract state machine. It was also used to prove the Church-Turing thesis as it has been understood by the logicians. Starting from the 1960s, the notion of algorithm has expanded -- probabilistic algorithms, quantum algorithms, etc. -- prompting introduction of a much more ambitious version of the Church-Turing thesis commonly known as the ``physical thesis.'' We emphasize the difference between the two versions of the Church-Turing thesis and illustrate how nondeterministic and probabilistic algorithms can be viewed as basic algorithms with appropriate oracles. The same view applies to quantum circuit algorithms and many other classes of algorithms.