Наблюдения за бытием

#include <deque>
#include <iostream>
#include <optional>
#include <string>
#include <tuple>
#include <unordered_map>

// Types for Turing machine
enum class Symbol { One, Blank };
enum class Direction { Left, Right };
using State           = std::string;
using TransitionKey   = std::tuple<State, Symbol>;
using TransitionValue = std::tuple<State, Symbol, Direction>;
using Transitions     = std::unordered_map<TransitionKey, TransitionValue, std::hash<TransitionKey>>;

struct Tape {
    std::deque<Symbol> data;
    size_t head_pos;
};

// Hash function for TransitionKey
namespace std {
template <>
struct hash<TransitionKey> {
    size_t operator()(const TransitionKey &key) const
    {
        auto [state, sym] = key;
        return hash<string>()(state) ^ (hash<size_t>()(static_cast<size_t>(sym)) << 1);
    }
};
} // namespace std

// Convert symbol to string for printing
std::string symbol_to_string(Symbol sym)
{
    return sym == Symbol::One ? "1" : "_";
}

// Print the current tape and head position
void print_tape(const Tape &tape, const State &state)
{
    std::string left_str, right_str;
    size_t i = 0;
    for (const auto &sym : tape.data) {
        if (i < tape.head_pos) {
            left_str += symbol_to_string(sym);
        } else if (i > tape.head_pos) {
            right_str += symbol_to_string(sym);
        }
        ++i;
    }
    std::cout << "[" << left_str << "] " << symbol_to_string(tape.data[tape.head_pos]) << " ("
              << state << ") " << right_str << "\n";
}

// Move the tape head
void move_head(Tape &tape, Direction dir)
{
    if (dir == Direction::Right) {
        if (tape.head_pos + 1 >= tape.data.size()) {
            tape.data.push_back(Symbol::Blank);
        }
        ++tape.head_pos;
    } else { // Left
        if (tape.head_pos == 0) {
            tape.data.push_front(Symbol::Blank);
        } else {
            --tape.head_pos;
        }
    }
}

// Step the Turing machine
std::optional<State> step(Tape &tape, const State &state, const Transitions &transitions)
{
    TransitionKey current = { state, tape.data[tape.head_pos] };
    auto it               = transitions.find(current);
    if (it == transitions.end()) {
        return std::nullopt; // No transition: halt
    }
    const auto &[new_state, new_symbol, dir] = it->second;
    tape.data[tape.head_pos]                 = new_symbol;
    move_head(tape, dir);
    return new_state;
}

// Run the Turing machine
void run_turing_machine(Tape tape, const State &start_state, const Transitions &transitions,
                        const State &accept_state, const State &reject_state)
{
    State current_state = start_state;
    while (true) {
        print_tape(tape, current_state);
        if (current_state == accept_state) {
            std::cout << "Accepted\n";
            break;
        }
        if (current_state == reject_state) {
            std::cout << "Rejected\n";
            break;
        }
        auto next_state = step(tape, current_state, transitions);
        if (!next_state) {
            std::cout << "Halted (no transition)\n";
            break;
        }
        current_state = *next_state;
    }
}

// Turing machine to add two unary numbers
void example_add()
{
    Transitions transitions = {
        // q0: Move right to find blank
        { { "q0", Symbol::One }, { "q0", Symbol::One, Direction::Right } },
        { { "q0", Symbol::Blank }, { "q1", Symbol::One, Direction::Left } },
        // q1: Move left to start
        { { "q1", Symbol::One }, { "q1", Symbol::One, Direction::Left } },
        { { "q1", Symbol::Blank }, { "qaccept", Symbol::Blank, Direction::Right } }
    };
    // Tape represents 2 + 3: 11_111
    Tape tape = {
        { Symbol::One, Symbol::One, Symbol::Blank, Symbol::One, Symbol::One, Symbol::One }, 0
    };
    run_turing_machine(tape, "q0", transitions, "qaccept", "qreject");
}

int main()
{
    example_add();
}

$ c++ -std=c++17 turing-add.cpp -o turing-add
$ ./turing-add
[] 1 (q0) 1_111
[1] 1 (q0) _111
[11] _ (q0) 111
[1] 1 (q1) 1111
[] 1 (q1) 11111
[] _ (q1) 111111
[_] 1 (qaccept) 11111
Accepted

(* Types for Turing machine *)
type symbol = One | Blank
type direction = Left | Right
type state = string
type transition = (state * symbol) * (state * symbol * direction)
type tape = { left: symbol list; head: symbol; right: symbol list }

(* Convert symbol to string for printing *)
let string_of_symbol = function
    | One -> "1"
    | Blank -> "_"

(* Print the current tape and head position *)
let print_tape tape state =
    let left_str = List.map string_of_symbol tape.left |> String.concat "" in
    let right_str = List.map string_of_symbol tape.right |> String.concat "" in
    Printf.printf "[%s] %s (%s) %s\n" left_str (string_of_symbol tape.head) state right_str

(* Move the tape head *)
let move_head tape dir =
    match dir with
    | Right ->
      let new_right, new_head = match tape.right with
          | [] -> ([], Blank)
          | h :: t -> (t, h)
      in
      { left = tape.head :: tape.left; head = new_head; right = new_right }
    | Left ->
      let new_left, new_head = match tape.left with
          | [] -> ([], Blank)
          | h :: t -> (t, h)
      in
      { left = new_left; head = new_head; right = tape.head :: tape.right }

(* Step the Turing machine *)
let step tape state transitions =
    let current = (state, tape.head) in
    match List.assoc_opt current transitions with
    | None -> None (* No transition: halt *)
    | Some (new_state, new_symbol, dir) ->
      let new_tape = { tape with head = new_symbol } in
      let moved_tape = move_head new_tape dir in
      Some (moved_tape, new_state)

(* Run the Turing machine *)
let run_turing_machine tape start_state transitions accept_state reject_state =
    let rec run tape state =
        print_tape tape state;
        if state = accept_state then Printf.printf "Accepted\n"
        else if state = reject_state then Printf.printf "Rejected\n"
        else match step tape state transitions with
            | None -> Printf.printf "Halted (no transition)\n"
            | Some (new_tape, new_state) -> run new_tape new_state
    in
    run tape start_state

(* Turing machine to add two unary numbers *)
let example_add () =
    let transitions = [
        (* q0: Move right to find blank *)
        (("q0", One), ("q0", One, Right));
        (("q0", Blank), ("q1", One, Left));
        (* q1: Move left to start *)
        (("q1", One), ("q1", One, Left));
        (("q1", Blank), ("qaccept", Blank, Right));
    ] in
    (* Tape represents 2 + 3: 11_111 *)
    let tape = { left = []; head = One; right = [One; Blank; One; One; One] } in
    run_turing_machine tape "q0" transitions "qaccept" "qreject"

(* Run the example *)
let () = example_add ()

$ ocaml turing_add.ml 
[] 1 (q0) 1_111
[1] 1 (q0) _111
[11] _ (q0) 111
[1] 1 (q1) 1111
[] 1 (q1) 11111
[] _ (q1) 111111
[_] 1 (qaccept) 11111
Accepted