Ulam Games, Łukasiewicz Logic, and AF C*-Algebras

Article type: Research Article

Authors: Mundici, Daniele

Affiliations: Department of Computer Science, University of Milan, via Comelico 39-41, 20135 Milan, Italy, E-mail: [email protected]

Abstract: Ulam asked what is the minimum number of yes-no questions necessary to find an unknown number in the search space (1, …, 2n), if up to l of the answers may be erroneous. The solutions to this problem provide optimal adaptive l error correcting codes. Traditional, nonadaptive l error correcting codes correspond to the particular case when all questions are formulated before all answers. We show that answers in Ulam’s game obey the (l+2)-valued logic of Łukasiewicz. Since approximately finite-dimensional (AF) C*-algebras can be interpreted in the infinite-valued sentential calculus, we discuss the relationship between game-theoretic notions and their C*-algebraic counterparts. We describe the correspondence between continuous trace AF C*-algebras, and Ulam games with separable Boolean search space S. whose questions are the clopen subspaces of S. We also show that these games correspond to finite products of countable Post MV algebras, as well as to countable lattice-ordered Specker groups with strong unit.

DOI: 10.3233/FI-1993-182-405

Journal: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 151-161, 1993