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 RAGE

 

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 LOL I DREW THIS DRAGON

 

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;
    }
}

Boom!

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 {
        return;
    }
}

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"
    arbitrate
    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