Pasar al contenido principal

ECUACIONES EN DERIVADAS PARCIALES: PROBLEMAS DE REACCION-DIFUSION, INTEGRO-DIFERENCIALES, Y DE LA FISICA MATEMATICA

PID2021-123903NB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal para Impulsar la Investigación Científico-Técnica y su Transferencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2021
Plan Estatal 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 1
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Estudio, informe, memoria (Report)

Topological entropy of Turing complete dynamics

  • Bruera Méndez, Renzo|||0000-0003-1184-4586
  • Cardona Aguilar, Robert
  • Miranda Galcerán, Eva|||0000-0001-9518-5279
  • Peralta-Salas, Daniel
We explore the relationship between Turing completeness and topological entropy of dynamical systems. We first prove that a natural class of Turing machines that we call “regular Turing machines” (which includes most of the examples of universal Turing machines) has positive topological entropy. We deduce that any Turing complete dynamics with a continuous encoding that simulates a universal machine in this class is chaotic. This applies to our previous constructions of Turing complete area-preserving diffeomorphisms of the disk and 3D stationary Euler flows. The article concludes with an appendix written by Ville Salo that introduces a method to construct universal Turing machines that are not regular and have zero topological entropy.