This project aimed to implement a K-tape Turing Machine, based on the definition I've learned during the course of "Informatica Teorica" (Mainly Theory of Computability and Theory of Complexity) at University of Florence "UniFI", both as a set of C++ libraries as well as a GUI app.
There is no need for any installation, the libraries (for the simulations) are header only and the app is already builded (at least for Windows now)
As I previously said, the project is divided into a GUI app, for creating and editing Turing Machines that can be executed, a simple binary to generate an example of a simulation runner and the set of libraries.
The GUI app uses a combination of ImGui + ImNodes + ImGuiFileDialogs + GLFW + OpenGL3. It can be used to create, save, load and edit Turing Machines.
Since the Turing Machine is implemented with K as a template argument, I couldn't create one runtime with the needed K. So I thought of creating an executable that is used to generate a simple simulation runner based on the given 'K', it searches if the executable "turing_machine_K" exists, if it doesn't, it uses a template simple cpp file to generate that particular binary. Still, the most flexible way to use these libraries is to just include them and use them, with a known K, in the code.
Example
./binary_generator 3
./turing_machine 3 machine.json alphabet.json tape.jsonThe executable takes 3 file paths as command line arguments, that are a Turing Machine, Alphabet and Tape, serialized to a json (this can be done using the helper.h header, these are also generated by the GUI app when we hit Save and the machine is correctly configured.
The 'big' part of this project are the libraries, that can be found under the headerfolder, these include turing_machine, tape, alphabet, definitions, helper and computation:
This class just holds the logic behind a Turing Machine, just number of states, number of symbols, final states and the list of transitions, represented as quadruples, where the shift can be specified as output symbol, L for left movement and R for right movement. Since states and symbols are finite, they are numerable, so we treat each as just an integer.
This class represents a tape that can be used by a Turing Machine during a computation. For the same reason as before, this works with symbols as integers. The correct way to use this class is through read, write, move_left and move_right.
This class is used as a bridge between logical symbols (integers, as before) and readable symbols (characters), just so we can use a more readable approach when definining a computation, rather than just with integers.
Just some definitions that are globally valid for all the libraries, symbols start from 0 so the blank symbol is -1, the blank char or empty cell is *, because we used this during class. Moreover, as left and right are treated as machine symbols, each has its own definitions, so the Turing Machine has the methods sx and dx that return the corresponding shift symbol. If a Machine has n symbols, from 0 to n-1, then R = n and L = n + 1.
A library that can be used to serialize Turing Machines, Alphabets and Tapes to json, as well as deserialize them from json, using nlohmann json library.
This class is what actually is used to execute a Turing Machine on a certain input string. We just create a computation, specifying the same number of tapes as the machine, then we set the Machine to use. We can specify a tape, to have an already initialized tape , or not set one, so it is created blank, and we can specify an alphabet, to read and write from and to the tapes directly using std::strings istead of symbols, as the alphabet is used for that translation. The alphabet is needed if we don't use an already initialized tape, as we wouldn't be able to give input. We can then start, stop, pause, resume the execution, as it is being performed on a separate jthread (this is the only class that requires C++20, all the others should be fine with C++17). There are also flags that specify if the computation ended naturally (terminated), manually (stopped), and if it was accepting (terminated + machine ended on a final state)
Pull requests are welcome. For major changes, please open an issue first to discuss what you would like to change.
MIT License
Copyright (c) 2025 Biribò Francesco
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.