Conjunto aperiódico de prototiles

Un conjunto de prototiles es aperiódico si se pueden ensamblar copias de los prototiles para crear teselados , de modo que todos los patrones de teselado posibles sean no periódicos . La aperiodicidad a la que se hace referencia es una propiedad del conjunto particular de prototiles; los diversos teselados resultantes son simplemente no periódicos.

Un conjunto dado de teselas, en el plano euclidiano o en cualquier otro contexto geométrico, admite un teselado si se pueden colocar copias no superpuestas de las teselas del conjunto para cubrir todo el espacio. Un conjunto dado de teselas podría admitir teselados periódicos, es decir, teselados que permanecen invariables después de ser desplazados por una traslación (por ejemplo, una red de teselas cuadradas es periódica). No es difícil diseñar un conjunto de teselas que admita teselados no periódicos así como periódicos (por ejemplo, los teselados dispuestos aleatoriamente utilizando un cuadrado de 2×2 y un rectángulo de 2×1 son típicamente no periódicos).

Sin embargo, un conjunto aperiódico de mosaicos solo puede producir mosaicos no periódicos. ^{[1] [2]} Se pueden obtener infinitos mosaicos distintos a partir de un único conjunto aperiódico de mosaicos. ^[3]

Los ejemplos más conocidos de un conjunto aperiódico de fichas son las diversas fichas de Penrose . ^{[4] [5]} Los conjuntos aperiódicos conocidos de protofichas se ven en la lista de conjuntos aperiódicos de fichas . La indecidibilidad subyacente del problema del dominó implica que no existe un procedimiento sistemático para decidir si un conjunto dado de fichas puede teselar el plano.

Los polígonos son figuras planas delimitadas por segmentos de línea recta . Los polígonos regulares tienen todos los lados de igual longitud , así como todos los ángulos de igual medida . Ya en el año 325 d. C., Pappus de Alejandría sabía que solo 3 tipos de polígonos regulares (el cuadrado, el triángulo equilátero y el hexágono) pueden encajar perfectamente juntos en teselaciones repetidas en un plano euclidiano . Dentro de ese plano, cada triángulo, independientemente de su regularidad, se tesela. Por el contrario, los pentágonos regulares no se teselan. Sin embargo, los pentágonos irregulares, con diferentes lados y ángulos, sí pueden teselarse. Hay 15 pentágonos convexos irregulares que forman mosaicos en el plano. ^[6]

Los poliedros son los correlatos tridimensionales de los polígonos. Se construyen a partir de caras planas y aristas rectas y tienen curvas pronunciadas en los vértices . Aunque el cubo es el único poliedro regular que admite teselación, muchas formas tridimensionales no regulares pueden teselarse, como el octaedro truncado .

La segunda parte del decimoctavo problema de Hilbert pedía un único poliedro que tesela el 3-espacio euclidiano , de modo que ninguna teselación por él sea isoédrica (una teselación anisoédrica ). El problema tal como se planteó fue resuelto por Karl Reinhardt en 1928, pero los conjuntos de teselaciones aperiódicas se han considerado como una extensión natural. ^[7] La ​​cuestión específica de los conjuntos aperiódicos de teselaciones surgió por primera vez en 1961, cuando el lógico Hao Wang intentó determinar si el Problema del Dominó es decidible, es decir, si existe un algoritmo para decidir si un conjunto finito dado de prototeselaciones admite una teselación del plano. Wang encontró algoritmos para enumerar los conjuntos de teselaciones que no pueden teselar el plano y los conjuntos de teselaciones que lo teselan periódicamente; con esto demostró que tal algoritmo de decisión existe si cada conjunto finito de prototeselaciones que admite una teselación del plano también admite una teselación periódica.

Por lo tanto, cuando en 1966 Robert Berger encontró un conjunto aperiódico de prototiles, demostró que el problema del teselado no es de hecho decidible. ^[8] (Por lo tanto, los procedimientos de Wang no funcionan en todos los conjuntos de losetas, aunque eso no los hace inútiles para fines prácticos). Este primer conjunto de este tipo, utilizado por Berger en su prueba de indecidibilidad, requería 20.426 losetas de Wang. Berger redujo más tarde su conjunto a 104, y Hans Läuchli posteriormente encontró un conjunto aperiódico que requería solo 40 losetas de Wang. ^[9] El conjunto de 13 losetas que se da en la ilustración de la derecha es un conjunto aperiódico publicado por Karel Culik, II, en 1996.

Sin embargo, un conjunto aperiódico más pequeño, de seis fichas no Wang, fue descubierto por Raphael M. Robinson en 1971. ^[10] Roger Penrose descubrió tres conjuntos más en 1973 y 1974, reduciendo el número de fichas necesarias a dos, y Robert Ammann descubrió varios conjuntos nuevos en 1977. La cuestión de si existe un conjunto aperiódico con un solo prototipo se conoce como el problema de Einstein .

Se conocen pocas construcciones de teselación aperiódica, incluso cuarenta años después de la revolucionaria construcción de Berger. Algunas construcciones son de familias infinitas de conjuntos aperiódicos de teselas. ^{[11] [12]} Las construcciones que se han encontrado se construyen en su mayoría de una de varias maneras, principalmente forzando algún tipo de estructura jerárquica no periódica. A pesar de esto, la indecidibilidad del Problema del Dominó asegura que debe haber infinitos principios de construcción distintos y que, de hecho, existen conjuntos aperiódicos de teselas para los cuales no puede haber prueba de su aperiodicidad.

Vale la pena señalar que no puede haber un conjunto aperiódico de teselas en una dimensión: es un ejercicio simple demostrar que cualquier conjunto de teselas en la línea no se puede utilizar para formar una teselación completa, o se puede utilizar para formar una teselación periódica. La aperiodicidad de las prototeselas requiere dos o más dimensiones.