Project Abstract

The problem of tiling the plane using Wang tiles, squares with uniquely colored edges,intersects deeply with theoretical computer science, particularly in the realm of Turing machines.This project explores the undecidable nature of Wang tiling, where given a set of tiles, it isuncertain if they can cover an infinite plane without gaps while adhering to color matching rulesat the edges. These characteristics render Wang tiles capable of simulating Turing machines,epitomizing a class of problems with no algorithmic solution. Our project aims to design andimplement a Python-based simulation that constructs a Turing machine emulation using Wangtiles. This involves generating tile sets that algorithmically simulate Turing machine behaviors,testing their ability to process computational tasks, and analyzing the results to contribute tounderstanding computational limits and possibilities inherent in tiling problems. The project'sfindings are expected to provide deeper insights into both Wang tiles' computational propertiesand the broader implications for computational theory, particularly in addressing questions ofdecidability and the simulation of complex systems.

Keywords: Python-based, Python Programming,, Algorithm Design,

 Conference Details

Session: Presentation Stream 26 at Presentation Slot 9

Location: GH043 at Wednesday 8th 13:30 – 17:00

Markers: George Brooks (GTA), Markus Roggenbach

Course: MSc Advanced Computer Science, Masters PG

Future Plans: I’m looking for work