Effective Halt-ability - Gödel’s Halting Theorem

During the mid-1990s, while an undergraduate at the University of Nebraska at Omaha, a well-kept secret in the Midwest, a simple high-level language feature that might ameliorate the dilemma of Gödel’s Halting Theorem was struck upon. Its rudiments might have been realized during a first course in programming fundamentals in Pascal at Vanderbilt University circa the Spring of 1989. It was simply this, “the only programmatic structure which would ever produce an infinite iteration found within any code listing is a definite or indefinite repetition. Hence, it seemed reasonable that, if one places a limiting constraint before each instance of these classes of statements found within a program listing, one might guarantee halt-ability; however, one could not ensure the correctness of the program’s final state. When a limit on an iteration was exceeded, a program could gracefully exit and provide an exception report. Such a technique would not guarantee programmatic correctness. Yet, seeing the simplicity of this approach, it might be the case that Gödel’s Halting problem might have been left behind by him as a teaching heuristic, a challenging yet very solvable problem.

A simple, conceptual description of the Halting Problem follows the pattern of its formal mathematically construction; yet, it only uses abstractions.

Also, considering the fact that Gödel and Turing would have been working primarily in the context of machine language, this view of the Halting Problem is understandable. And, in the absence of structured programming or any formal software engineering principles and best practices, these early systems likely were very error prone and commonly entering states of infinite iteration. So, a reasonable first step in ensuring program correctness is guaranteeing halt-ability, the absence of any runaway conditions. Plus, crafting a program which could process any other program listing and detect whether it would eventually terminate or not would be a wise strategy for this first step. Then, the question becomes, “is such possible? Or, is such computable?” Hence, the Theorem of Halt-ability. 

Gödel’s proof is contradictory by construction. Hence, mathematical instinct says that the reasoning is somewhat circular. We start with a contradictory construction and the show that it produces a contradiction. Is such acceptable proof-work? Yet, the assertion of the proof and its claims has stood for decades.

And, if one might somehow show that a program shall eventually halt, the next goal which one must guarantee is that its beginning, intermediate, and final states are all correct. Such might be achievable through the use of formally verifiable programmatic contracts. Such as those developed by Bertrand Meyer.  

Guaranteeing halt-ability in the high-level language layer of a system description would require the use of a global plus numerous local constraints covering all of the iterative structures within the program specification. If none of these upper-bounds on repetition were met, the program would reach its final state and stop. If one of these constraints were violated, the program would raise an exception, print a report on the error stream, and gracefully halt execution. And, a language translation tool, like a compiler or interpreter, which inspected a program listing ensuring that every repetition structure was within the scope of such constraints, would be a counterexample contradicting Gödel’s claim. In other words, it would be the very class of program that he sought.

At the layer of the instruction set architecture, detecting the presence of a processing loop would be necessary. So, an architecture with commands that signal the beginning and ending of a loop are sufficient for its detection. A hardware implementation of such would place a value of high in a field upon entering a loop, a value of medium upon exiting, and a value of low when it is outside of any loop.

While this value is high, a loop counter would be incremented before the first instruction of any iteration. When a loop is exited, the state of any enclosing ones, which includes its counter, would be removed from a register stack maintaining these and made the active loop state. And, if an architecture does not support a loop-begin and loop-end imperatives, they might be simulated by placing values representing these events plus loop state variables within the register file.

It is the case that the “practical” nesting depth of loops has its bounds. It is the said that the goal of efficient programmatic design would use a level of nesting that would produce a quadratic running time or better. So, a hardware implementation that supported a depth of nesting around ten should sufficient. Yet, the placement of the loop frames within the lowest portion of their stack in the main memory file would support a practically unlimited level of nesting. Although, such is impractical from the standpoint of algorithmic efficiency. Seeing that, the development of algorithms with a quadratic time complexity be the goal.

 So, an approximate high-level language solution be this.

#GOEDEL’S HALTING PROBLEM RESOLUTION - EXAMPLE

@[ MAXIMUM-ALLOWABLE-CYCLES := ANY_RESOLVABLE_VALUE ]

WHILE NON-STOP:

                NON-STOP := METHODCALL( PARAMETER_LIST )

So, in modern computing, it might be the case that the question of halt-ability is solve-able. The battle for programmatically enforceable correctness remains. Although, the work of Bertrand Meyer and his programmatic (design) contracts show promise.

It also might be the case that the computing community already holds this insight; yet, it has not been deemed a worthwhile implementation as a hardware circuit or high-level language feature. It is certain that evidence of Gödel’s counterexample exists among current language translation tools. A Python process will gracefully exit and report an exception if a recursive function exceeds an allowable number of self-referential calls. This ensures “halt-ability” for any recursively defined program. Plus, recursion and iteration are processing equivalents, simply different sides of the same algorithmic coin. So, in a sense, Python’s modern hybrid compiler-interpreter is the very type of program that Gödel sought and proved was not computable.

In the case of this problem of halt-ability, it is likely that many students are very-well baffled, befuddled, and brain-bazzizalled by its proof-description, the inherent contradiction built in the proof-work, and the social dynamic involved in questioning a scientific holy-grail put in place by a respected name of Germanic heritage. The Nobel prize-winning physicist at Stanford, Professor William Shockley, helped measure the social weighting of racial cohort labels. His work was based upon what he called “genetic” measures. These were a collection of “carefully chosen” measures. Which he felt accurately and best described the relative strengths of four racial communities. Unfortunately, five primary ones exist on this earth. One of these, those who are descendants of the indigenous inhabitants of the Americas was completely left off the list. Considering the history of the European-led occupation of the Americas, they might simply have been deemed a genocidal afterthought. However, these rankings might shift and adopt an arbitrary ordering depending upon the nature, number, and type of measures chosen for the genetic tuple describing these relative strengths. So, as it oft has been said, “Statistics might lie; and, liars might use statistics.” Yet, Shockley’s work in the social sciences is rarely questioned. This is a function of his social demographic, earnt station in life, and “expert” power.

Most likely, Shockley’s sequential series of populations curves should coincide perfectly with aligned medians. The only difference would be the relative sizes of each normal curve based upon the corresponding population sizes of each group. Yet, that was a brief digression.

Few students in this generation will dare ask an instructor a question for fear of the coming wrath. Which might be dealt out by an insecure professor or peers who are hoping that they keep the average level of performance in the course exceedingly low. This, academic apathy, is the greatest factor limiting the progress made in the modern sciences.

This “insight” has applicability in language design, compiler construction, architecture, or theory. This observation is so incredibly trivial that it does not merit a formal publication. Although, it might potentially invalidate a number of instances of proof-work found in the modern theory of computation as described within Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science 2nd Edition by Martin Davis, Ron Sigal, and Elaine J. Weyuker. As such, a greater range of problem classes might be computable. Hence, a wider spectrum of problems might be solvable.

Homeboy From Heaven [JOD: Psalm 119:73 – 80 (KJV)]

Certainty | A Diversion in Mathematics

 Team. Many among us are searching for an "absolute" truth. In an understanding of this lies certainty. From which, we can distill the reliable consequences of any action. Hence, many find solace in "faith-based" readings. It is their hope that they might further unravel and understand the  dynamic between spiritual actions and reactions. So, they know that certain behaviors elicit a predetermined set of responses. Such knowledge can potentially increase the "spiritual" stability in one's life.

It is this same desire for "predictability" and "stability" in the physical world that makes some pursue the field of mathematics. For seemingly, when one adds a pair of numbers "a" and "b", the result is consistently "c". This obviously apparent and timeless rule can never be violated.

And, it is through the historical investigation of such rules: +, -, *, and /, that a myriad of mathematical disciplines and subdisciplines have been established. This includes algebra, topology, calculus, and the theory of graphs. These subjects and their subfields hold "truths" which the modern mathematician sees as "self-evident" much like those inalienable "freedoms" of life, liberty, and the pursuit of happiness. Yet, are they? And, if not "self-evident", are they identically true.

And, if one might establish that a "fundamental" flaw exists in this "timeless" mathematical reasoning, how will the modern mathematician proceed? Will he persist in his "pollyannic" view of his discipline like a cogitating ostrich. Or, will he accept that centuries of reasoning performed by men which he deifies and holds as unquestionable, such a Descartes, Euler, Fermat, and Gauss, might be horribly flawed and incomplete?

One such observation concerning the sets of established numbers has been made on numerous occasions. And that is this, the set of "irrational" numbers simply is that, "irrational". The notion that another "whole" or "floating-point" number cannot be seen as a ratio of "whole" numbers is incredibly "counter-intuitive". In fact, it grates against "natural" mathematic instincts so much that one must consider such a mathematical proposition as "highly" suspect.

And, before one "raises" his mathematical hackles, consider this simple construction, an infinite "ten" or 100....0.  This one followed by an infinite expansion of zeroes, inf(10), is a "permissible" whole number. Although it has an abbreviated description, its complete expansion could never be rendered.

Now, take any "irrational" number with a "non-terminating" decimal such as pi or e and multiply them by inf(10).

    So, pi * inf(10) is an element of the set of natural numbers. Let us call it, PI. So, pi = PI/inf(10). And, pi is a "rationale" value formed from non-terminating whole numbers. The same is true of "e" or any other scalar which has previously been presented as "irrational". And, hence, any postulate, theorem, or worse yet, fundamental axiom, which has been established in the disciplines of mathematics since the establishment of the delusionary notion that number could actually be "irrational" is potentially flawed.

   So, "certainty" does not exist in mathematics, or for that fact, computation itself, in that it is built upon man's grossly limited, inherently flawed, and highly fallible capacity for reasoning. 

  And, it can be said that, with the introduction of the notion of the "irrational" number in the fifth century by the Greek mathematician Hippasus of Metapontum, mathematics itself has entered the realm of the "irrational". And, it should be said that as of 2021 A.D., it has not left.

irrational [ ih-rash-uh-nl ]

adjective

1. without the faculty of reason; deprived of reason.
2. without or deprived of normal mental clarity or sound judgment.
3. not in accordance with reason; utterly illogical: irrational arguments.
4. not endowed with the faculty of reason: irrational animals.

Mathematics.

1. (of a number) not capable of being expressed exactly as a ratio of two integers.
2. (of a function) not capable of being expressed exactly as a ratio of two polynomials.

Algebra. (of an equation) having an unknown under a radical sign or, alternately, with a fractional exponent.

Greek and Latin Prosody.

1. of or relating to a substitution in the normal metrical pattern, especially a long syllable for a short one.
2. noting a foot or meter containing such a substitution.

noun

Mathematics. irrational number.

Goofy Orientation

Team. Could you please help me find the right and left sides of the screen? Is the LHS and RHS, left-hand side and right-hand side, of a production in a context-free grammar inverted. In other words, what are the left and right sides of:

public static String aSimpleStringLiteral = "More backward than Aksarben."';

Could this be corrected? Or, is it the case that computing genius baffles "common sense".

When you "left-align" a paragraph in Microsoft Word or another online editor, what side of the page and screen does it align with? Are you saying, "Flush? On what side? Is that right-alignment?"

Just a reminder. Always keep this straight and remember that bolts tighten when they are turnt clockwise and loosen when they are turnt counter-clockwise. Common-sense is a nascent gift; but, it can be lost in this backwards world. Right? Or, is that Left?

And, if you think that it does not matter. Try this "natural" orientation for a year. And, see if life looks different.

Please Forgive the Rhetorical Nature of this Passage.

The Author Resolving Confusion. 

Free E-Book | A Synopsis of Programming Fundamentals

Team. Last week the author of this weblog drafted a short book covering some the concepts in computing which he has learnt within the past three decades of learning. He has a couple of post-baccalaureates in science and engineering. One is in computer science; the other is in engineering. And, the text does contain some religious content and references from the perspective of a Protestant Christian. So, if one would not find such offensive reading while seeing another man's perspective on computing, enjoy the reading. It is a "free" (*.pdf) that you can share with your friends.

Remember Hunt, Peck, and Think. It is the "Best" Programming Approach.

Pyhton In CaboosE (ICE) [ Non Zero-C Production ]

 Team. The CABOOSE System found in the text, JAVA in CABOOSE, by Abraham Vati James, has been ported. The companion Rosetta CABOOSE web history is currently working on rendering this simple product in fourteen different languages. Within the past week, an instance of this general-purpose controller (GPC) written in von Rossum's Python was provided. It is called Python ICE. This should not be confused with the product by Zero C. It contains a very simple-minded code-generator for use with its architectural control language (ACL) file containing the CABOOSE Logic.

This also can be found on GitHub.

Notoriously "Bad" English Skills - The Oracle Effect

 Team. An "oracle's" response is considered infallible. We might formulate our next query upon it, but we do not question its validity. Unfortunately, the modern computer and the software tools which it provides are seen a "oracles". We do not doubt a "fact" found on the WWW anymore than we would an output provided by a modern Texas Instrument's calculator given the problem "3+4". Yet, computers can produce "erroneous" output. 

As of this decade, 2020, modern computers have not passed the Turing Test proposed by the computing visionary Alan Turing nearly a century ago. In this test, he felt that, if the responses made by a computer could not be distinguished from those that a human would make, a software program could be deemed "fully" intelligent. And, in this era of International Business Machine's Deep Blue which bested the chess Grand Master Kasparov on numerous occasions, one might feel that a computer's intelligence greatly exceeds that of the average human. This simply is not the case.

There is a "universal law of cognitive limitation" governing modern computers or thinking machines. They cannot reason beyond the capacity of their creators. In essence, their "intelligence" could never exceed the "weakest" link in the chain of humans who programmed them. Nascently, computers are "mindless" automatons. They can perform logical functions at "lightening" speed that dazzles the mind. Yet, although modern processors can perform "billions" of commands per second, they cannot reason beyond their design limitations and can only do what they are told. Unless they are told how, they cannot innovate, learn from experience, or decide what "skills" or "knowledge" that they will acquire next.

And sadly, in this WWW-era, most humans deem computers unquestionable. This is ever so true in the use of modern languages. The author of this weblog is a native "Amurican" English-speaker. Notice that was not spelt American. And, he has found that many of the on-line resources describing the rules of a language he learnt throughout grammar school differ from his what he was taught by his grade school instructors.

Firstly, the orientation is "backward". In Ms. Tschetter's kindergarten class in 1975, the author learnt that English was read from the natural "right" side of the page as the eye scans the page "leftward". This orientation was based upon the top and bottom of the page with it experiencing an anthropomorphization that arises during "natural" communication. Arabic and Hebrew were deemed read from the "left-side".

Secondly, future years in grammar school taught the presence of irregular verbs in the English language. Some were used earlier in this passage.

Thirdly, the word "who" should be "whom" when it is an indirect or direct object in a sentence or follows certain prepositions.

Sadly, as computers grow increasing "brighter", humans become exponentially "duller" it seems. Many modern English speakers cannot understand passages with inverted word order. Which is an acceptable language construction. While, in graduate school at the University of Texas, the fact that most of the student body could not read English became apparent. And, most were Americans.

It seemed that they processed the words of a sentence in sequential order starting on what they called the "left" of the page or console. If the structuring of the sentence was not "super" simple and non-inverted, extremely confused they would become. Many of these students, despite their "poor" command of written language, earnt doctoral degree in computing with honors. Remember our "law of universal cognitive limitations" and our tacit acceptance of a computer's response as an oracle speaking.

Truth be told, in this Grammarly-Spellchecker era, written language lacks many of the idioms and mellifluous transitions and segues in speech that makes it interesting. And, this limited written usage affects the words which we speak. We become highly technical dullards, in light of this.

This phenomenon was first described in the 1980s by a high-school German teacher whom the author has know for many years. She stated that many of her students could not tell time based upon the quarter hour in English, since the relied upon their digital watches. They would read 3:45 P.M. as "three forty-five" and not "a quarter of four". They had forgotten the lessons which they had learnt about telling time on analog clocks in first and second grade. And, seeing that they did not understand and could not grasp this concept in their mother tongue, she had difficulty teaching them German.

And, this morning produced a shocker when the author was searching on Google for information on "intrest" rates which is a valid financial term. Yet, he was told that he should be searching for "interest rates" instead. In actuality, the author was interested in finding information on the intrest paid based upon an annual percentage rate for certain savings accounts.

And, this was not a "Google glitch". Other on-line references, such as www.dictionary.com, did not contain the term intrest, indicating a percentage of a financial principle charged or paid on a recurring periodic basis. And, it is wondered whether this language "snafu" has spread throughout the pages of the Motley Fool and CNBC with their expert on-line financial commentary.

And, seeing that we will forget certain facts over the years, we must refresh our memories, like a processor's cache. And, it has escaped the author whether the choice of an article such as "a or an" should be based upon the first noun that follows it or the word that it immediately proceeds. The rules governing articles and vowels plus the soft "h", such as the one found in "humor" properly pronounced (oomor), are well-remembered. 

Yet, where might might one find a "reliable" on-line grammar reference outline the language rules that he long since forgat.

Is this simply a phenomenon occurring with English, the world's third most widely spoken language, or is it present in others used on-line such a Mandarin Chinese and Spanish which are both more prevalent in world-wide use? And, will this ever cease?

Faithful Viewer

CABOOSE Team. We have a handful of "faithful" viewers who reside on various continents.This one is for you.  One of the projects which was mentioned earlier in this web history, that spans a few years, has been "revived". It is the Code Rosetta Stone project. Its goal is creating small "meaningful" code projects in various popular modern high-level computing languages. It was started in 2016, placed on pause that Fall, and restarted this summer. It comprises less than fifteen total post at this time. The web history currently outlines the developer of a CABOOSE-like controller kernel in fourteen "different" languages. With that said, some of the languages are "related", such as JAVA, Groovy, and Clojure or Node.js and Typescript. Best of all, the author has supplied an archive containing all of the source code implementations.

Hunt. Peck. Think. Happy Coding!