An Alternative Representation of Turing Machines by Means of the Iota-Delta Function

Luan Carlos de Sena Monteiro Ozelim
André Luís Brasil Cavalcante
Department of Civil and Environmental Engineering
University of Brasilia
Campus Universitário Darcy Ribeiro, SG12, Asa Norte
Brasilia, Federal District, 70910-900, Brazil
Todd Rowland
Zeta Cubed LLC
Odenton, Maryland 21113, United States
Jan M. Baetens
KERMIT
Department of Data Analysis and Mathematical Modelling
Ghent University
Coupure links 653, B-9000, Ghent, Belgium

Abstract

The evolution of universal systems has been of great interest to computer scientists. In particular, the role of Turing machines in the study of computational universality is widely recognized. Even though the patterns emerging from the evolution of this kind of dynamical system have been studied in much detail, the transition functions themselves have received less attention. In the present paper, the iota-delta function is used to encode the transition function of one-head Turing machines. In order to illustrate the methodology, we describe the transition functions of two universal Turing machines in terms of the latter function. By using the iota-delta function in this setting, Turing machines can be represented as a system of transition functions. This new representation allows us to write the transition functions as a linear combination of evolution variables wrapped by the iota-delta function. Thus, the nonlinear part of the evolution is totally described by the iota-delta function.

Keywords: Turing machines; universality; iota-delta function

Cite this publication as:
L. C. S. M. Ozelim, A. L. B. Cavalcante, T. Rowland and J. M. Baetens, “An Alternative Representation of Turing Machines by Means of the Iota-Delta Function,” Complex Systems, 32(4), 2024 pp. 381–393.
https://doi.org/10.25088/ComplexSystems.32.4.381