Abstract
This paper provides a framework enabling to define and determine the complexity of various universal programs U for various machines. The approach consists of first defining the complexity as the average number of instructions to be executed by U, when simulating the execution of one instruction of a program P with input x.
To obtain a complexity that does not depend on P or x, we then introduce the concept of an introspection coefficient expressing the average number of instructions executed by U, for simulating the execution of one of its own instructions. We show how to obtain this coefficient by computing a square matrix whose elements are numbers of executed instructions when running selected parts of U on selected data. The coefficient then becomes the greatest eigenvalue of the matrix.
We illustrate the approach using two examples of particularly efficient universal programs: one for a three-symbol Turing Machine (blank symbol not included) with an introspection coefficient of 3 672.98, the other for an indirect addressing arithmetic machine with an introspection coefficient of 26.27.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Minsky, M.: Computations: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1967)
Rogers, H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967) (also MIT Press, fifth printing, (2002))
Rogozin, Y.: Small universal Turing machines. Theoretical Computer Science 168(2) (November1996)
Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Colmerauer, A. (2005). On the Complexity of Universal Programs. In: Margenstern, M. (eds) Machines, Computations, and Universality. MCU 2004. Lecture Notes in Computer Science, vol 3354. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31834-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-31834-7_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25261-0
Online ISBN: 978-3-540-31834-7
eBook Packages: Computer ScienceComputer Science (R0)