Links

ΜΆ
Adam I. Gerard
ISU
NIU
CS MS TBD

The Liar Paradox in Programming

This originally appeared as a side discussion here.

The Liar Paradox and Programming

Programming languages, by design, are much more flexible than most mathematical languages (formal languages, in general). Programming languages have Try, Catch, and Error handling clauses (and keywords). So, logical paradoxes when implemented (albeit loosely implemented since the implementation of the Liar Sentence occurs at the level of a non-core language expression in programming - e.g. in logic, the Liar Paradox is a feature of the logic itself not a user's construction after the fact) will typically just recurse indefinitely (throwing an infinite recursion error and getting caught in an available Try-Catch clause).

Consider this programming discussion thread on Reddit.

// Implementation from Reddit Thread
bool ThisStatementIs(bool x) {
    return ThisStatementIs(!x);
}

The participants to that thread discuss how it's an imprecise but fairly close implementation that results in infinite recursion. I haven't thought too much about the programming language aspects of the Liar Paradox and it's fun to consider some of these intersections.

The above has to do with the following properties:

  1. Propositional Depth a quick sketch of Englebretsen who argues that any acceptable sentence must have a determinate, finite, propositional depth: One sentence can convey multiple propositions (by being the conjunction of multiple other independent sentences: "It is raining today.", "I am happy.", "It is raining today and I am happy." or referring to other sentences "Everything that person said is a lie." each of which conveys a proposition).

i. Crassly, a sentence has finite sentential depth when we can reduce the contents of a top-level sentence into all of its atomic sentences in a finite sequence of steps. Each proposition-bearing sentence then ultimately conveys a finite number of propositions - finite and determinate propositional depth thereby. Sentences whose propositional depth is both n and n+1 have indeterminate propositional depth. Self-recursive expressions have this (as do several others that aren't). This property of sentences aligns with the intuition that expressions in computer science and programming should not have infinite recursion (although there are some subtle differences between the two concepts).

ii. I think the propositional depth solution captures a real and interesting linguistic property but dispenses with many sentences that are completely valid expressions (valid even at compile time in almost all programming languages). Any self-reflexive sentence of any kind has an indeterminate propositional depth and would be ruled out according to Englebretsen. This threatens to rid programming languages of concepts like idempotence, reflection, some metaprogramming, and so on. Statements made at a certain level of abstraction range over infinitely-many expressions - do these then too lack meaning? As a result, despite finding the characterization of propositional depth to be intriguing, I disagree with the overall proposal (as a solution for the Liar Paradox).

There's the additional point that every sentence that happens to have indeterminate propositional depth as a result of containing a Truth Predicate is captured by my proposal. Note that Englebretsen doesn't specify the exact way such sentences would be ruled out. Arguably the way they'd be ruled out is to just restrict the T-Schema.

  1. Infinite Recursion in computer science is a problem for at least two reasons:

(a) the practical outcome of an interpreter or virtual machine iterating indefinitely in an unbreakable loop locks a thread (very bad in synchronous programming and still bad in asynchronous or concurrent programming since the thread would not release) and

(b) infinite recursion often represents mathematical properties like the above that while not always mathematically ruled out (like self-reflexive expressions), are often problematic for other reasons (like bad programming). Infinite recursion is usually sandwiched in Try-Catch clauses that ultimately throw an Error or Exception terminating the thread or process (depending).

  1. Run Time and Compile Time - programming languages separate write time, compile time, and run time. Logical inconsistencies can be introduced at write time and are then caught at compile time (along with syntax or grammar violations). Other inconsistencies (even ones involving Booleans) can appear at run time (depending on one's programming language). Mathematical logic has no such distinction between semantics and syntax - they "occur simultaneously" (so to speak) and completely align in systems that are both sound (everything provable is true) and complete (everything true is provable). (Proof is usually taken to be syntactic and when a proof system is both sound and complete anything proven is also true within that system.)
  2. Programming and Programming Languages allow for inconsistencies to a degree that mathematical languages (programming is in some sense mathematical - I mean the difference between say ZFC Set Theory and say Java) do not. For example, return Types might be incompatible, some value that's supposed to be something isn't, or some asynchronous call doesn't return (in time or just at all) causing data to be missing.
  3. Booleans while the Boolean Type exists in most programming languages, we observe that the Liar Paradox emerges only in languages with Predication (first or higher order, not zero). In other words, the Liar Paradox cannot be formulated using Boolean objects alone.
  4. Undecidability - more precisely, the Liar Paradox (and other Semantic Paradoxes) are formally undecidable since the Liar Paradox lacks stable fixed points (it oscillates between truth-values). As such, no determinate answer terminates the recursion chain (resulting in the infinite recursion). It's pretty cool to see this happen empirically and in real time (programmatically)!

Contents