Last week’s article was about ”Are Some Infinities Bigger Than Others?” and the Cantor Diagonal argument. This week I want to share one of my favourite Theoretical Computer Science Problem.

I remember back in middle school when I started doing Computer Science, I thought that I could theoretically solve any Computational Problem with the right Mathematical tools and Programming. I was wrong. There is Theoretical limitation to any Computing Machine and here we will see the proof that there is at least one logic problem that no Computer Program will ever be able to solve.

Defining H, The Impossible Computer Program

We define a Computer Program P(i) as a list of instructions P that when executed with an input i, give an output o.

For instance,

is a program that sums the two numbers you give it as inputs, and,

is a program that uses another program — P_add — as input, and passes this program the two other inputs. It does what P_add(a,b) does and doubles it.

When a program is executed, it can get stuck, run forever and never output anything, for instance, a program P_sum which proceed to the sum of all natural numbers will keep on adding natural numbers forever without ever finishing running (i.e., halt) and outputting the result.

Now let’s suppose that it exists a program H(P,i) that take as an input the list of instructions P of the program P(i) and i the input of P(i), and output a 1 if P(i) halt at some point and 0 if P (i) get stuck and run forever. To put it simply,

Why The List Of Logic Instructions H Cannot Possibly Exist

Based on Alan Turing’s proof in the paper ”On computable numbers, with an application to the Entscheidungsproblem”-1937, we will prove that H cannot exist.

Based on the assumption that H exist we construct a program X(P) that run forever if and only if H(P, P) = 1 and halt if and only if H(P, P) = 0. In other words,

We can now consider giving X(i) its own list of instructions X as an input: X(X).

Therefore X(X) run forever if and only if H(X, X) = 1 and X(X) halt if and only if H(X, X) = 0. In other words,

We have a contradiction! We have shown by Reductio ad absurdum that H cannot exist since its existence lead to absurd conclusions.

Therefore a Computer Program that can determine if any Computer Program given any input will be stuck and run forever or finish running is impossible. There is at least one Computer Program solving a logic problem that cannot possibly exist.

References, Alan Turing. “On computable numbers, with an application to the Entscheidungsproblem”. 1937.

I’m Maxim Perumal (Maxim xyz), Co-Founder of Relativty.com, a VR headset I designed from scratch, of which I Open-sourced the code and the hardware. Follow me on Twitter @maxim_xyz.

As a side note I’m not a Mathematician but a high school student — who hasn’t attended school for an entire year — and mostly a Computer Science enthusiast and programmer. That said, I taught myself Mathematics and want to share the beauty of some of my favourite Mathematical proofs in this series.

Do You Know How To Count?

When wondering whether some infinities can be bigger than others, it’s important to know what being ”bigger” means, and that involves defining countability. We can get a sense of this from real life experience: when you count apples you attribute a number to each one, starting with 1 and incrementing by 1 each time until there are no more apples to count.

In other words, you are pairing each apple, or any element of a set (or basket), with a unique positive integer. Therefore we can define a countable set as a set for which we can pair each element to one unique element of N, the set of natural numbers {0, 1, 2, . . .}.

It’s worth noting that we can pair each element of N, the set of natural numbers, with each element of itself. Therefore N is a countably infinite set; we could count every number of the infinite list of natural numbers, if we had an infinite amount of time…

Are There More Integers Than Natural Numbers?

Is Z, the set of all integers {…,-2,−1,0,1,2,… }, bigger than N, the set of natural numbers {0, 1, 2, . . .}? Seems like a weird question, right? I can still remember the excitement and joy shared by my best friend and me back in middle school when we surprisingly proved to each other that Z is actually the same size as N. Here, the exact term isn’t actually ”size” but ”cardinality”, which means the number of elements in a set.

The proof is actually quite simple, we can pair each negative number of the set Z to a unique natural odd number and pair each positive number of the set Z to a unique even number. Therefore we can count Z with N.

Even though we might think that there are more positive and negative integers than there are only positive integers we can pair each element of Z with a unique element of N.

Some Things You Couldn’t Count Even With An Infinite Amount Of Time,

Here we are going to prove that the set R of all real numbers is uncountable and we’ll be doing this using Cantor’s diagonal argument.

First, we suppose that we can list all real numbers between 0 and 1,

For instance, we can suppose,

Now consider the number d,

d, being made of the diagonal of our list. The first digit of d is the first digit of the first number of the list, the second digit of d is the second digit of the second number of the list, and so on adding digits diagonally for the entire list.

So, for any i,

For instance, given this list,

Now we construct the number x,

such that the i-th digit of x is different from the i-th digit of d and is not equal to 9, so

For instance for d = 0.16392… we can construct x = 0.27413… and continue for each digit of d since even if xi≠di there are still 8 possible digits di can be equal to.

We can now prove that x is missing from the list of all real numbers between 0 and 1.

By construction, the first digit of x is different from the first digit of d, and the first digit of d is the first digit of the first number of the list. So x can’t be the first number of the list since it has a different first digit.

By construction, the second digit of x is different from the second digit of d, and the second digit of d is the second digit of the second number of the list. So x can’t be the second number of the list since it has a different second digit. This goes on for the all numbers on the list.

In other words,

which by construction can’t be true since,

We have shown that if you create a list of all the real numbers between 0 and 1, x will always be missing. This contradiction proves that the set of all real numbers between 0 and 1 is uncountable, and therefore that R, the set of all real numbers, is also uncountable. You can’t pair each real number to a unique natural number.

This means that the cardinality of R is greater than the cardinality of N, therefore some infinities are bigger than others.

References, Georg Cantor. ”Ueber eine elementare Frage der Mannigfaltigkeitslehre”. 1891.

I’m Maxim Perumal (Maxim xyz), Co-Founder of Relativty.com, a VR headset I designed from scratch, of which I Open-sourced the code and the hardware. Follow me on Twitter @maxim_xyz.

Over the past days, I’ve received a lot of emails asking about the future of Relativty’s maintainership. There were then messages posted on our Discord’s server asking about my absence from day-to-day decisions and how this was slowing down Relativty. From this, the community requested that I clarify my vision for the project’s future and initiate the debate about our decisional power structure. So that’s what this open letter is about.

Why Gabriel and I built Relativty,

In middle school, Gabriel and I were really interested in VR, and when we got to high school, we built our own VR headset from the ground up. It cost us around $100 and was the only way for us to afford a VR headset.

My theory is that VR democratization needs inexpensive hardware and abundant content. This framework can be seen with the computer mouse, which went from costing $300 to $15, and which went from being almost useless to being the norm.

We open-sourced our hardware architecture and SDK because we wanted to at least try to help create the building blocks of affordable hardware and tools for content production.

What we have achieved

Once the project was out there, we went from the two of us working alone in my bedroom to a community of hundreds. I spent the first months building a community and leading the project’s maintenance and improvement along with Gabriel.

With the community’s help, the list of games compatible with the headset grew from two to hundreds. Check out the relativty-OSVR-plugin.

Contributors came up with new and better designs — like TheYxxy’s distribution, which I appreciate a lot — and they quickly upgraded the core’s code and expanded compatibility with more Arduino boards.

It’s hard to tell exactly how many people built the headset — there are over 200 emails in my inbox of people mentioning their build of the headset. It’s easier to say that we inspired a lot of makers and VR enthusiasts, and half a million people went through our GitHub and Medium content.

Why I don’t have as much time for Relativty anymore

During all of this, I didn’t talk about my situation and I disappointed some of you, my community, by being increasingly in the shadows and slower to respond.

I like to focus and go deeply into subjects, and I’ve been working on a new project over the past months (I even dropped out of school) that has resulted in increasing unavailability.

I’m now diving more into the content aspect of my democratization framework. I spend my time studying Machine Learning and testing new ways to produce content. As VR hardware is becoming cheaper and cheaper, providing the infrastructure to help produce the content that will result in more incentives for the general public to buy HMDs is, I think, crucial.

The new governance model

The signals of dissatisfaction with the lack of an effective governance model were there: people created a Patreon account for Relativty, an alternative website, an alternative repository, and stopped using Relativty’s GitHub.

So here is Relativty’s new governance model. My role is now to embody Relativty’s philosophy of helping democratize VR by creating building blocks of affordable hardware architecture and tools to create content.

Then there is the Committee, consisting of a small group of contributors: TheYxxy, Lost Garden (Haruun), Hugo Garritsen, and Кзобьтовскый, who are able to make decisions and lead the community forward according to my philosophy.

This small group will work to achieve consensus, act as leaders, and when needed, will come back and talk to me.

What matters for the future of Relativty

I’m really enthusiastic about the future of Relativty. The amount of work yet to be accomplished is growing with the added ambitions of new contributors working alongside early ones.

I’ll be more active on the server and will be talking every week with the Commitee to ensure everything is going well and help them articulate and execute the vision.

Here are the goals for the next 3 months:

-Achieving more accurate 3D tracking of the headset based on 9DOF IMU and sensor fusion. Adding camera’s processing movements is definitely an option to consider.

-Release a pre-Alpha standalone Headset running on Android. It is easy to run the headset on an ARM Cortex A7 CPU using our custom Unity libraries, which Gabriel and Sensei have done in the past. The greater challenge is to achieve this for regular Android VR games.

A team is also working on substituting Fresnel Lenses with a Biconvex lens. They’re looking into this because Fresnel lenses have a discontinuous shape, which tends to cause scattering, resulting in lower contrast for the HMD. The goal is also to reduce the lenses’ focal length in order to shrink the headset.

I will write more often about what I’m working on and keep you updated, you can expect me to be more active on Twitter and on our Discord server. You can follow me on Twitter @maxim_xyz.

The wonderful illustrations come from the great Josan Gonzalez. His art has been a source of inspiration since the beginning of Relativty for both Gabriel and me.

Maxim

I’m Maxim Perumal (Maxim xyz), Co-Founder of Relativty.com, a VR headset I designed from scratch, of which I Open-sourced the code and the hardware. Follow me on Twitter @maxim_xyz.

My name is Maxim Perumal (Maxim xyz). I’m 16 and I built my own VR headset with my best friends, Jonas Ceccon and Gabriel Combe. And it ended up costing us $100.

I started programming when I was 13, thanks to my math teacher. Every Monday and Tuesday, my friends and I used to go to his classroom to learn and practice instead of having a meal at the cafeteria.

I spent one year building a very basic 8-bit OS from scratch and competing in robotics contests with my friends.

I then got interested in VR and with my friends we agreed that it would be really cool to create our own world in VR where we could spend time after school. But facing the fact that an Oculus was $700 at the time, we decided to build our own headset.

Making VR accessible to everyone?

It was because of an anime called Sword Art Online where the main character is in a virtual reality RPG that I fell in love with VR. I wanted to understand every aspect of it.

I bought the cheapest components I could and we started by learning the very basics of the physics and math behind VR (proper acceleration, antiderivatives, quaternions…). And then we re-invented VR. I wrote WRMHL, and then FastVR with Gabriel. Putting all of this together, we ended up with a $100 VR headset.

A fully hackable VR headset and development kit

To speed up VR development time, we built FastVR, an open-source SDK for developers that is easy to understand and customize. It works like this:

• The core headset computes the position of the headset in space;
• The position is sent from the headset to WRMHL, and part of the CPU’s power is dedicated to reading those messages;
• Then FastVR retrieves the data and uses them to render the VR game.

Everything you need to build the headset has been open-sourced and can be hacked.

Why open source?

I want to make VR mainstream. So I reached out to Oussama Ammar, one of the co-founders at The Family. I talked to him about setting up a company and launching a Kickstarter.

But he convinced me that for now, it’s better to wait on starting a business, to keep meeting others who have the same goals, and to keep learning.

We took a trip to Silicon Valley and Oussama introduced me to the chief architect at Oculus, Atman Brinstock. And they gave me some precious advice: make all of this open source.

The Next Step?

There are still a lot of technical points that we want to improve.

Our big focus right now is on a standalone VR headset, which we already have as a simple version, and cheaper 3D tracking.

All of this will be released soon.

How do I get started?

If you want to learn more about the technical side and build your headset, just follow the guide by clicking here. Star the repo if you liked it ⭐️

I would love to hear about what you’ve experienced while building the headset, or if you need any help or have any questions. Ping me at maxim@unai.one or on Twitter @maxim_xyz.