Yue Su: Avgörbara och oavgörbara problem-en analys utifrån strategiska spel

Abstract

This paper presents the concepts of decidability and undecidability within the context of computability theory. The main aim is to provide a fundamental understanding of these concepts by analyzing both mathematical problems and strategic games—namely Magic: The Gathering and Dominion. Central focus is placed on the notion of undecidability: the classical Halting Problem, and Turing machines are introduced. Furthermore, the case where Magic: The Gathering has been proven to be Turing-complete and undecidable is presented to deepen the conceptual understanding of undecidability. Finally, the significance of an undecidable game like Magic: The Gathering is discussed, along with how the employed proof technique may inspire further investigation of the undecidability problem in Dominion.