Snippets Hilbert Decision Problem into Simulation

This page is under development. Comments are welcome, but please load any comments in the comments section at the bottom of the page. Please include your wiki MONIKER and date in your comment with the same courtesy that I will give you. Aside from your courtesy, your wiki MONIKER and date as a signature and minimal good faith of any internet post are the rules of this TCL-WIKI. Its very hard to reply reasonably without some background of the correspondent on his WIKI bio page. Thanks, gold 8/31/2026

• • Title: Snippets Hilbert Decision Problem into Simulation
  • SubTitle: “A Tcl Simulation Illustrating Coding Limits of Hilbert's Entscheidungsproblem.”
  • Preface
  • Introduction
• Page Scope on Historic Math Problems
• Historical Mini-Bio of David Hilbert
• Purpose
• Conclusions
• Wiki table. Provisional Classes for Hilbert Decision Problem
• References
  • Screenshots
    • Figure. David Hilbert, 1907
• Testing Extended deck
• Results so far
• Printout from ActiveState Console
• Results so far
• Hidden Comments Section
• Program Change Log

Title: Snippets Hilbert Decision Problem into Simulation

SubTitle: “A Tcl Simulation Illustrating Coding Limits of Hilbert's Entscheidungsproblem.”

Preface

gold Update 9/3/2026. The examples here include code safety limits and need strong guardrails, so the programs remain practical on ordinary computers. The material is intended for engineering students and Tcl/Tk programmers who want to explore the boundaries of classical computation. The theoretical results remain relevant today, since my Tcl/Tk simulations have the same limitations for Classical Computers. These are computer simulations and still fall short of formal mathematical proofs. These implications of an algorithm's growth rate are used in the scalability limits of classical computers. Content is targeted towards engineering students.

Introduction

There was a long trail of thought and research that led from the historic Hilbert Decision Problem to the current Computer Halting Problem. In practical terms, Hilbert’s program and circle of academics pursued the idea that mathematics could be placed on a rigorous formal foundation. Pure mathematics in disciplined methods should be capable of settling well-formed mathematical questions. Later, Turing entered the story with an imaginary machine, not a room full of hardware. His Turing machine showed that some questions are not merely difficult. The subsequent work on the Turing Machine suggests no universal method can answer some questions. However, we must point out the Computer Halting Problem in the Turing Machine is a distinct undecidable problem, and different approaches, in opinion here.

That is why the tiny Tcl simulation program can report HALTS or UNKNOWN, but cannot always replace UNKNOWN with a final answer. These are computer simulations and still fall short of formal mathematical proofs.

Page Scope on Historic Math Problems

This page uses the term Hilbert’s Entscheidungsproblem for the decision problem associated with Hilbert and Ackermann’s 1928 work in mathematical logic. The "Decision Problem" should not be confused with Hilbert’s tenth problem, which asks whether a polynomial equation with integer coefficients has an integer solution. These are separate historical and mathematical problems, although later work showed deep connections among them through computability theory and reductions. The present Tcl/Tk examples address neither problem in its full mathematical form. The examples are bounded simulations of a small toy system for educational purposes. Accordingly, this page does not claim to solve, reproduce, or prove the undecidability of either Hilbert’s Entscheidungsproblem or Hilbert’s tenth problem et al.

Historical Mini-Bio of David Hilbert

David Hilbert was born on 23 January 1862 in Königsberg, Prussia (now Kaliningrad, Russia). Hilbert earned his PhD (Inaugural-Dissertation) in 1885 at the University of Königsberg under Ferdinand von Lindemann. Dr. Hilbert served as Privatdozent from 1886 and then as professor in Königsberg. Dr. Hilbert accepted a full professorship at the University of Göttingen in 1895, where he remained for the rest of his career. In 1900 he presented his famous list of 23 problems at the International Congress of Mathematicians in Paris. Dr. Hilbert and his students shaped much of twentieth-century mathematics. Hilbert passed away on 14 February 1943 in Göttingen, Germany.

The heyday of the Decision Problem research inside Hilbert’s "Göttingen circle" and students was roughly 1921 to 1928. The definitive statement from the Hilbert Program came in 1928. Hilbert & Ackermann published the " Grundzüge der Theoretischen Logik." The standard English translation was "Principles of Theoretical Logic" or more commonly in later references: Principles of Mathematical Logic. The textbook clearly states the Entscheidungsproblem or Decision Problem for first-order logic. Hilbert also emphasized the Decision Problem at the International Congress of Mathematicians in Bologna in 1928. The wider foundational program that motivated it runs from about 1920 into the early 1930s.

Note. By the mid-to-late 1930s, German foundational research in this area had been drastically reduced by the general purge of talent, emigration, and the regime’s outright hostility to "abstract mathematics [...]" Church and Turing independently established undecidability results in 1936, using related but different approaches.

Purpose

Yes/No Version of Hilbert's Entscheidungsproblem (1928) in Colloquial English Paraphase.

"Is there a procedure that, given any statement in a formal system, always finishes in finitely many steps and correctly says YES (provable) or NO (not provable) — never running forever, never guessing?"

Note. From the German, Hilbert and Ackermann's original 1928 wording didn't actually use "one mechanical procedure" as some translations state the Decision Problem. The original H-A book states it as: "Das Entscheidungsproblem ist gelöst, wenn man ein Verfahren kennt, das bei einem vorgelegten logischen Ausdruck durch endlich viele Operationen die Frage beantwortet, ob dieser Ausdruck allgemeingültig ist oder nicht." Roughly: " The problem is solved once you have a Verfahren — a procedure/method — that decides, in finitely many operations, whether a given logical expression is universally valid." That's what "a procedure" means here. A procedure is a process so rote a person could do it without understanding the mathematics. Or a literal machine could do it without understanding anything at all.

I need a fresh look at this problem. I’m trying to use simulation in Tcl/Tk to highlight Hilbert’s ideas. But I guess we solve the problems for which we have tools, and know how to use them. I have found nothing in Wiki code that comes close to this Hilbert Decision problem, as originally stated. Other than breaking the HDP problem into parts and classes? I can solve one problem with one method, but not all problems with one method. Also, there may exist a set of problems, that are not restricted, and solvable by more than one method. I can tell you that it is possible to constrain a problem so hard that no solution is possible. Received twixt from offsite advisor on what Hilbert is effectively doing. The HDP proposal implies an effective analysis for termination exists, when to shut down the method, and get the computed answer.

# HDP broken into Classes

One problem that is not restricted
Often analyzable.

One restricted family of problems:
Sometimes analyzable by one method.

Problems so restricted and constrained so that no Solution is possible.
Not analyzable by any method

All possible problems:
No universal terminating analyzer exists.

Conclusions

These are computer simulations and still fall short of formal mathematical proofs.

Wiki table. Provisional Classes for Hilbert Decision Problem

References

• Discovering Dennis Ritchie’s Lost Dissertation
• Computer History Museum CHM
• Personal draft? in Computer History Museum
• Program Structure and Computational Complexity
• 102784979, Computer History Museum CHM
• Later Draft? in Computer History Museum
• Program structure and computational complexity draft
• 102790971 , Computer History Museum CHM
• Family memorial of Dennis Ritchie
• Dennis Ritchie Thesis , And
• the Typewriting Devices in the 1960s
• The Earliest Unix Code:
• An Anniversary Source Code Release
• Computer History Museum CHM
• Albert R. Meyer and Dennis M. Ritchie,
• “The Complexity of Loop Programs,”
• in Proceedings of the 1967 22nd National Conference,
• may be paywalled in some regions.
• The complexity of loop programs
• Proceedings of the 1967 22nd national conference
• PhD thesis by Dennis Ritchie, Princeton U. Records
• How did Dennis Ritchie produce his PhD thesis?
• Proceedings of the 22nd ACM Symposium on Document Engineering
• David F. Brailsford, Brian W. Kernighan, William A. Ritchie

• Principles of Mathematical Logic,
• Hilbert, David, 1862-1943, Ackermann, W. (Wilhelm), 1896-
• Grundzüge der theoretischen Logik in German
• David Hilbert's lectures on the foundations of mathematics
• and physics, 1891 - 1933 Vol. 3.
• David Hilbert's lectures on the foundations
• of arithmetic and logic 1917 - 1933
• William Ewald ; Wilfried Sieg, ed.
• In collab. with Ulrich Majer and Dirk Schlimm

History of Math Notation

• Explorations and False Trails -
• The Innovative Techniques That Eventually Brought
• About Modern Algebra” - Jens Høyrup
• History of Mathematical Notations” - Florian Cajori
• Robert Recorde - Tudor Polymath, Expositor,
• and Practitioner of Computation” - Jack Williams
• Robert Recorde: The Life and Times of a Tudor Mathematician”
• edited by Gareth Roberts and Fenny Smith
• Universal mathematics and the new algebra:
• Maurolico, van Roomen, Descartes” - Jeffrey Oaks
• The Whetstone of Witte” - Robert Recorde

Note. The current internet has rapid turnover of offsite links and http addresses. Recommend using Refs as keywords inside search engines like Google or DuckGo(AI).

Screenshots

Figure. David Hilbert, 1907

Photo Credit to Wikipedia

Testing Extended deck

Results so far

# Hilbert Decision Problem into Simulation V4
# TCL Club, 9/4/2026
# Written on ActiveState and Windows 11
# Version Tcl/Tk V8.6+
# Code may have dependencies on ActiveState TCL
# Adding guardrails.
# Max characters on line should be 80 ch.
# This does NOT solve or prove Hilbert’s Entscheidungsproblem.
# This does NOT solve or prove Computer Halting Problem.
# This is not a classical TURING MACHINE.
# It only runs a toy register machine simulation
# for a fixed number of steps.
# HALTS  = we found a definite answer inside the limit
# UNKNOWN = the experiment ran out of patience, slang.
# UNKNOWN means bounded experiment found
# no answer within its step limit.
# ERROR = program found ERROR
# Program halts after 20 steps
# whether recognizable solution or not. 
# NO "Universal Terminator" reaches analysis decision.
# Modules of 15 to 25 lines are sweet spots for portability.
# Modules under 15 lines are ok.
# These testcases are computer simulations 
# and still fall short of formal mathematical proofs.

console show

#!/usr/bin/env tclsh

proc op_halt {steps} {
    return "HALTS after $steps step(s)"
}

proc op_set {instr regsVar pcVar} {
    upvar 1 $regsVar regs
    upvar 1 $pcVar pc
    dict set regs [lindex $instr 1] [lindex $instr 2]
    incr pc
    return {}
}

proc op_inc {instr regsVar pcVar} {
    upvar 1 $regsVar regs
    upvar 1 $pcVar pc
    set name [lindex $instr 1]
    set value 0
    if {[dict exists $regs $name]} {
        set value [dict get $regs $name]
    }
    dict set regs $name [expr {$value + 1}]
    incr pc
    return {}
}

proc op_decjnz {instr regsVar pcVar} {
    upvar 1 $regsVar regs
    upvar 1 $pcVar pc
    set name [lindex $instr 1]
    set target [lindex $instr 2]
    set value 0
    if {[dict exists $regs $name]} {
        set value [dict get $regs $name]
    }
    set value [expr {$value - 1}]
    dict set regs $name $value
    if {$value != 0} {
        set pc $target
    } else {
        incr pc
    }
    return {}
}

proc op_jmp {instr pcVar} {
    upvar 1 $pcVar pc
    set pc [lindex $instr 1]
    return {}
}

proc op_predict {instr pcVar} {
    upvar 1 $pcVar pc
    set answer [lindex $instr 1]
    set haltTarget [lindex $instr 2]
    set loopTarget [lindex $instr 3]

    if {$answer eq "halt"} {
        set pc $haltTarget
        return {}
    }
    if {$answer eq "loop"} {
        set pc $loopTarget
        return {}
    }
    return "ERROR: bad prediction '$answer'"
}

proc op_unknown {instr} {
    return "ERROR: unknown instruction '[lindex $instr 0]'"
}

proc run_step {program regsVar pcVar stepsVar} {
    upvar 1 $regsVar regs
    upvar 1 $pcVar pc
    upvar 1 $stepsVar steps

    if {$pc < 0 || $pc >= [llength $program]} {
        return "ERROR: bad program counter"
    }

    set instr [lindex $program $pc]
    incr steps

    switch -- [lindex $instr 0] {
        halt {
            return [op_halt $steps]
        }
        set {
            op_set $instr regs pc
        }
        inc {
            op_inc $instr regs pc
        }
        decjnz {
            op_decjnz $instr regs pc
        }
        jmp {
            op_jmp $instr pc
        }
        predict {
            set result [op_predict $instr pc]
            if {$result ne {}} {
                return $result
            }
        }
        default {
            return [op_unknown $instr]
        }
    }
    return {}
}

proc run_machine {program {maxsteps 20}} {
    set pc 0
    set steps 0
    set regs [dict create]

    while {$steps < $maxsteps} {
        set outcome [run_step $program regs pc steps]
        if {$outcome ne {}} {
            return $outcome
        }
    }

    return "UNKNOWN after $maxsteps step(s)"
}

set suite_a {
    {"1 halts immediately" {{halt}}}
    {"2 infinite loop" {{inc a} {jmp 0}}}
    {"3 counts down from 5" {{set a 5} {decjnz a 1} {halt}}}
    {"4 minimal one-step loop" {{set a 1} {decjnz a 1} {halt}}}
    {"5 halts exactly at budget" {{set a 18} {decjnz a 1} {halt}}}
}

set suite_b {
    {"6 misses budget by one step" {{set a 19} {decjnz a 1} {halt}}}
    {"7 jump to bad address" {{inc a} {jmp 5}}}
    {"8 unknown instruction" {{foo a}}}
    {"9 two sequential loops" {{set a 2} {decjnz a 1} {set b 3} {decjnz b 3} {halt}}}
    {"10 far beyond the budget" {{set a 25} {decjnz a 1} {halt}}}
}

set suite_c {
    {"11 two-register decreasing measure" {
        {set a 5}
        {set b 0}
        {decjnz a 4}
        {halt}
        {inc b}
        {jmp 2}
    }}
    {"12 halts just beyond default budget" {
        {set a 38}
        {decjnz a 1}
        {halt}
    }}
    {"13 long finite trajectory" {
        {set a 60}
        {decjnz a 1}
        {halt}
    }}
    {"14 diagonal sketch: predict halt" {
        {predict halt 3 2}
        {halt}
        {inc a}
        {jmp 2}
    }}
    {"15 diagonal sketch: predict loop" {
        {predict loop 3 2}
        {halt}
        {inc a}
        {jmp 2}
    }}
}



proc report {suite {maxsteps 20}} {
    foreach entry $suite {
        lassign $entry label prog
        set result [run_machine $prog $maxsteps]
        puts [format "Program %-40s %s" $label $result]
    }
}

report $suite_a 20
report $suite_b 20
report $suite_c 20 

Note. This program performs bounded execution testing of a toy register machine. The program can confirm a halt observed within N steps. But the program cannot determine whether a non-halting run will halt after N steps or never halt. This does NOT solve or prove Hilbert’s historic Entscheidungsproblem, ref David Hilbert and others. This does NOT solve or prove the historic Computer Halting Problem, ref Turing and others. The program does not offer mathematical proofs. .

Printout from ActiveState Console

Testcase 1 halts immediately                      HALTS after 1 step(s)
Testcase 2 infinite loop                          UNKNOWN after 20 step(s)
Testcase 3 counts down from 5                     HALTS after 7 step(s)
Testcase 4 minimal one-step loop                  HALTS after 3 step(s)
Testcase 5 halts exactly at budget                HALTS after 20 step(s)
Testcase 6 misses budget by one step              UNKNOWN after 20 step(s)
Testcase 7 jump to bad address                    ERROR: bad program counter
Testcase 8 unknown instruction                    ERROR: unknown instruction 'foo'
Testcase 9 two sequential loops                   HALTS after 8 step(s)
Testcase 10 far beyond the budget                 UNKNOWN after 20 step(s)
Testcase 11 two-register decreasing measure       HALTS after 16 step(s)
Testcase 12 halts just beyond default budget      UNKNOWN after 20 step(s)
Testcase 13 long finite trajectory                UNKNOWN after 20 step(s)
Testcase 14 diagonal sketch: predict halt         UNKNOWN after 20 step(s)
Testcase 15 diagonal sketch: predict loop         UNKNOWN after 20 step(s)

Note. This experimental code studies halting and guardrails. There are deliberate edge cases or rather deliberate edge errors, that we would expect to find in experimental code study of halting concepts. The code halts after 20 steps, whether a "terminating analysis answer" is found or not.

Results so far

Adding guardrails.

Hidden Comments Section

Program Change Log

gold 2/3/2025. Testing, encountered initial difficulty in saving work? Long code blocks with or unmatched wiki markup can sometimes confuse the Tcl Wiki formatting engine, especially if fences are not balanced or a line begins with markup it treats specially.

gold 9/3/2026. Trying to use simulation in Tcl/Tk to highlight Hilbert’s ideas. But I guess we solve what problems that we have tools for, and know how to use.