Opened Access Fractal dimension versus process complexity

Citas

buscar en

Estadísticas
Icon
Exportar a
Autor: Joosten, Joost J.
Soler Toscano, Fernando
Zenil, Hector
Departamento: Universidad de Sevilla. Departamento de Filosofía y Lógica y Filosofía de la Ciencia
Fecha: 2016
Publicado en: Advances in Mathematical Physics, 2016, 1-21.
Tipo de documento: Artículo
Resumen: We look at small Turing machines (TMs) that work with just two colors (alphabet symbols) and either two or three states. For any particular such machine t and any particular input x, we consider what we call the space-time diagram which is basically the collection of consecutive tape configurations of the computation t (x). In our setting, it makes sense to define a fractal dimension for a Turing machine as the limiting fractal dimension for the corresponding space-time diagrams. It turns out that there is a very strong relation between the fractal dimension of a Turing machine of the above-specified type and its runtime complexity. In particular, a TM with three states and two colors runs in at most linear time, if and only if its dimension is 2, and its dimension is 1, if and only if it runs in superpolynomial time and it uses polynomial space. If a TM runs in time O (xn), we have empirically verified that the corresponding dimension is (n + 1)/n, a result that we can only partially...
[Ver más]
Cita: Joosten, J.J., Soler Toscano, F. y Zenil, H. (2016). Fractal dimension versus process complexity. Advances in Mathematical Physics, 2016, 1-21.
Tamaño: 3.787Mb
Formato: PDF

URI: http://hdl.handle.net/11441/64222

DOI: 10.1155/2016/5030593

Ver versión del editor

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones