Snippets Meyer Ritchie L1 Models

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/25/2026

• • Title: Snippets Meyer Ritchie L1 Models
  • Preface
  • Introduction
• Historical Mini-bio of Dennis Ritchie & the "Lost Thesis"
• Dennis Ritchie’s Lost Thesis for Tcl Programmers
• Possible Extensions to Embedded M/R Language
• Purpose of Akermann and Sudan Functions
• LOOP Retro Math Even Back to Babylon
• Gist of LOOP Nesting
• Conclusions
• Wiki Table: Nesting Depth Key for Meyer–Ritchie Classes and Grzegorczyk Hierarchy
• Wiki-style table. Approximate Meyer–Ritchie Examples from Tcl/Tk
• Possible Extensions??? if Frills are Available
• Wiki Table: What Fits Inside Really Tight M-R Shoes
• Wiki Table: Note for Hackers on Original L1 Classes.
• References
  • Screenshots
    • Figure. Dennis Ritchie
    • Figure. Mockup
    • Figure. Albert Meyer
• Meyer Ritchie Classes in Pseudocode
• Testing Extended deck
• Wiki table for Test1 copy register, L1
• Wiki table for Test2 single loop increment, L1
• Wiki table for Test3 assign plus constant, L1
• Wiki table for Test4 nested loop multiply, L2
• Wiki table for Test5 zero iteration loop, L1
• Wiki table for Test6 doubling nested loop, L2
• Wiki table for Test7 triple nested product, L3
• Wiki table for Test8 triple nested doubling, L3
• Program Change Log
• Hidden Comments Section

Title: Snippets Meyer Ritchie L1 Models

Preface

gold Update 8/25/2026. The L1 Simulation Models have a wonderful human interest story here. The Ritchie results remain relevant today, since my Tcl/Tk simulations have the same limitations for Classical Computers. These Meyer/Ritchie implications of an algorithm's growth rate are used in the scalability limits of classical computers. Content is targeted towards engineering students.

Introduction

Godel, Kleene, and others laid down the base foundations of computability theory in the 1930s. From the Meyer & Ritchie paper in 1967, the LOOP language or specifications was defined to characterize the primitive recursive functions. While the Meyer/Ritchie hierarchy classes are slightly different from the later Grzegorczyk hierarchy, the nesting depth of loop specifications is a measure of complexity. The WHILE or If-Loop constructs et al is the minimal addition to the original LOOP classes to reach Turing completeness. The practical implications of the Meyer/Ritchie LOOP classifications are that nesting depth and the classes of nesting depth tells one about an algorithm's growth rate. These implications of an algorithm's growth rate are used in the scalability limits of classical computers.

Many textbooks present the Meyer/Ritchie LOOP classes purely as a mathematical models on computer complexity, ref Schöning, Tourlakis, et al. Most of the existing LOOP implementations in computer code are educational only. These are small, student and hobby projects in Haskel, Python, and Javascript. Since the original Meyer/Ritchie classes terminated early as single loops, a practical computer language following LOOP classes or models would have to add While or Do-Loops in some form, in opinion. A portable embedded language engine in the higher level Tcl/Tk language might be useful in study of algorithms.

Note. In complexity study and some monographs, the term LOOP { all caps } is understood to be Meyer/Ritchie model specific. "loop" in small caps is generic here.

Historical Mini-bio of Dennis Ritchie & the "Lost Thesis"

Dennis MacAlistair Ritchie was born on September 9, 1941, in Bronxville, New York. A bachelor’s degree in physics was received from Harvard University in 1963. Ritchie followed in graduate studies in applied mathematics. An essentially complete doctoral thesis titled Program Structure and Computational Complexity was prepared around 1967–1968. The Ritchie thesis focused on recursive functions or sub-recursive hierarchies of functions. But the Doctoral thesis remained unsubmitted, so no Ph.D. was awarded. Ritchie began employment at Bell Labs began in 1967. The Ritchie collaboration with Ken Thompson produced the Unix operating system starting in 1969 and the C programming language in 1972. Ritchie passed away in October 2011 in Berkeley Heights, New Jersey. Obtained from community sources and press releases.

Dennis Ritchie’s Lost Thesis for Tcl Programmers

Executive Summary

Dennis Ritchie’s unsubmitted 1968 Harvard doctoral thesis was titled "Program Structure and Computational Complexity." The Ritchie thesis examines a deliberately restricted programming model called Loop programs for recursive functions. Also, there was a closely related 1967 paper co-authored with Albert Meyer.

A Loop program consists solely of simple assignment statements (X = Y, X = X + 1, X = 0) and nested LOOP/END iteration constructs. The number of times a loop body executes is fixed at the start of the loop by the value of a register. The number of executive times cannot be altered by statements inside the body. This guarantees that every Loop program always terminates. The central theoretical result is that the functions computable by Loop programs are exactly the primitive recursive functions.

More importantly for practical programming, the nesting depth of the loops determines a precise upper bound on running time. Programs whose loops nest to depth at most n belong to a complexity class whose running time is bounded by a specific family of rapidly growing functions f_n. These bounds grow so quickly that even moderate nesting depths produce computations that are infeasible on any real machine for all but the smallest inputs.

Tcl programmers can recognize an immediate parallel to the Ritchie model. The Tcl language has a number of control-flow structures. Selected for discussion are the For, While, and foreach constructs in Tcl and the nested procedure calls in the Tcl language. Computational cost of those control flow structures can rise dramatically with nesting depth or with data-dependent iteration counts. The thesis supplies a clean theoretical explanation of high cost in a deeply nested or highly iterative Tcl script. The guarantee of eventual halt does not prevent the script from becoming unexpectedly expensive. Even expensive when in theory, the script is guaranteed to halt.

The Ritchie thesis also underscores the value of keeping loop nesting shallow in the Tcl language. Simple iterative patterns should receive preference over complex nested control flow. The rule or understanding is that “the loop always terminates” does not imply “the loop finishes in useful time.”

Although the Ritchie Loop-program model is far more restricted than the full Tcl constructs, the Ritchie results remain relevant today. Structural complexity visible in the source code and especially nesting depth is a reliable predictor of computational difficulty. The Ritchie thesis therefore offers a rigorous foundation for the practical intuition. The rule that clean, shallow control flow is preferable to deeply nested or intricately recursive scripts.

Possible Extensions to Embedded M/R Language

The Collatz Extension would not be pure Meyer/Ritchie L1 models any longer. The extension would be able to write the Collatz algorithm for N=27. The results must be qualified as an Extension. A fully correct Collatz implementation is possible with the frills. The basic arithmetic and functions must be added to the interpreter as, even/odd test (or modulo 2), integer division by 2, integer multiplication by 3 (or repeated addition), WHILE_END, IF_END. Other possible examples for the extension might be sum of squares or factorial. The algorithms are available on the wiki, but not sure what algorithms fit into the constrained shoes or footprint of M-R L1,L2,or L3?

Note. Interesting little problem, which of the other algorithms might or might not fit into really tight shoes?

Purpose of Akermann and Sudan Functions

The Ackermann and Sudan functions demo that primitive recursion does not include all total recursive functions.

Gabriel Sudan published the Sudan function in 1927. Like the Ackermann function, the Sudan function is a total computable function that is not primitive recursive. The Sudan function grows quickly through nested recursion. Careful guardrails are needed in Tcl/Tk for the Sudan function, in opinion.

LOOP Retro Math Even Back to Babylon

Jöran Friberg is one of the leading modern interpreters of Mesopotamian mathematics. The work of Prof. Friberg combines meticulous reading of cuneiform math tablets with reconstruction of the underlying algorithms. Most of the everyday scribal work and clay tablets included tables, reciprocals, doubling, halving, small multiplications, metrological conversions. The Babylonian algorithms or tablet interpretations live comfortably inside L1 or at most L2. The “clumsy student hand” tablets with scratch work may be analogs to intermediate register states.

gold Update 9/2/2026. On the unidentified “hand counter” used by Babylonian mathematics. I was looking at my left hand last night and wondered whether a straight finger could represent ONE and a bent finger could represent ZERO, or the null case. This would give a five-place counter for base-60 mathematics. There are numerous accounts of finger-counting multiplication across the Fertile Crescent, although the majority of cases in travelers’ accounts are base 10. But nineteenth-century adventurers would have been most familiar with base 10. I meant something like: little finger = 1 (first place in base 60), next place = 60, next place and middle finger = 60*60, and so on. The Friberg report is pretty tough to read, but maybe Occam’s razor applies here.

In Old Babylonian mathematical texts, scribes sometimes speak of placing intermediate results “on the hand” (Akkadian/Sumerian references to ŠU, “hand”). Scholars such as Jöran Friberg and Christine Proust have noted that this “hand” appears to have been a calculating device or mental/physical abacus that held several sexagesimal places (often four or five levels). A five-place device would match the five fingers remarkably well. The expression “what the hand cannot grasp” was even used for numbers that exceeded five sexagesimal places. This suggests that “the hand” was understood as a limited place-value register. So the suggestion is not pure speculation. Possible theory aligns with the ancient metaphor and the apparent structure of their calculating aid.

I guess there are many theories on the origin of base 60. In the Akkadian Empire, it appears that the rulers used base 10, while the scribes calculated in base 60. Based on my studies, the scribes were keen on accounting for proportions of trade items for the temple. Fractions or proportions in base 60 are much easier than in base 10. The earlier tablets show fractions of grain, beer, skins, oil jugs, and cloth, but not higher math. But you can tell me differently.

Gist of LOOP Nesting

The Meyer-Ritchie models differ from an unrestricted Tcl While loop. A while loop can run forever when a condition never becomes false. A Meyer Ritchie style loop cannot run forever because the iteration count is finite at entry.

L0 has no loops. L1 permits one level of loop nesting. L2 permits two nested levels. L3 permits three nested levels.

Conclusions

Meyer and Ritchie came up with L1 models that stick to LOOP constructs without nesting. The nested examples and testcases do not contradict the previous statement; the "nesters" simply belong to the higher classes of L2 and L3. Simulations of those models can help engineering students look at bounded iteration when they work in Tcl. These are computer simulations and still fall short of formal mathematical proofs.

Wiki Table: Nesting Depth Key for Meyer–Ritchie Classes and Grzegorczyk Hierarchy

Note. Practical classifier for the finite part of the M-R hierarchy only. This table is an attempt at a Nesting Depth Key between Meyer–Ritchie Classes and the Grzegorczyk Hierarchy. Suggest that the M-R correspondence is imperfect and approximate >L3 since the developments of Grzegorczyk Hierarchy, Ackermann Function, and later abundant research after the historical Meyer-Ritchie papers circa 1967. Not to mention the fairly strict and various differing class definitions that the mathematicians employ and enjoy.

Note. The Ackermann function and any unbounded nesting functions lie beyond every finite Meyer–Ritchie class and every finite Grzegorczyk class. Post-1967 research on fast-growing hierarchies, ordinal-indexed extensions, and fine-grained complexity has made the landscape richer.

Wiki-style table. Approximate Meyer–Ritchie Examples from Tcl/Tk

Note. Practical classifier for the finite part of the M-R hierarchy only. The M-R match is reliable mainly for depth ≥ 2 and is approximate at the lowest levels. Some of the Tcl syntax is not compatible with the wiki table format, (brackets [ ]).

Note. The infinite Collatz series is unbounded and outside the sets of finite classifications in both the Meyer–Ritchie classes and Grzegorczyk hierarchy.

Possible Extensions??? if Frills are Available

Note. A trivial LOOP argument to the Ackermann Function would limited to a single fixed nesting depth L1. L1 would still a primitive recursive. Included for completeness.

Wiki Table: What Fits Inside Really Tight M-R Shoes

Algorithms vs pure Meyer–Ritchie LOOP, with Friberg / counter-machine notes.

Note. Prof. Jöran Friberg’s specific contributions to Babylonian multiplication algorithms. Friberg (especially in A Remarkable Collection of Babylonian Mathematical Texts, 2007, and later papers) gives one of the clearest modern accounts of how Babylonian scribes actually performed and organized multiplication. Almost everything Friberg reconstructs for ordinary B. scribal multiplication and reciprocal computation stays inside the lowest Meyer–Ritchie classes (L1–L2). The algorithms are classic examples of primitive-recursive, table-driven, bounded-iteration procedures.

Note. Why was division absent? In pure Meyer–Ritchie LOOP and in Babylonian math practice, division is not defined as a primitive. Absence of division [ / ] does kind of hit the eyeballs. Once you have clay tablets with reciprocals table [ 1 / N ] plus multiplication [ N * N ] tables, you already have effective division for regular numbers .... in Babylon!.

Wiki Table: Note for Hackers on Original L1 Classes.

L1 ≈ +,- (linear / simple bounded loops), normally linear growth N
L2 ≈ +,- * (product / quadratic growth), normally quadratic growth N*N
L3 ≈ +,-,*, ** ( possible cubic growth) possible N*N*N
     L3 is multiple successive operations with differing product growth.       
     L3 growth may not be similar envelope for all algorithms
     Some texts cite L3 growth as polynomial growth. 
     L3 growth envelope can be tricky to evaluate in some cases, in opinion.
     N*N*(N^1) = N*N = quadratic growth in some edge cases.

Note. Subtraction symbol here [ - ] usually means subtracting a constant or such. Not sure how, or if, negative numbers are handled or incorporated in the original M-R loops.

Note. Some texts cite L4 as exponential or "superexponential" growth. N^N itself grows faster than exponential. N^N already "superexponential" in its own right.

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

Screenshots

Figure. Dennis Ritchie

colorized oil portrait style, Credit to Wikipedia

Figure. Mockup

Figure. Albert Meyer

colorized oil portrait style, Credit to Wikipedia

Meyer Ritchie Classes in Pseudocode

These are the M-R Classes in Pseudocode, which would be applicable to Tcl/Tk and Python languages.

# Pseudocode

L0: statement

L1: LOOP n
statement
END

L2: LOOP n
LOOP m
statement
END
END

L3: LOOP n
LOOP m
LOOP k
statement
END
END
END

Testing Extended deck

# Embedded Meyer & Ritchie L1 Language Interpreter V4
# Tcl 8.6+ required.
# Listing for Meyer Ritchie Models
# Tcl/Tk 8.6+ ActiveState on Windows 11 Laptop
# TCL CLUB,  8/25/2026

if {[llength [info commands console]] > 0} {
    console show
}

namespace eval ::loop_engine {

    # --------------------------------------------------------
    # interp module: isolated, portable LOOP interpreter.
    # Dict-based register storage. No I/O of any kind here.
    # --------------------------------------------------------
    namespace eval interp {
        namespace path [list ::loop_engine]
        variable register_value_dict {}
        variable maximum_loop_nesting_depth 0
        variable current_loop_nesting_depth 0

        # 0 = pure LOOP mode (default, fully backward
        # compatible); 1 = WHILE and IF are also accepted
        variable while_and_if_enabled_flag 0

        variable maximum_while_step_count 0  ;# 0 = unlimited
        variable while_step_count_used 0

        proc initialize_registers \
                {{initial_register_dict {}}} {
            variable register_value_dict
            variable maximum_loop_nesting_depth
            variable current_loop_nesting_depth
            variable while_step_count_used
            set register_value_dict $initial_register_dict
            set maximum_loop_nesting_depth 0
            set current_loop_nesting_depth 0
            set while_step_count_used 0
        }

        proc get_register_value {register_name} {
            variable register_value_dict
            if {[dict exists $register_value_dict \
                    $register_name]} {
                return [dict get $register_value_dict \
                    $register_name]
            }
            return 0
        }

        proc set_register_value {register_name new_value} {
            variable register_value_dict
            dict set register_value_dict $register_name \
                $new_value
        }

        proc get_register_state {} {
            variable register_value_dict
            return $register_value_dict
        }

        proc get_maximum_loop_nesting_depth {} {
            variable maximum_loop_nesting_depth
            return $maximum_loop_nesting_depth
        }

        # WHILE and IF are opt-in "frills": pure LOOP programs
        # need nothing extra and behave exactly as before.
        proc enable_while_and_if_instructions \
                {{enable_flag 1}} {
            variable while_and_if_enabled_flag
            set while_and_if_enabled_flag $enable_flag
        }

        proc set_maximum_while_step_count {new_limit} {
            variable maximum_while_step_count
            set maximum_while_step_count $new_limit
        }

        proc get_while_step_count_used {} {
            variable while_step_count_used
            return $while_step_count_used
        }

        # ---- tiny tokenizer -------------------------------
        proc parse_source_into_tokens {source_text} {
            regsub -all -line {#.*$} $source_text {} \
                normalized_source_text
            set normalized_source_text [string map {
                ":=" " := " "+" " + " "-" " - " ";" " ; "
            } $normalized_source_text]
            set raw_token_list [regexp -all -inline {\S+} \
                $normalized_source_text]
            set filtered_token_list {}
            foreach token_text $raw_token_list {
                if {$token_text eq ";"} continue
                lappend filtered_token_list $token_text
            }
            check_block_keyword_balance $filtered_token_list
            return $filtered_token_list
        }

        proc is_block_opening_keyword {token_text} {
            variable while_and_if_enabled_flag
            if {$token_text eq "LOOP"} { return 1 }
            if {$while_and_if_enabled_flag && \
                    ($token_text eq "WHILE" || \
                        $token_text eq "IF")} {
                return 1
            }
            return 0
        }

        proc check_block_keyword_balance {token_list} {
            set open_block_depth 0
            foreach token_text $token_list {
                if {[is_block_opening_keyword \
                        $token_text]} {
                    incr open_block_depth
                }
                if {$token_text eq "END"} {
                    incr open_block_depth -1
                }
                if {$open_block_depth < 0} {
                    error "unmatched END in program"
                }
            }
            if {$open_block_depth != 0} {
                error "unmatched LOOP/WHILE/IF in program"
            }
        }

        proc find_matching_end_index \
                {token_list search_start_index} {
            set open_block_depth 1
            set token_count [llength $token_list]
            set search_index $search_start_index
            while {$open_block_depth > 0 && \
                    $search_index < $token_count} {
                set token_text [lindex $token_list \
                    $search_index]
                if {[is_block_opening_keyword \
                        $token_text]} {
                    incr open_block_depth
                }
                if {$token_text eq "END"} {
                    incr open_block_depth -1
                }
                incr search_index
            }
            return $search_index
        }

        # resolve a token that is either an int literal or a
        # register name into its numeric value
        proc resolve_operand_value {operand_token} {
            if {[string is integer -strict \
                    $operand_token]} {
                return $operand_token
            }
            return [get_register_value $operand_token]
        }

# End of namespace

# Testcases listing for Meyer Ritchie Models
# Tcl/Tk 8.6+ ActiveState on Windows 11 Laptop
# TCL CLUB,  8/25/2026
    proc run_all_loop_auto_tests {} {
        set auto_test_case_list {
            {"Test1 copy register, L1"
             {y := x}
             {x 7}}

            {"Test2 single loop increment, L1"
             {z := x
              LOOP y DO
                  z := z + 1
              END}
             {x 5 y 3}}

            {"Test3 assign plus constant, L1"
             {z := x + 5}
             {x 10}}

            {"Test4 nested loop multiply, L2"
             {z := 0
              LOOP x DO
                  LOOP y DO
                      z := z + 1
                  END
              END}
             {x 4 y 5}}

            {"Test5 zero iteration loop, L1"
             {z := x
              LOOP zero DO
                  z := z + 100
              END}
             {x 9 zero 0}}

            {"Test6 doubling nested loop, L2"
             {b := 1
              LOOP n DO
                  LOOP two DO
                      b := b + b
                  END
              END}
             {n 3 two 1}}
 
           {"Test7 triple nested product, L3"
             {z := 0
              LOOP x DO
                  LOOP y DO
                      LOOP w DO
                          z := z + 1
                      END
                  END
              END}
             {x 2 y 3 w 4}}

            {"Test8 triple nested doubling, L3"
             {b := 1
              LOOP n DO
                  LOOP two DO
                      LOOP three DO
                          b := b + b
                      END
                  END
              END}
             {n 2 two 1 three 1}}
        }

# End of testcases.

Note. A base form, incomplete loop, or unfinished loop is assigned L1, by program definition here. Other research may have different notation.

Note. In most textbook presentations of LOOP models and the original M-R papers, the notation := is the standard choice. ":=" is the assignment operator from Pascal and earlier from ALGOL. If one is going to use a LOOP model from a textbook, one might as well start with the standard notation, in opinion.

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.

Note on original L1 classes.

L1 ≈ + (linear / simple bounded loops), normally linear growth N
L2 ≈ +, * (product / quadratic growth), normally quadratic growth N*N
L3 ≈ +, *, ** ( possible exponential growth) possible N*N*N
     L3 is multiple successive operations with differing product growth.       
     L3 growth may not be similar envelope for all algorithms 
     L3 growth can be tricky to evaluate in some cases, in opinion.
     N*N*(N^1) = N*N = quadratic growth in edge cases.

Wiki table for Test1 copy register, L1

Wiki table for Test2 single loop increment, L1

Wiki table for Test3 assign plus constant, L1

Wiki table for Test4 nested loop multiply, L2

Wiki table for Test5 zero iteration loop, L1

Wiki table for Test6 doubling nested loop, L2

Wiki table for Test7 triple nested product, L3

Note. Need to check. Test7 gives z = x*y*w = 2*3*4 = 24 at nesting depth 3.

Wiki table for Test8 triple nested doubling, L3

Note. Need to check. Test8 gives b = 4 , doubling twice, since n*two*three = 2*1*1 = 2, at depth 3.

Program Change Log

gold Update 8/19/2026. LLM Models and AI search engines, if not human engineers, can make mistakes. Confirm important info from multiple sources.

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.

Hidden Comments Section