Two Proofs That The Set of All Computable Ordinals Is Not Computable

Posted on August 16, 2025 by mmiliauskas

Is the Kleene’s set $\mathcal{O}$ of all computable ordinals computable? The answer is, no. It is an old result, but I think trying to prove it yourself is a good exercise to learn some basics when it comes to ordinals.

Note, in the proofs below ordering = well-ordered set.

Proof #1

Suppose $\mathcal{O}$ is computable, then it is listable: $\text{ALL}[i] = <_{i}$ . Using ALL we can construct a new computable ordering: $<_x(m,n)= \neg \text{ALL}[m](m,n)$ . $<_x$ is computable, therefore in the list ALL, so it has some index $j$ : $<_x = \text{ALL}[j]$ . We can now give $j$ as an input to $<_x$ and obtain a contradiction: $<_x(j,n) = \text{ALL}[j](j,n)$ and $<_x(j,n)= \neg \text{ALL}[j](j,n)$ . Therefore, $\mathcal{O}$ is not computable.

Proof #2

Suppose the set of all computable ordinals is computable. Then it is listable: ALL[i] = $(\mathbb{N}, <_i)$ (I will conflate $(\mathbb{N}, <_i)$ with $<_i$ ). We can construct a new computable ordering:

def <_ALL(m,n):
    (b1, x) = unpair(m)
    (b2, y) = unpair(n)
    if b1 == b2:
        b = ALL[b1]
        return b(x, y)
    else:
        return b1 < b2

$B=(\mathbb{N},<_{\text{ALL}})$ is a computable ordering of type $\beta$ . $A_i = (\mathbb{N}, <_i)$ is a computable ordering of type $\alpha_i$ .

If we could prove that $\forall i :\beta > \alpha_i$ , then this would prove that $\beta$ is not in the list ALL. Let’s do that.

For every $i$ we can construct a new computable ordering $<_{ALL'}$ :

ALL' = copy(ALL)
ALL'[0], ALL'[i] = ALL[i], ALL[0]

def <_ALL'(m, n):
    (b1, x) = unpair(m)
    (b2, y) = unpair(n)
    if b1 == b2:
        b = ALL'[b1]
        return b(x, y)
    else:
        if b1 < i and b2 == i:
            return False
        elif b1 == i and b2 < i:
            return True
        else:
            return b1 < b2

For every $<_{\text{ALL'}}$ there exists an order-preserving bijection $g(x)$ s.t. $x <_{\text{ALL}} y \Longleftrightarrow g(x) <_{\text{ALL'}} g(y)$ :

def g(x):
    (k, z) = unpair(x)
    if k != 0 and k != i:
        return x
    else:
        if k == 0:
            return pair(i, z)
        else:
            return pair(0, z)

Therefore ordering $B_i = (\mathbb{N}, <_{\text{ALL'}})$ also has the order type $\beta$ . Next, let’s take the initial segment of $B_i$ , namely $C=({ x \in \mathbb{N} ~ | ~ (k,z) = \text{unpair}(x) \land k < 1 }, <_{\text{ALL'}})$ . $C$ has the order type $\alpha_i$ . Because $C$ is a proper subset of $B_i$ , $\beta > \alpha_i$ . Since we can perform the same procedure for every $i$ , $\forall i : \beta > \alpha_i$ .

So a computable ordering of type $\beta$ is not in the list ALL. Yet, $<_{\text{ALL}}$ is computable. So either:

ALL is not a full list of computable ordinals, which means it is not computable, or
$<_{\text{ALL}}$ is not computable, but unpair(x) and ALL[i](x,y) are computable, which only leaves the list ALL to be not computable.

Thus, ALL is not computable and therefore the set of all computable ordinals is not computable.

A Loopy Little Essay on Truth

Posted on November 14, 2024 by mmiliauskas

In this essay I would like to give a proof of a certain definition of truth. Let us refer to this definition as H. But what would this kind of proof even look like? Well, it is an argument for something, so there should be a set of propositions provided. All the propositions should work together in order to build a case for the proposed definition. As an author, I would be considered to accept all of those statements as true by default. [A] However, you as a reader would assign your own truth values to each and one of them. Finally, you would assign your verdict on the truthhood of H.

The first paragraph has already listed some propositions. We are on the right track. You probably have already assigned some rough truth values to all of those propositions. This would mean that the proposition A is true for you. [B] This kind of border check procedure takes place every time somebody presents us with some truth to be imported. The exact process is somewhat opaque. However, we can often observe how some truths seem to just pass through via a fast-lane as if they are citizens. Others might meet quite a bit of resistance together with some support. Their process is much lengthier and can take from seconds to months or even forever. They exist in a kind of quarantined area. We could say that their truth value is maybe. For example, the implicit proposition “H is true” at the moment is in the maybe state; it is still being evaluated. There are also truths that we outright reject. We might come around to them in later stages of our understanding of the world, but at present they receive the status of being false.

Where did the proposition B land for you? Would you say it is true? What arguments were for it to be true? How about for it to be false?

In my experience, the border check is always active when I read somebody’s argument. But I have already stated that. However, what I have not stated yet is that when I am in writer’s mode, the border screening is very much active too. Frankly, the whole process of writing could be summarized as throwing shit at the wall and seeing if it passes the border. The second paragraph is a good example of a paragraph that passed. But I did have to open the bags. For example, I started to wonder about the extreme cases like radical skeptics or trivialists. Do they operate in the described fashion? If we suppose that there actually is such a person that truly embodies a radical skeptic, for her, all knowledge is permanently quarantined. If we apply the same leeway for a trivialist, for him, every proposition is true. He has an open border policy. Thus, even in the extreme cases there appears to be a border and a procedure of dealing with inbound propositions. This reasoning was enough for me to keep the second paragraph. However, I should note that this sentence right here was added later during the revision of the paragraph; I realized that I am not completely confident using both “radical skeptic” or “trivialist” concepts in this context and I need a bit of a memory refresher [I should also not that the bolded text was also product of even further revision]; therefore the battle for the second paragraph was much more recursive then it would appear on the surface; suffice to say that the initial tension was resolved in favor of keeping those concepts¹.

Personally, I find propositions that are in the maybe state to be the most interesting. Whether the proof is formal or informal, you still get to partially see the cogs of your truth making machinery turning. This emotional rollercoaster is eloquently depicted by Douglas Hofstadter²:

It is easy to imagine a reader starting at line 1 of this derivation ignorant of where it is to end up, and getting a sense of where it is going as he sees each new line. This would set up an inner tension, very much the tension in a piece of music caused by chord progressions that let know what the tonality is, without resolving. Arrival at line 28 confirms the reader’s intuition and gives him a momentary feeling of satisfaction while at the same time strengthening his drive to progress towards what he presumes is the true goal.

[…]

This is typical of the structure not only of formal derivations, but of informal proofs. The mathematician’s sense of tension is intimately related to his sense of beauty, and is what makes mathematics worthwhile doing.

Though we have not covered many topics, we did talk about them in a rather loopy fashion. A recap would do us good. First, we stated that every proof needs a set of propositions because otherwise how on Earth are we going to build an argument that would convince somebody that something is indeed true. Second, we have seen some of the propositions in favor of the definition of truth in question already. Some I hope you agreed with. Suppose you were convinced of all of them. Was this enough to convince you of H? Obviously, not. For one, the definition itself has not been stated yet. And two, should these kinds of defenses not be preceded by some background knowledge, perhaps including previously stated theories of truth?

Let us address the question of the background knowledge first. The most popular theory of truth in philosophical circles is the correspondence theory. It has some arguments for it that seem valid. It also has some criticism that also seems valid. In short, it has a set of arguments for it and a set of arguments against it. The definition of truth in correspondence theory is a proposition as well. We can state it here as “truth is correspondence to facts”. Aristotle, Descarte, Locke, Leibniz, Hume and many other great philosophers were advocates of this theory. It also has some opponents, namely the advocates of different theories of truth, such as deflationism or coherentism. If we were to present the theories of deflationists or coherentists, they would have the exact same form. Both of them would have some excellent arguments for them, usually at the expense of other theories. They would also have some great arguments against them. They too would have some famous philosophers as their proponents and opponents. There is a great count of other theories and even a greater count of their different flavors. However, to my knowledge, they all seem to follow this pattern. There is one final thing worth noting that is kind of loosely implied by the previous propositions, namely that amongst the philosophers even today there is no clear consensus which theory is right³.

Now that we have stated all the necessary background knowledge and presumably made some arguments for the definition, can we finally state it? Let us suppose I just did. I just stated what the H is. All of the propositions above were meant as empirical evidence for H. So far as you read those propositions you might have agreed with some or most of them. If you have not agreed with any of them, most likely you are no longer with us. However, you might be hesitant to agree that they prove H itself. You know what? Let us even assume you have some serious criticism, maybe you are a deflationist and truth is not a thing for you. Once you read that “the definition of truth is …” you already had one in the chamber ready to fire, and you immediately emailed me your argument against H. After reading the criticism, yours truly realized that there is indeed a problem. Upon further investigation, this author found it impossible to refute that there are instances where the definition fails. At this point the only way to save H would be reply saying that all of the truth theories face the exact predicament – my definition is no different. However this reply would be a strategic mistake. My counter-argument would be self-defeating, since it would appear that I promote pluralism. Therefore, my theory would simply collapse into just one more argument for the pluralist theory of truth. In addition, by sacrificing self-conviction I would render my definition to be inferior to all the other theories of truth.

It is a good thing I have not stated the definition yet. So far we just had a hypothetical discussion of some hypothetical definition of truth. I still have a card to throw, and the card is to define truth as a product of two opposing sets of truths. Not a pluralist anymore, instead of acknowledging that other definitions have the same flaw, I managed to fit everyone into the definition. However, I did something more here too. By acknowledging criticism as part of the truth nature, I have promoted this definition above others. Correspondence, coherence, deflationist theories, all have to live with the annoying neighbor called criticism, whilst the proposed definition invites it and turns it into an argument for it.

First question that might come to one’s mind is what is this product exactly? We have already seen few examples, but here are few more:

A peace treaty between two countries.
A verdict by a judge.
A theorem that comes out of a proof.
A memory recalled.
A decision that was decided.
Item #1 on this list.
This list.

Instances of the word “product” here have many shapes, however they are all united by how they are forged. Namely, they are all results of a resolution of a tension that has once existed. More colloquially we could express the definition as truth is truce. We could also phrase it as truth is a product of criticism. This phrasing allows us to see what would happen if we were to construct a truth function based on this definition, and then feed the definition to this function. The proposed definition of truth would be a fixed point – even if somebody managed to provide any valid criticism, they would only be doing what the definition says would happen.

This document itself was once called “A weird essay on truth” before it became “A weird essay on truth (V2)” – I felt that all of the paragraphs should reapply after being quarantined for two weeks.
↩︎
Hofstadter, D. R. (1999). Gödel, Escher, Bach: an eternal golden braid. Basic books. ↩︎
Based on a survey conducted in 2009, when faculty members from 99 leading philosophy departments were asked, ‘Truth: correspondence, deflationary, or epistemic?’, 50.8% answered correspondence,24.8% deflationary, 6.9% epistemic, and 17.5% other. (Bourget, D., & Chalmers, D. J. (2014). What do philosophers believe?. Philosophical studies, 170, 465-500) ↩︎

Norway Road Trip

Posted on November 11, 2024 by mmiliauskas

First night of camping ended up at 2AM and us running back to the car due to being too optimistic about Norway’s weather in autumn.

However, it was nice just to sit down in the middle of nowhere with a view to a waterfall and to cook some food, and talk shit about city life.

Gudvangen

It turns out that in Norway it was raining all August and the rain did not stop in September. At this point I started to think if I did a major mistake yoloing the weather research. Most of the nights we didn’t even bother with the tent and just slept in the car. It seemed like a drier and warmer way to sleep with very little sacrifice of comfort.

There was one nice day when the clouds cleared and we managed to squeeze in a hike:

Whilst on our way back from our hike in Bakka, we saw a French guy just backpacking through the rain. He was hitchhiking and traveling by bus through Norway. He ended up in our camp. I watched him put a tent through a heavy rain. Fuck, he had worst than us. We talked for a bit. Apparently he was traveling around Norway until December. It was his dream.

It is interesting how you feel shitty realizing that you might have timed the season bad, it is pissing down with rain, you are moody, your girlfriend is even moodier, yet you see that you are not alone with your shitty holiday decisions and everyone is just moving forward. So you too start moving forward.

Before you get used to them, mountain have this devouring effect. You can stand at the most random spot and simply watch.

Stana Gard

Eventually the rain started to get the best of two of us. The initial idea was to camp all the way, but the batteries seem to start running low. A little bit of luck and we found a small house to rent on a shore of a fjord just two hours away from Gudvangen. The house was built in 1930s and it made you want to start your poetry career as soon as you open the door.

The Bulgarian

Meanwhile the weather forecast started to get better. Initially seeing all this rain I have buried the original plan to hike for four days to Trolltunga from Kinsarvik. However, now it seemed like we are back in the game. The only problem was the final cloudy days that we need to kill. And here we were back to that parking lot life.

The parking spot was in a really nice, 24 hours, with a toilet. The only problem was that on the first day some guy with French plates pulled over and took a massive shit that killed the toilet for everyone and just bounced. I was still taking a nap when I saw him come out. After seeing the smirk on his face, I new right there that we might have a problem.

Soon after a new character entered the movie, the Bulgarian. A retired miner who worked in Australia and was apparently traveling with a camper, just fishing around the world. He was proper pissed off that the toilet was clogged and quickly started the investigation: “was it that car?”, “shit, it was probably that fatty”, “fucking hell, what were the numbers of the car?”. I am pretty sure I was his primary suspect, since when he came back from fishing it was just me and the crime scene at that point.

Kinsarvik – Stavali

Once the weather cleared, we stayed one night at a hostel to prepare for the four day hike. The next day we left my car near some grocery store and took a bus to Kinsarvik — our starting point. The hike itself was beautiful. I lost the water bottle almost at the start, but in Norway it is a useless thing to carry anyways. At some point we lost the markings of the trail too, so had to improvise.

Luckily we made it to Stavali. There was a point when it got dark, no cabin insight, rain had made the rocks wet and slippery, and at the most crucial moment my Garmin Instinct was just as lost as we were. It is interesting how in these kind of situations your mind becomes 100% focused on the survival, switching-off the pain, making you run over the slippery rocks in almost complete darkness, yet you make no mistakes. Nothing but a blind optimism that drives somebody in the moments like these.

It was great to finally reach the cabins and be greeted by a fiery full moon rising from the peaks of the mountains.

Stavali – Torehytten

The next day I had this pulsating headache that got worse when I moved. The good news was that there was another 20km hike ahead of us. Eventually, I just managed to walk it off, and that was an extra layer of beauty!

Mountain lakes, few random lemmings, and just quiet. For 20km.

I wish I had taken more photos of the Hårteigen mountain. It was definitely a highlight of the hike to see a mountain on top of the mountains. The good news was that Hårteigen turned out to be our new view from the porch.

Torehytten – Tyssevassbu

The next morning we were greeted by a helicopter. It landed next to our cabin and dropped off the cleaning guy with his dog. We packed our stuff and left for Tyssevassbu. This third stretch of 20km was by far the easiest. Whilst it was third day of the same difficulty trail, the body and mind seems completely used to it. There is no more pain. The kilometers just keep clocking. Rocks of different type become your new social media feed, only it makes you feel peaceful and fulfilled.

On this stretch you get to see large patches of hardened layers of snow. The ponds that form from it melting are actually refreshing to swim.

We have also encountered some eagles. First, just one of them started to circle us, then two others joined. Between us and them, not sure who was more entertained.

Tyssevassbu – Trolltunga – Tyssedal

On our final day of the hike we decided to wake up early and beat the crowds at Trolltunga. As the dawn was just breaking we were already walking. The trail itself was more of the same: lots of Norwegian sudoku.

Even though we had to backtrack multiple times and therefore took longer than expected, we managed to be amongst very few already at Trolltunga. We actually had the whole thing for ourselves. Initially I thought that maybe it was an overkill to get there so early before everyone else arrived only to realize 30 minutes later that, nope, I was right. People fucking kill shit.

It is a strange feeling to see crowds again after you have spent three days in the middle of nowhere with little to no contact with other humans. And then you see this stream…

According to my watch, we clocked about 76km in total. This picture encapsulates my mood at the end best:

The end

We thought about going to the Lysefjord next. However, in those four days it felt like we downloaded a torrent worth terabytes of data, most of which we didn’t even have time to process even partially. Going somewhere else felt like pouring water into a glass which was already beyond full. So we just bought the ferry ticket from Sweden to Poland and left for Sweden.

Metaverse Might Just Solve Climate Change

Posted on March 23, 2024 by mmiliauskas

For the longest I was somewhat pessimistic about how realistic the climate change fight is. First of all, there are a lot of prematurely optimistic headlines floated by the media on how a solid progress is being made. However, CO2 capture, renewable energy, pledges made during climate change conferences and so on, they all might look hopeful summarized in a title, but once looked under the hood, one quickly realizes how much work in progress they all are. Second, it is human nature not to care until the last minute, consuming and being hypocritical. Everyone is pointing fingers into the oil & gas industry and calling them the villain, because somebody needs to take the blame, it is surely not Us who are responsible, right? Nobody wants to use public transport, we are constantly gorging on cheap fashion and useless crap on Amazon, constantly just staring at our phones. We pretend to be super concerned about the environment but also need to “travel the world”, eat meat and so on. Finally and most cynical of all, the aforementioned consumerism is not a bug in our system, it is actually a feature, this is how the system is designed to operate. If we were to stop consuming, GDP would drop and we would have a recession, that would eventually turn into a depression, society would fragment, order would fall apart and we would end up with a bloodbath. In short, we find ourselves in a deadlock – if we continue to consume we are screwed, if we stop consuming we are also screwed, just faster and with a higher guarentee.

Seems like a dead end? Maybe not. Lockdowns have shown that a -6.4% change in CO2 emissions compared to 2019 can be actually achieved at any time just if we stayed at home. We have actually for the first time come very close to the -7.6% emissions target set by the 2015 Paris climate agreement. The drop in emissions was mostly contributed by reductions in transportation: aviation decreased by 75%, surface transport by 50%. Transportation is the biggest contributor to our GHG emissions. It is also one that is the most redundant going forward in our society connected by the internet.

2020-21 Covid-19 experience might be both a hint to a probable solution and a peek into where we are headed. Whilst the never ending lockdown future is dystopian, it might not be forced, but actually naturally transitioned into. Lockdowns have showed us that working, studying and socializing from home is viable even with such rudimentary technologies like Microsoft Teams, Zoom or Twitch.

Improvements in VR and development of the metaverse, might evolve virtual life from a crude substitute to a strong alternative or even main attraction. Most importantly, the creation of metaverse would solve the consumption part of the equation beyond transportation. Fashion industry is estimated to contribute 5–7% of total CO2 emissions – that could just become purely virtual. There could be further reduction in demand for iron, steel and cement (another -10%) if physical housing became less of an asset that it is today, especially in China, where ghost towns are being built purely for economic growth and investment purposes but not for living. Obviously, all of the mentioned CO2 reductions wouldn’t happen overnight nor reach an absolute zero. Certain amount of housing would still be needed, so would clothing, seldom haircut and so on.

Another interesting pro to this approach is countries like China and India would be forced to join this growing new economy or risk being left behind. Again, no need to ask for pointless pledges and promises – the West stops consuming cheap physical goods and transitions into cheap virtual goods consumption, producer economies will be forced to adjust or enter recession.

The only question is how far the VR tech can get us and how fast to keep us happy at home?

Martynas M.

Category Archives: Uncategorized