We need to create a universal Turing machine.
We have a file with the provided information: tape count, starting input, starting position and the rules.
Reading from the file isn't that big of a problem. What I'm doing right now is creating a structure vector and reading all the rules to there.
What I can't figure out is how to make the machine itself work. We know that the starting state is always zero, so I'm starting from there. Looking for the rules that start with this state, but what I cannot figure out is what if I have to jump back to the first rules? What to do then? What can of counting mechanism for the vector can I implement? I'm really new to vectors. I'll add that for the algorithm itself.
No more than two loops can be used, not counting printing out text or reading from the file.
The code I have right now is:
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <Windows.h>
struct rule {
std::string qstate; // dabartine busena
char csymbol; // dabartinis simbolis
char nsymbol; // naujasis simbolis
char direction; // i kuria puse eis galvute
std::string nstate; // naujoji busena
};
void printingText(std::vector<char> input, int position, long long steps);
void searchingForASymbolOrState(std::vector<rule> rules, std::vector<char> input, std::string state, int position, int& cursorPos);
int main()
{
int tapeCount, position;
long long steps = 0;
std::string tape;
std::ifstream file("1.txt");
file >> tapeCount >> tape >> position;
std::vector <char> input(tape.begin(), tape.end());
std::vector <rule> rules;
rule temp;
while (file >> temp.qstate) {
file >> temp.csymbol;
file >> temp.nsymbol;
file >> temp.direction;
file >> temp.nstate;
rules.push_back(temp);
}
file.close();
position--; // kadangi masyvas skaiciuoja nuo nulio, tai ir startine pozicija sumazinu, kadangi ji skaiciuoja nuo vieno
int cursorPos = 0; // saugosim vieta, kurioje vietoje prasideda taisykles su reikiama busena
std::string state = "0"; // saugosim busena, kad zinotume, kokioje busenoje siuo metu esame
// Tiuringo masinos "algoritmas"
while (true) {
printingText(input, position, steps);
if (state == rules[cursorPos].qstate) {
if (input[position] == rules[cursorPos].csymbol) {
if (input[position] != rules[cursorPos].nsymbol) {
input[position] = rules[cursorPos].nsymbol;
if (rules[cursorPos].direction == 'L') {
position--;
steps++;
}
else if (rules[cursorPos].direction == 'R') {
position++;
steps++;
}
if (rules[cursorPos].nstate != state) {
state = rules[cursorPos].nstate;
}
}
else if (input[position] == rules[cursorPos].nsymbol) {
if (rules[cursorPos].direction == 'L') {
position--;
steps++;
}
else if (rules[cursorPos].direction == 'R') {
position++;
steps++;
}
if (rules[cursorPos].nstate != state) {
state = rules[cursorPos].nstate;
}
}
}
else if (input[position] != rules[cursorPos].csymbol) {
searchingForASymbolOrState(rules, input, state, position, cursorPos);
}
}
else if (state != rules[cursorPos].qstate) {
searchingForASymbolOrState(rules, input, state, position, cursorPos);
} // Skaiciuojam zingsnius
// std::cout << cursorPos << " " << position << " " << state << " " << rules[cursorPos].qstate; // Eilute naudojama klaidu paieskai
Sleep(100);
system("cls");
}
// "Algoritmo pabaiga"
}
void printingText(std::vector<char> input, int position, long long steps) {
std::cout << "Head position can be seen with '' symbols\n\n";
for (int i = 0; i < input.size(); i++) {
if (i == position) {
std::cout << "'" << input[i] << "'";
}
else {
std::cout << input[i];
}
}
std::cout << "\n\nSteps: " << steps;
}
void searchingForASymbolOrState(std::vector<rule> rules, std::vector<char> input, std::string state, int position, int& cursorPos) {
for (int i = 0; i < rules.size(); i++) {
if (rules[i].qstate == state) {
if (rules[i].csymbol == input[position]) {
cursorPos = i;
}
}
if (rules[cursorPos].qstate != state) {
if (rules[i].qstate == state) {
cursorPos = i;
}
}
}
}
I know that either .eof()
or system("cls")
aren't good functions to use, but for this project, I think they'll work fine. Correct me if I'm wrong.
EDIT: I tried to do something. Not sure if there's a more effective why. Obviously it's not finished, no halting and error checking and etc. But if you have any comments, they would be really appreciated.