A well-known brainteaser asks about the truth of the statement "this statement is false". My previous article on this topic, outlined common approaches to this problem and then argued that we should conceive of two distinct kinds of truth:

- Statements about the world, where as per Tarski there is a natural interpretation: "Snow is white" is true iff and only iff "Snow is white"
- Logical/Mathematical statements, where the notion truth is constructed to give us a convenient way of talking about our rules of inference within a particular system that normally excludes self-referential statements

I should add that some statements can only be defined using a combined notion of truth, ie. "The car is red and 1+1=2".

My point was that if we chose to extent logical/mathematical statements outside of their usual bounds, we shouldn't be surprised that it breaks down and that if we choose to patch it, there will be multiple possible ways of achieving this.

## Patching with INFINITE-LOOP

So let's consider how we might attempt to patch it. Suppose we follow the Formalists (ht CousinIt) and insist that "true" or "false" or only applied to sentences that can be evaluated by running a finite computation process. Let's add a third possible "truth" value: INFINITE-LOOP.

Consider the following sentence:

`The truth value of this sentence is not INFINITE-LOOP`

This seems to be a contradiction because the sentence is infinitely recursive, but at the same time denies this.

In order to understand what is happening, we need to make our algorithm for assigning truth values more explicit:

`if expansion terminates:`

Resolve truth value by expanding expressions with references to other expressions

else:

Assign INFINITE-LOOP if expansion fails to terminate

What we see here is that if the sentence is not able to be expanded without ending up in an infinite loop, it is assigned the truth value INFINITE-LOOP without any regard to what the sentence asserts. So there isn't actually an inconsistency, at most, this system for assigning truth values just isn't behaving how we'd want.

In fact consider the following:

`A: This sentence is false`

B: Sentence A has a truth value of INFINITE-LOOP

According to the above algorithm, assigning INFINITE-LOOP to B is correct, when it seems like it should be FALSE. Further, this system assigns INFINITE-LOOP to:

`1+1=2 or this sentence is false`

when perhaps it'd be better to assign it a value of TRUE.

## Patching with an oracle

Being able to talk about whether or not sentences end up in an infinite loop seems useful. So we can imagine that we have a proof oracle that can determine whether sentence will end up in a loop or not.

`for reference in sentence:`

if oracle returns INFINITE-LOOP:

Evaluate the clause given the value INFINITE-LOOP as the truth value of the reference

else:

Expand normally

However, our oracle still doesn't demystify:

`The truth value of this sentence is not INFINITE-LOOP`

As our algorithm would replace the first clause with INFINITE-LOOP and hence evaluate

`INFINITE-LOOP is not INFINITE-LOOP`

to FALSE. But then:

`FALSE is not INFINITE-LOOP`

so we would expect it to also be TRUE.

So perhaps we should define our oracle to only work with sentences that don't contain references to INFINITE-LOOPS. Consider the following situation:

`A: This sentence is false`

B: Sentence A has a truth-value of INFINITE-LOOP

C: Sentence B is true

D: Sentence C is true

B would be TRUE (even though it refers to INFINITE-LOOP, the oracle only has to work with the reference "Sentence A"). However, C would be undefined.

We could fix this by allowing the oracle to return TERMINATES for sentences that can be evaluated after one level of expansion with our initial definition of an oracle. We can then allow sentence D to be true by allowing the oracle to return TERMINATES for any sentence that can be evaluated after two levels of expansion and we can recursively extend this definition until infinity.

This also resolves cases like:

`1+1=2 or this sentence is false`

The second clause evaluates to INFINITE-LOOP and since this is a truth value, rather than actually infinitely looping, (TRUE OR INFINITE-LOOP) should give true.

## Patching with ORACLE-LOOP

We still haven't figured out how to handle cases like:

`The truth value of this sentence is not INFINITE-LOOP`

I would suggest that we might want to repeat our first move and say that the truth value is ORACLE-LOOP whenever an oracle fails to resolve it (even if we expand it an infinite number of times, we still end up with a sentence containing INFINITE-LOOP). We can then stack meta-levels and further metalevels on top of this.

## Fixed points

We could also define another notion of truth whether a statement is true when there is a single fixed point. This would result in statements like:

`This sentence is true`

Being set to true instead of INFINITE-LOOP.

In any case, the way that we extend the concept of truth to apply to these degenerate cases is purely up to what we find convenient.

## Final Note

I actually think there's a similarity here to the Least Interesting Number Paradox. This paradox seems paradoxical only when we fail to define interesting precisely. Once we start to do that, we realise that Interesting Meta-Level 0 and Interesting Meta-Level 1 are different. Similarly, there are different levels of truth depending on how far we go in trying to resolve a question.

Consider patching by tabooing "truth". Declarative sentences don't actually have truth value, except in the sense where "truth" is a handwave toward conveying information which allows an update of the receiver's beliefs. The improvement of predictions enabled by this update is sometimes referred to as "truth".

Don't get me wrong - it's a very useful shorthand, and in many many cases you don't need to expand it. But in the adversarial case where statements are picked to break the normal use of "truth", the right response is to abandon the simple concept for those cases.

I really like the idea that an evaluation algorithm of a proposition can either terminate or end up in a fixed point, mapping back to the evaluation algorithm itself. It unites mathematical and non-mathematical statements instead of separating them, and it allows for algorithm-dependent outcomes of propositions, which fits well into my anti-realist ontology. In this approach a lack of convergence would be an indication that a new, potentially higher-level evaluation algorithm (I call those "models") is required.

Going by what you have presented, some basic hierarchy could be something like this:

Evaluating algorithm-1: Immediately/obviously/postulated true or false, no extra evaluation needed

Evaluating algorithm-2: Evaluated to true or false with or the evaluating algorithm-2 (your "infinite loop")

Evaluating algorithm-3: Evaluated to one of the 2 above or to itself, if the "evaluation field" is not closed.

Etc.

I can't figure out how to indent my code

Open a code-block by typing ``` (triple tick), then press enter.

Didn't work, just showed the triple ticks

Weird, here is a gif of how it's supposed to work:

http://www.giphy.com/gifs/IgigWli9bG8OmtpFPv

Are you using the markdown or the draft-js editor? If it's the markdown editor, then surrounding things with those ticks should make everything in between them code.

Probably wrong editor

Hmm, it looks like it was written in the draft-js editor. In any case, I fixed it for you.

Try editing the post on GreaterWrong. There’s a “code block” button in the editor—select your code and click it, it’ll generate the right Markdown to make it a code block.

compare https://en.m.wikipedia.org/wiki/Turing_jump

Definitely quite relevant

There are a couple of books I know of that deal with paradoxes of circularity. I've read the first one (a long time ago, so don't ask me about the details) but not the second.

"The Liar: An Essay on Truth and Circularity" by Barwise and Etchemendy, which is all about the liar paradox, its elaborations, and attempts to resolve them.

"Vicious Circles: On the Mathematics of Non-Wellfounded Phenomena" by Barwise and Moss is more wide-ranging.

Can't this sentence be assigned the value of "True"? If you have those 3 possible assignments (and there is no additional "unknown" value that may be assigned) then the sentences may be true or false or "infinite loop". If it were infinite loop then it would be false. If it were false then it would be infinite loop. But if it is true, then (since true isn't infinite loop) it is true.

Yep, it can be assigned that if you use the fixed point definition of truth.

A similar conjecture is: "Omniscent Omega tells you that you see is an illusion."

It could be interpreted as a) Omega is real, it said truth and thus I see is an illusion. b) Omega is not real and thus Omega is illusion, no matter what it says. In both cases I see an illusion.

This paradox appears in the discussions about the Simulation Argument in the following form: some people object to SA: if I am in simulation, I can't make any conclusion about the outside world and thus I can't use the computer power estimations to prove future AI capabilities, and thus SA does not work.

However, as it is already assumed that you are in simulation, SA is already proved, no matter what you can or can not conclude, and it is similar to (b) branch of Omega paradox from above.

How does this last sentence end?

Unfortunately, I didn't see this comment and now I can't remember, so I just removed it and we'll never know.