Un conjunto de prototipos es aperiódico si se pueden ensamblar copias de los prototipos para crear mosaicos , de modo que todos los patrones de teselación posibles sean no periódicos . La aperiodicidad a la que se hace referencia es una propiedad del conjunto particular de prototiles; los diversos mosaicos resultantes en sí mismos simplemente no son periódicos.
Un determinado conjunto de baldosas, en el plano euclidiano o en algún otro entorno geométrico, admite un mosaico si se pueden unir copias no superpuestas de las baldosas del conjunto para cubrir todo el espacio. Un conjunto dado de mosaicos podría admitir mosaicos periódicos, es decir, mosaicos que permanecen invariantes después de ser desplazados por una traducción (por ejemplo, una red de mosaicos cuadrados es periódica). No es difícil diseñar un conjunto de mosaicos que admita mosaicos no periódicos y periódicos. (Por ejemplo, los mosaicos dispuestos aleatoriamente que utilizan un cuadrado de 2 × 2 y un rectángulo de 2 × 1 generalmente no son 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 de mosaicos aperiódicos son los diversos mosaicos de Penrose . [4] [5] Los conjuntos aperiódicos de prototiles conocidos se ven en la lista de conjuntos aperiódicos de mosaicos . La indecidibilidad subyacente del problema del dominó implica que no existe ningún procedimiento sistemático para decidir si un conjunto determinado de fichas puede formar mosaicos en el plano.
Los polígonos son figuras planas delimitadas por segmentos de 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 sólo tres tipos de polígonos regulares (el cuadrado, el triángulo equilátero y el hexágono) pueden encajar perfectamente entre sí en teselaciones repetidas en un plano euclidiano . Dentro de ese plano, cada triángulo, independientemente de su regularidad, se teselará. Por el contrario, los pentágonos regulares no forman mosaicos. Sin embargo, los pentágonos irregulares, con diferentes lados y ángulos, pueden formar teselas. Hay 15 pentágonos convexos irregulares que recubren el avión. [6]
Los poliedros son los correlatos tridimensionales de los polígonos. Están construidos a partir de caras planas y aristas rectas y tienen curvas cerradas en los vértices . Aunque un 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 solo poliedro que tese el espacio tridimensional euclidiano , de modo que ningún mosaico sea isoédrico (un mosaico anisoédrico ). El problema mencionado fue resuelto por Karl Reinhardt en 1928, pero los conjuntos de mosaicos aperiódicos se han considerado como una extensión natural. [7] La cuestión específica de los conjuntos aperiódicos de mosaicos 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 prototiles admite un mosaico. del avión. Wang encontró algoritmos para enumerar los conjuntos de mosaicos que no pueden colocar mosaicos en el plano y los conjuntos de mosaicos que lo colocan periódicamente; Con esto demostró que tal algoritmo de decisión existe si cada conjunto finito de prototipos que admite un mosaico del plano también admite un mosaico periódico.
Por lo tanto, cuando en 1966 Robert Berger encontró un conjunto aperiódico de prototipos, demostró que el problema de las teselas, de hecho, no es decidible. [8] (Por lo tanto, los procedimientos de Wang no funcionan en todos los conjuntos de fichas, 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, requirió 20.426 fichas de Wang. Más tarde, Berger redujo su conjunto a 104, y Hans Läuchli posteriormente encontró un conjunto aperiódico que requería sólo 40 fichas de Wang. [9] El conjunto de 13 mosaicos que se muestra en la ilustración de la derecha es un conjunto aperiódico publicado por Karel Culik, II, en 1996.
Sin embargo, Raphael M. Robinson descubrió en 1971 un conjunto aperiódico más pequeño, de seis mosaicos que no eran de Wang . [10] Roger Penrose descubrió tres conjuntos más en 1973 y 1974, reduciendo el número de mosaicos necesarios a dos, y Robert Ammann descubrió varios conjuntos nuevos en 1977. La cuestión de si existe un conjunto aperiódico con un solo prototilo se conoce como el problema de Einstein .
Se conocen pocas construcciones de mosaicos aperiódicos, incluso cuarenta años después de la innovadora construcción de Berger. Algunas construcciones son de infinitas familias de conjuntos de mosaicos aperiódicos. [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ó garantiza que debe haber infinitos principios de construcción distintos y que, de hecho, existen conjuntos aperiódicos de fichas para los cuales no puede haber prueba de su aperiodicidad.
Vale la pena señalar que no puede haber un conjunto aperiódico de mosaicos en una dimensión: es un ejercicio simple mostrar que cualquier conjunto de mosaicos en la línea no puede usarse para formar un mosaico completo o puede usarse para formar un mosaico periódico. embaldosado. La aperiodicidad de los prototiles requiere dos o más dimensiones.