kao konobe ili staje. Ulice u središnjem dijelu grada bile su popločane na nož. Danas su jedini ostaci takvog načina popločavanja još vidljivi kod župne crkve i Čorićevog turnja.

matematičar Hao Wang je pločice, kasnije nazvane po njemu, prvi put počeo promatrati u kontekstu pitanja odlučivosti popločavanja ravnine. Pitao se postoji li algoritam koji u konačno mnogo koraka za dani skup pločica određuje je li moguće njima

ravninu. Pokazalo se da odgovor na to pitanje ovisi o tome postoje li aperiodični skupovi pločica. popločavanja ravnine i više o različitim pravilnim popločavanjima možete pročitati u prethodnom broju Math.e, u članku [ KR ].

, ako postoje dva nekolinearna vektora takva da translacije za te vektore prevode popločavanje u njega samog. Sva popločavanja u članku [ KR ] bila su periodična.

. Svaki sljedeći red tako kodira izgled trake Turingovog stroja nakon sljedećeg koraka. Na kraju, u zadnjem redu tog popločavanja dobivamo izgled trake Turingovog stroja s izlaznim podacima. Ako se baš želi popločati cijela ravnina, može se u skup

Turingovih strojeva Wangovim pločicama ima još jednu posljedicu. Pokazuje se da je zbog nje pitanje odlučivosti popločavanja ravnine (" Postoji li algoritam koji za dani skup pločica određuje je li moguće njima popločati ravninu? ")

algoritam koji za svaki stroj određuje hoće li ikada doći u završno stanje. popločavanja ravnine Wangovim pločicama jest i postojanje aperiodičnog skupa Wangovih pločica. Možemo li ga konstruirati?

reda sa slike. To je zapravo popločavanje koje u prvom kvadrantu računa sve višekratnike od a: popločavanja donje poluravnine sljedeći:

četvrtog kvadranta. Ako treba, možete pretpostaviti da su a i b različiti brojevi veći od 1. popločavanja

kvadrate). Isto tako, ako možemo popločati neki kvadrat, možemo popločati i sve kvadrate manje od njega. Popločavanja kvadrata iz iskaza teorema organizirat ćemo u stablo s korijenom. To je poseban slučaj grafa. Svaki graf sastoji se od

svaki vrh na trećem nivou jedno 5 5 popločavanje i tako dalje. Općenito, vrhovi na n - tom nivou predstavljaju sva moguća popločavanja (2 n-1) (2 n-1) kvadrata. Uočite da nijedan nivo nije prazan (jer za svaku veličinu kvadrata postoji popločavanje) i da

) - vom nivou, koji predstavlja popločavanje kvadrata stranice 2 n 1, ako se popločavanje većeg kvadrata može dobiti iz popločavanja manjeg tako da se manji okruži po jednim redom pločica sa svake strane (poštujući, naravno, pravila slaganja Wangovih

pločica. Hipoteza se pokazala krivom - algoritam kakav je Wang pokušao konstruirati 1961. ne postoji, a problem popločavanja ravnine je neodlučiv

Tada postoji prirodan broj n takav da se u svakom popločavanju ravnine tim skupom pločica i u svakom n n bloku pločica tog popločavanja nalaze sve pločice skupa S.

došla su tek s novim idejama, kad su Robinson i Penrose modificirali neka druga u međuvremenu otkrivena aperiodična popločavanja ravnine da bi od njih dobili Wangove pločice (Penroseovo popločavanje dvjema pločicama u obliku romba s obilježenim