/* * This code simulates a single-tape Turing machine * calculating the characteristic function of * the set containing natural numbers up to 2^8-1 * using a unary alphabet. * * Additional info below the code. * * Input: 1 positive integer (choose a small number) * Output: 1 if input is even, 0 if input is odd */ #include #include #include #include // Initialize the relevant excerpt of the infinite tape std::vector init(unsigned int input) { std::vector tape = { 'b', 'b' }; while (input + 1) { tape.push_back('0'); --input; } tape.push_back('b'); tape.push_back('b'); return tape; } // Defining the states void move(std::array::iterator &state, std::vector::iterator &tape) { switch (*state) { // start = q0 case 0: ++tape; ++state; break; // odd case 1: if (*tape == '0') { *tape = 'b'; ++tape; ++state; } else if (*tape == 'b') { *tape = '0'; --tape; state += 3; } break; // even case 2: if (*tape == '0') { *tape = 'b'; --state; ++tape; } else if (*tape == 'b') { *tape = '0'; --tape; ++state; } break; // end case 3: *tape = '0'; --tape; ++state; break; } } // Print the current machine void print(std::vector &tape, std::vector::iterator ¤t_symbol) { for (char c : tape) { std::cout << c << ' '; } std::cout << std::endl; for (auto it = tape.begin(); it != current_symbol; ++it) { std::cout << " "; } std::cout << "^\n\n"; } // Getting the output uint8_t count(std::vector::iterator tape) { uint8_t count = 0; do { ++tape; if (*tape == '0') { ++count; } } while (*tape != 'b'); return count; } int main() { // Defining the machine char sigma = '0'; // input alphabet char gamma[2] = { 'b', '0' }; // tape alphabet, b = blank char tau = '0'; // output alphabet std::array Q = { 0, 1, 2, 3, 4 }; // states: start = q0, odd, even, end, stop std::vector tape; // Initializing the tape unsigned int input = 0; std::cin >> input; tape = init(input); // Iterators where necessary std::array::iterator current_state = Q.begin(); std::vector::iterator current_symbol = tape.begin()+1; // Print the initial data print(tape, current_symbol); // Calculation while (*current_state != 4) { // Move the pointer move(current_state, current_symbol); // Print the current data print(tape, current_symbol); } // Print the result std::cout << "f(" << input << ") = " << count(current_symbol) - 1; return 0; } /* * The first 3 variables aren't actually used, they're * only part of the TM's specification and furthermore a * remnant of a complexer code I initially wanted to write. * * Replacing read 0s with blanks is not necessary, * but I liked to do it for better visualization. * * Fun fact: * -1 is a valid input, although it causes an overflow. * It simulates a Turing machine that doesn't get any input * while pseudo-calculating a very high number, but for both * the empty input and the calculation the result is correct. * (It's not a bug, it's a feature!) */

Turing Machine