Kiyoshi is an undergraduate math major at Loyola Marymount University with a minor in philosophy. He enjoys logic and making flashy animations with Mathematica.
Project: Self Reference in String Substitutions
In string substitution systems, connections to logic are drawn by likening strings to theorems and rules to axioms; however, in traditional forms of logic these two behave the same, as theorems lead to new rules of inference, and rules of inference can be applied to axioms. For a string substitution system to easily emulate traditional logic, a method to translate theorems into axioms must exist. Here I will attempt to see if a method to translate axioms into theorems and back by replacing the arrow with a string is viable.
The fact that an arrow substitution system cannot conserve its rules means that string substitution systems cannot be translated into traditional consistent logical statements simply by replacing certain strings with arrows. The fact that this sort of “exclusively string substitution” method can’t work (while other methods do work) hints that there may be more to the translation methods we use than simply checking if they always halt. It would seem that while one part of the system contains the undecidability, another might contain a necessary complexity which, though decidable, is still non-trivial.
Favorite Four-Color, Four State Turing Machine