Wangin laatat

Wangin laatoitukset ovat kuvaava esimerkki siitä, miten matemaattinen idea syntyy, muovautuu tutkimuskohteeksi ja lopulta saa ratkaisunsa monien matemaatikkojen vuosien työn tuloksena.

Hao Wang (1921–1995) [1] oli amerikankiinalainen loogikko, filosofi ja matemaatikko, New Yorkin Rockefeller-yliopiston logiikan professori. Hänen mukaansa on nimetty Wangin laatat. Ne ovat neliöitä, joiden reunat on väritetty. Nykyään ne esitetään niin, että laattojen neljäsosat ovat värillisiä (kuva 1). Niistä muodostetaan laatoituksia niin, että vierekkäisten sivujen tulee olla samanvärisiä [2]. Laattaa ei saa kiertää. Wang tutki sekä laatoituksia että tällaisten laattojen joukkojen loogista yhteyttä Turingin koneeseen.

Wang nimitti domino-ongelmaksi tehtävää, jossa on etsittävä ratkaisu sille, onko taso mahdollista laatoittaa annetulla joukolla Wangin laattoja, kun kutakin laattaa on käytettävissä rajattomasti. Tehtävä voidaan yrittää ratkaista esimerkiksi algoritmilla, joka etsii annetuista laatoista rakentuvia suorakulmiokuvioita, joilla taso voitaisiin sitten peittää. Sellainen ratkaisu on luonnollisesti jaksollinen (kuva 2). Algoritmi pysähtyy, kun suorakulmio löytyy, mutta jatkaa muuten toimintaansa. Vuonna 1961 Wang arveli, että hänen laatoistaan ei voisi rakentaa jaksotonta laatoitusta eivätkä hänen algoritminsakaan sellaisia löytäneet. Silloin ei vielä tiedetty, että voidaan muodostaa yksinkertaisia kysymyksiä, jotka eivät ratkea algoritmisesti. Kyse ei ole tietokoneiden laskentakyvystä tai algoritmin laadusta, vaan loogisesta mahdottomuudesta. [2]

Muutamaa vuotta myöhemmin 1964 Wangin oppilas, MIT:n Lincoln-laboratorion tutkija Robert Berger osoitti kuitenkin, että jaksoton laatoitus voidaan muodostaa 20 426 erilaisesta Wangin laatasta, joista ei voida rakentaa jaksollista laatoitusta. Tätä tulosta koskevassa raportissaan [4], joka itse asiassa oli sama kuin hänen väitöskirjansa, hän ei käyttänyt värejä laatoissa. Myöhemmin hän keksi vain 104 laatasta koostuvan ratkaisun. Muutamaa vuotta myöhemmin TeX-ladontajärjestelmän kehittäjä ja Stanfordin yliopiston professori Donald Knuth osoitti, että jaksoton laatoitus voidaan rakentaa 92 Wangin laatasta. Samoihin aikoihin keksittiin myös 52 ja 40 laatan ratkaisut, mutta nämä tulokset julkaistiin vasta myöhemmin.

Vuonna 1996 Turun yliopiston professori Jarkko Kari keksi uuden algebrallisen menetelmän domino-ongelman ratkaisemiseksi ja sen avulla 14 laatan ratkaisun; ja pian tämän jälkeen hänen menetelmällään Karel Kulik 13 laatan ratkaisun [2]. Kilpailu päättyi siihen, että Emmanuel Jeandel ja Michael Rao keksivät 11 laatan (kuva 1) ratkaisun vuonna 2015 ja todistivat, että sitä pienemmästä määrästä Wangin laattoja ei voida rakentaa jaksotonta laatoitusta [5].

Lähteet ja lisää luettavaa

[1] Wikipedia-artikkeli Hao Wang (academic) osoitteessa https://en.wikipedia.org/wiki/Hao_Wang_(academic)

[2] Kari, Jarkko (2021): Laskettavuuden teoria ja tason laatoitukset. Teoksessa Martti Annanmäki ja Ilkka Norros (toim): Urautumattomat. Matemaattis-luonnontieteellisten alojen Akateemiset ry MAL, s. 16–20. Osoitteessa [3] Wikipedia-artikkeli Pavage du plan osoitteessa https://fr.wikipedia.org/wiki/Pavage_du_plan

[4] Berger, Robert (1966): The undecidability of the Domino Problem. Memoirs of the American Mathematical Society, 66, osoitteessa http://www.ams.org/books/memo/0066/memo0066.pdf

[5] Jeandel, Emmanuel ja Rao, Michaël (2015): An aperiodic set of 11 Wang tiles osoitteessa https://hal.inria.fr/hal-01166053v2/file/14tiles.pdf

[6] Shawcross, Graham (2012): Wang Tiles and Aperiodic Tiling osoitteessa https://grahamshawcross.com/2012/10/12/wang-tiles-and-aperiodic-tiling/