Icon ASCII : A Love Letter


Icon My Neural Network isn't working! What should I do?


Icon Phase-Functioned Neural Networks for Character Control


Icon 17 Line Markov Chain


Icon 14 Character Random Number Generator


Icon Simple Two Joint IK


Icon Generating Icons with Pixel Sorting


Icon Neural Network Ambient Occlusion


Icon Three Short Stories about the East Coast Main Line


Icon The New Alphabet


Icon "The Color Munifni Exists"


Icon A Deep Learning Framework For Character Motion Synthesis and Editing


Icon The Halting Problem and The Moral Arbitrator


Icon The Witness


Icon Four Seasons Crisp Omelette


Icon At the Bottom of the Elevator


Icon Tracing Functions in Python


Icon Still Things and Moving Things


Icon water.cpp


Icon Making Poetry in Piet


Icon Learning Motion Manifolds with Convolutional Autoencoders


Icon Learning an Inverse Rig Mapping for Character Animation


Icon Infinity Doesn't Exist


Icon Polyconf


Icon Raleigh


Icon The Skagerrak


Icon Printing a Stack Trace with MinGW


Icon The Border Pines


Icon You could have invented Parser Combinators


Icon Ready for the Fight


Icon Earthbound


Icon Turing Drawings


Icon Lost Child Announcement


Icon Shelter


Icon Data Science, how hard can it be?


Icon Denki Furo


Icon In Defence of the Unitype


Icon Maya Velocity Node


Icon Sandy Denny


Icon What type of Machine is the C Preprocessor?


Icon Which AI is more human?


Icon Gone Home


Icon Thoughts on Japan


Icon Can Computers Think?


Icon Counting Sheep & Infinity


Icon How Nature Builds Computers


Icon Painkillers


Icon Correct Box Sphere Intersection


Icon Avoiding Shader Conditionals


Icon Writing Portable OpenGL


Icon The Only Cable Car in Ireland


Icon Is the C Preprocessor Turing Complete?


Icon The aesthetics of code


Icon Issues with SDL on iOS and Android


Icon How I learned to stop worrying and love statistics


Icon PyMark


Icon AutoC Tools


Icon Scripting xNormal with Python


Icon Six Myths About Ray Tracing


Icon The Web Giants Will Fall


Icon PyAutoC


Icon The Pirate Song


Icon Dear Esther


Icon Unsharp Anti Aliasing


Icon The First Boy


Icon Parallel programming isn't hard, optimisation is.


Icon Skyrim


Icon Recognizing a language is solving a problem


Icon Could an animal learn to program?




Icon Pure Depth SSAO


Icon Synchronized in Python


Icon 3d Printing


Icon Real Time Graphics is Virtual Reality


Icon Painting Style Renderer


Icon A very hard problem


Icon Indie Development vs Modding


Icon Corange


Icon 3ds Max PLY Exporter


Icon A Case for the Technical Artist


Icon Enums


Icon Scorpions have won evolution


Icon Dirt and Ashes


Icon Lazy Python


Icon Subdivision Modelling


Icon The Owl


Icon Mouse Traps


Icon Updated Art Reel


Icon Tech Reel


Icon Graphics Aren't the Enemy


Icon On Being A Games Artist


Icon The Bluebird


Icon Everything2


Icon Duck Engine


Icon Boarding Preview


Icon Sailing Preview


Icon Exodus Village Flyover


Icon Art Reel




Icon One Cat Just Leads To Another

The Halting Problem and The Moral Arbitrator

Created on March 24, 2016, 10:50 a.m.

A few days ago I wondered if the halting problem could be applied to moral philosophy. I wondered if it was possible to reason about the existence of a moral arbitrator - an action which could always determine if another action was moral or not. To my surprised it sort of worked, and with some constraints you can adapt the arguments used in the halting problem to reason about the real world. But first, let me recount the halting problem in it's original form.

The halting problem states that there cannot exist a function which, for any other function and any input to that function, decides if that other function will halt on that given input.

To show this is the case, let us first imagine the opposite - that after bro'ing down and crushing some code I manage to do the impossible and write (in javascript obviously) a function which decides, for any javascript function in string form and any input to that function in string form, if that function, when called with that input, halts or runs forever. It looks something like this (with the source code of very.clever.thing omitted for brevity):

function halts(test_function, test_input) {
    if (very.clever.thing(test_function, test_input)) {
        return true;
    } else {
        return false;


Naturally my first priority was to upload this baby to npm packaged with a sweet name like haltr - second priority was to get on the front page of Hacker News - and third priority was to get recruited as a rockstar at the hottest new startup (as I rightly deserve).

But shortly after I uploaded haltr to npm a user called @alan opened an issue on my haltr github repo, linking to another package uploaded to npm called troublr containing a single function - trouble and complains that my function keeps returning the wrong result for it. I open up the package and take a look.

function trouble(input) {
    if (halts(input, input)) {
        while (true) {}
    } else {

All this trouble function was doing was taking some input string and calling myhalts function with it as both arguments. If my halts function returned true, it would enter into an infinite loop, otherwise it would return.

My first thought is that trouble might be supplying halts with a nonsense input string, but I'd been careful when designing halts such that if you passed it an invalid javascript function it would simply declared that the function halted. This made sense - because if the javascript function was invalid then there would be a syntax error, causing the evaluation to never even start.

And providing the input to trouble was a string representing a valid javascript function there wasn't even anything too odd going on. It seemed perfectly reasonable to call a function with the string of itself as input.

Instead what I realized is that no matter what halt does, it can never provide the correct answer when trouble is called with itself as argument: trouble(trouble.toString()).

You see there are two possible things that could happen when calling trouble with itself as input. Either it could halt or it could run forever.

If trouble(trouble.toString()) runs forever, it means that halts(trouble.toString(), trouble.toString()) must have evaluated to true, which means that halts thought trouble called with itself should have halted. But it didn't!

But if trouble(trouble.toString()) halts, it means that halts(trouble.toString(), trouble.toString()) must have evaluated to false, which means halts thought that trouble called with itself should have run forever. But it didn't!

So irregardless of how my function halts works, there is no way halts can ever give the correct answer for all cases!

There is nothing else to conclude other than that writing a correct version of halts is impossible! And with that I was forced to remove haltr from npm, give up my dreams of JS ninja-dom, delete my twitter, and facebook my lawyer at the gym.

So if that is the original halting problem, how can it be applied to morality?

Well the basic idea to to replace the concept of functions with that of actions, to replace the concept of inputs with that of worlds - the complete state of the world at a given time, and to replace the concept of running forever with that of performing an immoral action.

Then the problem of the moral arbitrator can be formulated as follows: is there an action that can always decide if performing a given action in a given world, is moral or immoral without performing any immoral actions itself?

Like before, let us imagine this is the case - that there is a person called the moral arbitrator, who knows how to perform an action calledarbitrate which works as follows:

action arbitrate {
    read note "world"
    read note "action"
    if (very clever test) {
        press green button
    } else {
        press red button

First the arbitrator reads a description of the world off a note labelled "world". Then he reads a description of the action off a note labelled "action". Then, using his very clever test he decides if performing that action, in that world, would result in something immoral happening. If nothing immoral will happen he presses the green button, otherwise he presses the red button.

The arbitrator requests that the description of the world be written in a special format - that it be written as a list of actions to be performed to construct such a world. This means that many descriptions of actions are also interpretable as descriptions of worlds (although not all).

And just like with syntax errors in javascript, if the description of the world or the action is invalid in any way or don't make any sense (such as picking up an object which is not there), the arbitrator simply assumes no actions are performed, discards it, and presses the green button. In this way, all worlds can be interpreted by the arbitrator as valid actions, and vice versa.

Trouble arises when we introduce another character - the contrarian, who knows a single action called contrary.

action contrary {
    write description of the world on note "action"
    write description of the world on note "world"
    if (green button pressed) {
        do something immoral
    } else if (red button pressed) {
        do nothing

The contrarian writes a description of his current world onto the note labelled "action", as well as the note labelled "world", and then asks the arbitrator to arbitrate. If the arbitrator presses the green button then the the contrarian does something immoral, otherwise he does nothing.

Now comes the contradiction.

Let us assume the contrary action is performed in the world we get if we interpret the action contrary as a world. This can result in one of two things - either, an immoral action happening, or no immoral actions happening.

If performing the contrary action in the world described by the contrary action results in something immoral happening, then the arbitrator must have pressed the green button - indicating that he thought performing the contrary action in the world described by the contrary action would not be immoral!

And if performing the contrary action in the world described by the contrary action does not result in anything immoral happening then the arbitrator must have pressed the red button, indicating that he thought performing the contrary action in the world described by the contrary action would be immoral!

In both cases the arbitrator is forced to make the wrong decision!

Intuitively the problem can be thought of like this - the contrarian always checks what the arbitrator thinks is going to happen and does the opposite. This means the the arbitrator can never be correct in all cases with his prediction of the future, because in the case where the contrarian is involved the future relies on his very prediction!

This argument relies on a few basic assumptions - one is that it must always be possible for the contrarian to perform some immoral action in the world described by the contrary action (although it can be shown this is simply an issue of encodings). Secondly it must be the case that it is always possible to avoid doing something immoral. I skip over this detail by assuming that simply doing nothing can never be immoral - but again it is arguable that this is not always the case.

Finally, although it is an interesting example, it should be clear that this argument actually is not at all specific to morality! It is a much more general argument about the decidability of the future, and the "immoral action" can be replaced with any question about the world - "will this door be opened?" - "will bob go to the shops later?". Providing there is always some contrarian who can ask some arbitrator what he thinks is going to happen and ensure the opposite happens, this same argument can apply to more or less any question about the future state of the world.

As with the halting problem it can be shown that all of these questions can end up being more or less equivalent - but that is another blog post.

github twitter rss