Analyzing the Post Correspondence Problem: Insights into Undecidability and its Connection to Turing Machines

Emma JohnsonFollow

School Name

South Carolina Governor's School for Science and Mathematics

Grade Level

12th Grade

Presentation Topic

Mathematics

Presentation Type

Mentored

Abstract

Undecidability has captivated mathematicians, driving them on a hunt to understand the underlying causes behind problems that are forever beyond explanation. This research delves into undecidability, focusing on the Post correspondence problem as a foundation for exploring the complexities of unsolvability. This research sheds light on the nature of such issues through systematic inquiry and analysis. We started by unraveling the Post correspondence problem, one of the most notable examples of undecidability. As the study progresses, a creative approach is adopted to devise a program capable of solving specific samples of the post-correspondence problem. This strategy involves working backward from the problem's undecidable nature, leading to the emergence of a program capable of addressing select post-correspondence problems. The program's development presents helpful understandings of the underlying structure of these issues, ultimately contributing to a deeper understanding of the broader domain of mathematical undecidability. Various mathematical processes and methods are employed to explore and clarify the boundaries of solvability in the context of undecidability. By uncovering the inner workings of the developed program, this study aims to enlighten why some mathematical issues are inherently unsolvable despite extensive efforts to find solutions, providing an exploration of the profound complexities surrounding undecidability in mathematics. The program, offering solutions to specific instances of the Post correspondence problem, serves as a beacon of insight into the intricacies of unsolvability. This represents a significant stride towards comprehending the challenges within mathematics, ultimately enhancing our grasp of the limits and possibilities inherent in mathematical problem-solving.

Location

RITA 273

Start Date

3-23-2024 11:15 AM

Presentation Format

Oral Only

Group Project

No

COinS
 
Mar 23rd, 11:15 AM

Analyzing the Post Correspondence Problem: Insights into Undecidability and its Connection to Turing Machines

RITA 273

Undecidability has captivated mathematicians, driving them on a hunt to understand the underlying causes behind problems that are forever beyond explanation. This research delves into undecidability, focusing on the Post correspondence problem as a foundation for exploring the complexities of unsolvability. This research sheds light on the nature of such issues through systematic inquiry and analysis. We started by unraveling the Post correspondence problem, one of the most notable examples of undecidability. As the study progresses, a creative approach is adopted to devise a program capable of solving specific samples of the post-correspondence problem. This strategy involves working backward from the problem's undecidable nature, leading to the emergence of a program capable of addressing select post-correspondence problems. The program's development presents helpful understandings of the underlying structure of these issues, ultimately contributing to a deeper understanding of the broader domain of mathematical undecidability. Various mathematical processes and methods are employed to explore and clarify the boundaries of solvability in the context of undecidability. By uncovering the inner workings of the developed program, this study aims to enlighten why some mathematical issues are inherently unsolvable despite extensive efforts to find solutions, providing an exploration of the profound complexities surrounding undecidability in mathematics. The program, offering solutions to specific instances of the Post correspondence problem, serves as a beacon of insight into the intricacies of unsolvability. This represents a significant stride towards comprehending the challenges within mathematics, ultimately enhancing our grasp of the limits and possibilities inherent in mathematical problem-solving.