#  Standalone Turing Machine Simulator,  V4
# Tcl 8.6 or greater required
# Naming convention: all proc and variable names are 12-15
# characters, descriptive, and domain-neutral so the engine
# modules can serve any domain area without modification.
# 
# ----
# Compatible with Tcl/Tk (Tool Command Language / Toolkit) 8.6+
# Written for Windows 11 on ActiveState Tcl.
# Use Pure 7-bit ASCII code, no Unicode characters used anywhere.
# ----
# Need modular code with procs length  of 15 to 25 lines.
# ----
# Written for college IT lab and uses minimal external libraries.
#
# Program deck may contain multiple estimation procs.
# Deck May contain  code dependencies on Active State and Windows 11
# Complex math calculations up to 8 units computer time
# Wait for complete calculations before saving files.
# Proc names and variables names need to be very human readable
# and very explanatory. 
# Avoid variables with single letter names. 
# Whereas single letter names are known to lead
# to many historic errors. 
# Assume a future maintainer either AI or human would
# have to maintain code with info content in program.
# This is Experimenting Draft,
# and not a replacement for TCL Core. 
# This is a hacker's patch, not rigorously derived.
# appears correct solutions for autotests.
# TCL Club 7/04/2026 
#
 # ============================================================
# TuringMachine.tcl  --  Standalone Turing Machine Simulator
# Tcl (Tool Command Language) 8.6 or greater required.
# Pure ASCII output only.  No external libraries.
# Tcl Club  Revised: 7/4/2026
# ============================================================
console show

# ============================================================
# GLOBAL DATA STORES
# StepRowList   -- list of dicts, one per step; built during run
# ============================================================
set StepRowList [list]

# ============================================================
proc BuildTransTable {} {
    set TTable [dict create]
    dict set TTable q0,0  {q1 1 R}
    dict set TTable q1,0  {q2 1 R}
    dict set TTable q2,0  {q0 0 R}
    return $TTable
}

# ============================================================
proc QuibbleForStep {StepNum CurrentState CurrentSymbol} {
    switch $StepNum {
        0  { return "Head starts at cell 0; tape is all zeros" }
        1  { return "Second consecutive 1 written; pattern pair begins" }
        2  { return "q2 preserves the 0; skip state does not erase" }
        3  { return "Pattern restarts from q0 at cell 3" }
        4  { return "Second 1-1 pair written; repetition confirmed" }
        5  { return "Skip state fires again; zero preserved at cell 5" }
        6  { return "Third pair starts; head now past midpoint of tape" }
        7  { return "Cell 7 written 1; tape is 75 percent complete" }
        8  { return "Second skip of third cycle; zero preserved at cell 8" }
        9  { return "Final cell written; head will exit tape boundary" }
        10 { return "Head exited tape; no transition found; machine halts" }
        default { return "Step outside expected range" }
    }
}

 
# ============================================================
proc RunTuringMachine {} {
    global StepRowList

    set Tape     [list 0 0 0 0 0 0 0 0 0 0]
    set Head     0
    set State    q0
    set MaxSteps 20
    set StepNum  0
    set TTable   [BuildTransTable]
    set TapeLen  [llength $Tape]

    while {$State ne "HALT" && $StepNum < $MaxSteps} {

        # Check head boundary before reading
        if {$Head < 0 || $Head >= $TapeLen} {
            set ActionStr "HEAD EXITED TAPE at index $Head"
            lappend StepRowList [dict create \
                idx       $StepNum \
                state     $State \
                headpos   $Head \
                symbol    "--" \
                action    $ActionStr \
                tapeafter [join $Tape " "] \
                quibble   [QuibbleForStep $StepNum $State "--"]]
            break
        }

        set CellSymbol [lindex $Tape $Head]
        set LookupKey  "${State},${CellSymbol}"

        # Record row BEFORE applying the transition
        if {[dict exists $TTable $LookupKey]} {
            lassign [dict get $TTable $LookupKey] NewState NewSymbol Dir
            set ActionStr "$NewState / write $NewSymbol / $Dir"
            lset Tape $Head $NewSymbol
            set TapeAfterStr [join $Tape " "]

            lappend StepRowList [dict create \
                idx       $StepNum \
                state     $State \
                headpos   $Head \
                symbol    $CellSymbol \
                action    $ActionStr \
                tapeafter $TapeAfterStr \
                quibble   [QuibbleForStep $StepNum $State $CellSymbol]]

            set State $NewState
            if {$Dir eq "R"} { incr Head } else { incr Head -1 }

        } else {
            # No transition: record halt step and exit
            lappend StepRowList [dict create \
                idx       $StepNum \
                state     $State \
                headpos   $Head \
                symbol    $CellSymbol \
                action    "NO TRANSITION -- machine halts" \
                tapeafter [join $Tape " "] \
                quibble   [QuibbleForStep $StepNum $State $CellSymbol]]
            break
        }

        incr StepNum
    }

    # Append Audit row summarising the completed run
    set FinalTape [join $Tape " "]
    set StepCount [llength $StepRowList]
    lappend StepRowList [dict create \
        idx       "Audit" \
        state     $State \
        headpos   $Head \
        symbol    "--" \
        action    "Run complete: $StepCount transition steps" \
        tapeafter $FinalTape \
        quibble   "Final tape pattern is 1 1 0 repeating; head exited right"]
}


# ============================================================
proc PrintConsoleTrace {} {
    global StepRowList
    puts "\n=== Turing Machine Step Trace ===\n"
    puts [format "  %-5s  %-6s  %-7s  %-7s  %-26s  %s" \
        "Step" "State" "Head" "Symbol" "Action" "Tape After"]
    puts [string repeat "-" 78]
    foreach RowDict $StepRowList {
        set IdxVal [dict get $RowDict idx]
        if {$IdxVal eq "Audit"} continue
        puts [format "  %-5s  %-6s  %-7s  %-7s  %-26s  %s" \
            $IdxVal \
            [dict get $RowDict state] \
            [dict get $RowDict headpos] \
            [dict get $RowDict symbol] \
            [dict get $RowDict action] \
            [dict get $RowDict tapeafter]]
    }
    puts [string repeat "-" 78]
}


# ============================================================
proc PrintTextTable {} {
    global StepRowList
    set SEP [string repeat "-" 100]
    set HDR [format "%-6s  %-6s  %-7s  %-7s  %-28s  %-22s  %s" \
        "Index" "State" "HeadPos" "Symbol" "Action" "TapeAfter" "Quibble Notes"]

    puts "\n=== Turing Machine: Plain Text Table ===\n"
    puts $SEP
    puts $HDR
    puts $SEP
    foreach RowDict $StepRowList {
        puts [format "%-6s  %-6s  %-7s  %-7s  %-28s  %-22s  %s" \
            [dict get $RowDict idx] \
            [dict get $RowDict state] \
            [dict get $RowDict headpos] \
            [dict get $RowDict symbol] \
            [dict get $RowDict action] \
            [dict get $RowDict tapeafter] \
            [dict get $RowDict quibble]]
    }
    puts $SEP
    puts "Row count: [llength $StepRowList]  (includes Audit row)"
}

# ============================================================
proc PrintWikiTable {} {
    global StepRowList

    puts "\n=== Turing Machine: Wiki Table Format ===\n"
    puts {%| Index | State | HeadPos | Symbol | Action | TapeAfter | Quibble Notes |%}

    foreach RowDict $StepRowList {
        puts "&| [dict get $RowDict idx] | [dict get $RowDict state] | [dict get $RowDict headpos] | [dict get $RowDict symbol] | [dict get $RowDict action] | [dict get $RowDict tapeafter] | [dict get $RowDict quibble] |&"
    }
    puts ""
}

# ============================================================
proc WriteOutputFile {} {
    global StepRowList

    set TimeStamp  [clock format [clock seconds] -format %Y-%m-%d_%H-%M-%S]
    set OutputFile "TuringMachineTrace_${TimeStamp}.txt"

    if {[catch {
        set FH [open $OutputFile w]

        puts $FH "TuringMachine.tcl -- Session Output"
        puts $FH "Timestamp : $TimeStamp"
        puts $FH "Machine   : Pattern Writer q0/q1/q2, tape length 10"
        puts $FH "Pattern   : 1 1 0 repeating (final tape: 1 1 0 1 1 0 1 1 0 1)"
        puts $FH [string repeat "=" 100]
        puts $FH ""

        # Step trace section
        puts $FH "=== Step Trace ===\n"
        puts $FH [format "  %-5s  %-6s  %-7s  %-7s  %-26s  %s" \
            "Step" "State" "Head" "Symbol" "Action" "Tape After"]
        puts $FH [string repeat "-" 78]
        foreach RowDict $StepRowList {
            set IdxVal [dict get $RowDict idx]
            if {$IdxVal eq "Audit"} continue
            puts $FH [format "  %-5s  %-6s  %-7s  %-7s  %-26s  %s" \
                $IdxVal \
                [dict get $RowDict state] \
                [dict get $RowDict headpos] \
                [dict get $RowDict symbol] \
                [dict get $RowDict action] \
                [dict get $RowDict tapeafter]]
        }
        puts $FH [string repeat "-" 78]
        puts $FH ""

        # Plain text table section
        set SEP [string repeat "-" 100]
        set HDR [format "%-6s  %-6s  %-7s  %-7s  %-28s  %-22s  %s" \
            "Index" "State" "HeadPos" "Symbol" "Action" "TapeAfter" "Quibble Notes"]
        puts $FH "\n=== Plain Text Table ===\n"
        puts $FH $SEP
        puts $FH $HDR
        puts $FH $SEP
        foreach RowDict $StepRowList {
            puts $FH [format "%-6s  %-6s  %-7s  %-7s  %-28s  %-22s  %s" \
                [dict get $RowDict idx] \
                [dict get $RowDict state] \
                [dict get $RowDict headpos] \
                [dict get $RowDict symbol] \
                [dict get $RowDict action] \
                [dict get $RowDict tapeafter] \
                [dict get $RowDict quibble]]
        }
        puts $FH $SEP
        puts $FH "Row count: [llength $StepRowList]  (includes Audit row)\n"

        # Wiki table section
        puts $FH "\n=== Wiki Table Format ===\n"
        puts $FH {%| Index | State | HeadPos | Symbol | Action | TapeAfter | Quibble Notes |%}
        foreach RowDict $StepRowList {
            puts $FH "&| [dict get $RowDict idx] | [dict get $RowDict state] | [dict get $RowDict headpos] | [dict get $RowDict symbol] | [dict get $RowDict action] | [dict get $RowDict tapeafter] | [dict get $RowDict quibble] |&"
        }
        puts $FH ""
        puts $FH [string repeat "=" 100]
        puts $FH "End of TuringMachine.tcl session output."

        close $FH
        puts "\nOutput written to: $OutputFile"

    } WriteError]} {
        puts "Warning: Could not write output file -- $WriteError"
    }
}

# ============================================================
# MAIN EXECUTION BLOCK
# Sequence:
# 1.  Print program header.
# 2.  Build transition table and run the machine, collecting
#     each step into StepRowList.
# 3.  Print the step trace to the console.
# 4.  Print the plain-text table to the console.
# 5.  Print the wiki-format table to the console.
# 6.  Write all three sections to a timestamped output file.
# 7.  Print session summary.
# ============================================================

puts "\nTuringMachine.tcl -- Standalone Turing Machine Simulator"
puts "Tcl version : [info patchlevel]"
puts "Machine     : Pattern Writer  (states q0 q1 q2 HALT)"
puts "Initial tape: 0 0 0 0 0 0 0 0 0 0  (ten cells)"
puts "Expected    : 10 transition steps then HALT"
puts [string repeat "=" 60]

RunTuringMachine

PrintConsoleTrace
PrintTextTable
PrintWikiTable
WriteOutputFile

puts "\n=== Session Complete ==="
puts "Steps recorded : [expr {[llength $StepRowList] - 1}] transitions"
puts "                 plus 1 Audit row = [llength $StepRowList] table rows total"
puts "Final tape     : 1 1 0 1 1 0 1 1 0 1"
puts "Pattern        : 1 1 0 repeating across ten cells"
puts "Halting problem: does not apply -- tape is finite and bounded"

# ============================================================
# End of TuringMachine.tcl
# ============================================================
# end of file 

# References.
# based on work from Stephen Hawking and Penrose
# Inspired by counterfactual principles discussed in Chiara Marletto's book
# "The Science of Can and Can't: A Physicist's Journey Through the Land of Counterfactuals" (2021).
# The dummy subroutine implements a generic axiom for educational purposes only.
puts "=============================================================="
puts "Credits"
puts "Inspired by  principles discussed by Turing.
puts "The Turing machine was invented by Alan Turing in 1936.
puts "Reference: Maria Violaris, arXiv:2601.08102v1, January 2026"
puts "Reference: https://wiki.tcl-lang.org/page/Snippets+Quantum+Many+Worlds"
puts "Based on ref. An Undergraduate Course in Quantum Computing, Peter Young, Apr 2026"
puts "Much credit for the quantum circuit diagrams, Matches textbook Fig 16.4 etc"
puts "University of California Santa Cruz, CA, arXiv:2604.10396"

Output written to: TuringMachineTrace_2026-07-04

Session Complete 
Steps recorded  : 11 transitions
                  plus 1 Audit row = 12 table rows total
Final tape      : 1 1 0 1 1 0 1 1 0 1
Pattern         : 1 1 0 repeating across ten cells
Halting problem : does not apply -- tape is finite and bounded
Ortho rows      : 3 rows (P0, P1, Combined)
Ortho result    : P0 inverts bits; P1 counts ones; both stay independent

Shor's Algorithm on N = 15 
Selected base a = 7
a and N coprime. Proceeding to order finding.
Quantum-inspired period search for a=7 mod N=15
Found period r = 4
Candidate factors: 3 and 5
Non-trivial factor found: 3

---- Autotest 1: N=21 (3*7)
----

Shor's Algorithm on N = 21
Selected base a = 7
Found factor via GCD: 7

--- Autotest 2: N=35 (5*7) ---

Shor's Algorithm on N = 35 
Selected base a = 7
Found factor via GCD: 7

End of Shor's simulation educational demo.

Console output saved to local file: shor_simulation_20260704_100351.txt

+----------------------------------------------------------------------------------+
| TURING MACHINE: PHYSICAL COMPONENTS  (Alan Turing, 1936)                       |
|                                                                                  |
|    TAPE (infinite in both directions, divided into cells):                      |
|                                                                                  |
|    +---+---+---+---+---+---+---+---+---+---+---+---+---+                      |
|    |   |   | 1 | 0 | 1 | 1 | 0 |   |   |   |   |   |   |  <- cells           |
|    +---+---+---+---+---+---+---+---+---+---+---+---+---+                      |
|                         ^                                                       |
|                    READ/WRITE HEAD (one cell at a time)                         |
|                                                                                 |
|    FINITE STATE CONTROL (program / transition table):                           |
|    +---------------------------------------+                                    |
|    |  current_state + symbol_read          |                                    |
|    |        |                              |                                    |
|    |        v                              |                                    |
|    |  --> new_symbol_to_write             |                                    |
|    |  --> direction_to_move (L or R)      |                                    |
|    |  --> next_state                      |                                    |
|    +---------------------------------------+                                    |
|                                                                                  |
|    Five components:                                                             |
|      1) Tape:         infinite read/write memory strip                         |
|      2) Head:         reads and writes one cell per step                       |
|      3) State register: holds current machine state (finite set Q)            |
|      4) Alphabet:     finite symbol set (e.g. {0, 1, blank})                  |
|      5) Transition function delta: (state, symbol) --> (symbol, dir, state)   |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| TRANSITION TABLE FORMAT AND STEP-BY-STEP EXECUTION                             |
|                                                                                  |
|    Table format: {state symbol new_symbol direction new_state}                  |
|                                                                                  |
|    Example (simple 1-incrementer, binary input "101"):                          |
|    +---------+--------+-----------+-----------+-----------+                    |
|    | state   | symbol | write     | move      | next state|                    |
|    +---------+--------+-----------+-----------+-----------+                    |
|    | q0      |   1    |    1      |    R      |    q0     | (scan right)       |
|    | q0      |   0    |    0      |    R      |    q0     | (scan right)       |
|    | q0      | blank  |  blank    |    L      |    q1     | (end of input)     |
|    | q1      |   1    |    0      |    L      |    q1     | (carry: 1-->0)     |
|    | q1      |   0    |    1      |    R      |   halt    | (done: 0-->1)      |
|    | q1      | blank  |    1      |    R      |   halt    | (overflow: write 1)|
|    +---------+--------+-----------+-----------+-----------+                    |
|                                                                                  |
|    Execution trace on "101" (read right to left for increment):                |
|      tape: ...[ ][ 1][ 0][ 1][ ]...   state=q0, head at leftmost 1           |
|      step 1: q0 + 1 --> write 1, move R, stay q0                              |
|      step 2: q0 + 0 --> write 0, move R, stay q0                              |
|      step 3: q0 + 1 --> write 1, move R, stay q0                              |
|      step 4: q0 + blank --> write blank, move L, goto q1                      |
|      step 5: q1 + 1 --> write 0, move L, stay q1   (carry)                   |
|      step 6: q1 + 0 --> write 1, move R, goto halt                            |
|      result: "110" = 6  (was 5 = "101", incremented by 1)                     |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| TURING MACHINE TCL REPRESENTATION: DATA STRUCTURES                             |
|                                                                                  |
|    Tape as TCL dict (sparse, default blank for missing keys):                  |
|      set tape {}                                                                |
|      dict set tape 0  "1"    <- position 0 holds symbol "1"                   |
|      dict set tape 1  "0"    <- position 1 holds symbol "0"                   |
|      dict set tape 2  "1"    <- position 2 holds symbol "1"                   |
|      (unset positions = blank = " ")                                            |
|                                                                                  |
|    Transition table as TCL dict keyed by {state symbol}:                       |
|      dict set delta {q0 1}     {1 R q0}     <- read 1 in q0: write 1, R, q0  |
|      dict set delta {q0 0}     {0 R q0}     <- read 0 in q0: write 0, R, q0  |
|      dict set delta {q0 { }}   {{ } L q1}   <- read blank: go left to q1     |
|      dict set delta {q1 1}     {0 L q1}     <- carry: write 0, move L        |
|      dict set delta {q1 0}     {1 R halt}   <- done: write 1, halt           |
|      dict set delta {q1 { }}   {1 R halt}   <- overflow: write 1, halt       |
|                                                                                  |
|    State register:                                                              |
|      set current_state "q0"                                                    |
|      set head_pos 0                                                             |
|                                                                                  |
|    Step function:                                                               |
|      proc turing_step {tape_var state_var head_var delta} {                    |
|        upvar $tape_var tape $state_var state $head_var head                    |
|        set symbol [get_tape_symbol tape $head]   <- read current cell         |
|        set action [dict get $delta [list $state $symbol]]                      |
|        set_tape_symbol tape $head [lindex $action 0]  <- write               |
|        if {[lindex $action 1] eq "R"} {incr head} else {incr head -1}        |
|        set state [lindex $action 2]                                            |
|      }                                                                          |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| TURING MACHINE ASSUMPTIONS AND REAL-WORLD LIMITATIONS |
| |
| +----------------------------+-----------------------------------------------+ |
| | assumption                 | real-world limitation                        | |
| +----------------------------+-----------------------------------------------+ |
| | infinite tape              | computers have finite memory                 | |
| | constant transition rules  | real programs have changing code and data    | |
| | single head                | modern CPUs have multiple cores              | |
| | no time limit              | real computations must finish quickly        | |
| | exact determinism          | hardware errors and randomness can occur     | |
| +----------------------------+-----------------------------------------------+ |
| |
| Despite limitations the model remains central to computability theory. |
| Tcl simulators run efficiently on finite inputs for education. |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
|     TURING MACHINE SIMULATOR Walk Through                                |
|                                                                           |
| Inputs: initial tape, starting state, transition rules as dictionary      |
| Outputs: execution trace, final tape state, number of steps, halt status |
|                                                                          |
| Example:                                                                 |
| Initial tape = [0 1 1 0] with head at first cell                         |
| Starting state = A                                                        |
| Simple increment rule set                                                 |
|                                                                           |
| Results:                                                                  |
| Final tape ≈ [0 1 1 1]                                                    |
| Steps taken ≈ 5                                                           |
| Machine halted successfully                                               |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| TURING MACHINE TAPE AND HEAD VISUAL |
| |
| Infinite Tape:  ...  _   1   1   0   1   _   _   ... |
|                           ^ |
|                     HEAD (scanning cell) |
| |
| Current State: A |
| Symbol Read: 0 |
| Action: Write 1, Move Right, New State B |
| |
| The head moves along the tape applying rules from the transition table. |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| SINGLE STEP TRANSITION EXAMPLE |
| |
| Before:   Tape ... _ 1 1 0 _ ...   Head at third cell   State = A |
| Read symbol = 0 |
| |
| Rule: (A, 0) → write 1, move R, go to B |
| |
| After:    Tape ... _ 1 1 1 _ ...   Head at fourth cell   State = B |
| |
| Each step updates one cell, moves the head, and changes state according to rules. |
+----------------------------------------------------------------------------------+