Halting Problem Proves That Lethal Robots Cannot Correctly Decide To Kill Humans

KentuckyFC writes: The halting problem is to determine whether an arbitrary computer program, once started, will ever finish running or whether it will continue forever. In 1936, Alan Turing famously showed that there is no general algorithm that can solve this problem. Now a group of computer scientists and ethicists have used the halting problem to tackle the question of how a weaponized robot could decide to kill a human. Their trick is to reformulate the problem in algorithmic terms by considering an evil computer programmer who writes a piece of software on which human lives depend.

The question is whether the software is entirely benign or whether it can ever operate in a way that ends up killing people. In general, a robot could never decide the answer to this question. As a result, autonomous robots should never be designed to kill or harm humans, say the authors, even though various lethal autonomous robots are already available. One curious corollary is that if the human brain is a Turing machine, then humans can never decide this issue either, a point that the authors deliberately steer well clear of.

Comments

I think

[fyngyrz]

I'm just going to reformulate the problem by considering idiots who use unrealistic, not-supported-by-evidence premises to make general statements as one that calls for sending killer robots after said idiots.

Re:I think

[ShanghaiBill]

The premise of TFA is that killer robots need to be perfect. They don't. They just need to be better than humans.

Which is more likely to shoot a civilian:
1. A carefully programmed and thoroughly tested robot.
2. A scared, tired, and jumpy 18 year old soldier, who hasn't slept in two days, and saw his best friend get his legs blown off by a booby trap an hour ago.

Re:I think

[Anonymous Coward]

1, when ordered to shoot civilians.

Re:I think

[bmo]

Product liability never results in anyone being actually responsible for the death going to jail or huge penalties.

A multinational might> pay out a couple of million in product liability, but then it will just be chalked up to the cost of doing business.

If the multinational is a defense contractor (BAE, Raytheon, Lockheed, General Dynamics, etc), it will all be swept under the rug and more money will be thrown at the contractor to "fix" it.

That's the reality.

--
BMO

Re:I think

[Anonymous Coward]

That which a bunch of Ethicists say should happen, and that which does happen, are often in dis-accord.

The military will build killer robots. The primary concern for behavior development won't so much be safety mechanisms against killing innocents or children as safety mechanisms against losing control. They don't want their robots turning on them. Beyond that, they want the robots to obediently slaughter whatever they are pointed at. This level of obedience is precisely what makes them useful as a weapon.

This will happen. Count on it, and adapt to it.

Re:I think

[AthanasiusKircher]

So we're cutting down the criteria to not just people carrying guns, but people carrying guns actively shooting at you?

Actually, the definition of civilian is well-defined in the Laws of War, commonly codified today in international laws by Protocol I of the Geneva Conventions.

In sum, a "civilian" is anyone who is not a "privileged combatant," i.e., basically someone (1) carrying arms, (2) taking orders in an organized military structure, and (3) following the laws and customs of warfare. (Also, usually privileged combatants are required to wear insignia.)

Someone who carries arms but does not satisfy those criteria is still a "civilian," though if those arms are actively used in support of an organized military force, he/she may be a civilian who is also an "unprivileged combatant," i.e., he/she not eligible for protection under the normal rules for prisoners of war.

So, actually the criteria are much more specific than you describe. "Civilians" can fight in wars, in which case they become "combatants," but they do not cease to be "civilians," as the term is commonly understood in contrast to organized military personnel.

As for the farmer in GGP's example, he's clearly a civilian unless he's a member of a military force. If he carries a gun but only for his own protection and does not engage in direct action against an enemy, he is probably assumed to be a "non-combatant" as well, under international legal definitions.

By the same logic

[Anonymous Coward]

By the same logic, computers should not be allowed in any life-critical situation. That includes hospital equipment, airplanes, traffic control, etc. etc.

Fortunately, we don't judge the reliability of computers based on the ability to mathematically prove that nobody has put evil code in on purpose.

Re:By the same logic

[tlhIngan]

By the same logic, computers should not be allowed in any life-critical situation. That includes hospital equipment, airplanes, traffic control, etc. etc.

Fortunately, we don't judge the reliability of computers based on the ability to mathematically prove that nobody has put evil code in on purpose.

In your examples, there are humans in the loop.

In this case, you have a robot trying to autonomously decide "kill" or "don't kill" when it encounters a human.

Hospital equipment - it's generally observed by personnel who after failures can decide to not use the equipment further (see Therac 25), or that changes need to be made in order to use the equipment. The equipment never hooks itself up to a patient automatically and provides treatment without a human involved. Sure there are errors that kill people unintentionally, but then there's a human choice to simply take the equipment out of service. E.g., an AED is mostly autonomous, but if a model of AED consistently fails in its diagnosis, humans can easily replace said AED with a different model. (You can't trust said AED to take itself out of service).

Airplanes - you still have humans "in the loop" and there have been many a time when said humans have to be told that some equipment can't be used in the way it was used. Again, the airplane doesn't takeoff, fly, and land without human intervention. In bad cases, the FAA can issue a mandatory airworthiness directive that says said plane cannot leave the ground without changes being made. In which case human pilots check for those changes before they decide to fly it. The airplane won't take off on its own.

Traffic control - again, humans in the loop. You'll get accidents and gridlock when lights fail, but the traffic light doesn't force you to hit the gas - you can decide that because of the mess, to simply stay put and not get involved.

Remember, in an autonomous system, you need a mechanism to determine if the system is functioning normally. Of course, said system cannot be a part of the autonomous system, because anomalous behavior may be missed (it's anomalous, so you can't even trust the system that's supposed to detect the behavior).

In all those cases, the monitoring system is external and can be made to halt a anomalous system - equipment can be put aside and not used, avoiding hazardous situations by disobeying, etc.

Sure, humans are very prone to failure, that's why we have computers which are far less prone to failure, But the fact that a computer is far less prone to making an error doesn't mean we have to trust it implicitly because we're more prone to making a mistake. it's why we don't trust computers to do everything for us - we expect things to work but when indications are that it doesn't, we have measures to try to prevent a situation from getting worse.

Re:By the same logic

[Dutch Gun]

Agreed. The authors set up a nearly impossibly complex ethical dilemma that would freeze even a human brain into probable inaction, let alone a computer one, and then claims "See? Because a computer can't guarantee the correct outcome, we can therefore never let a computer make that decision." It seems to be almost the very definition of a straw man to me.

The entire exercise seems to be a deliberate attempt to reach this conclusion, which they helpfully spell out in case anyone missed the not-so-subtle lead: "Robots should not be designed solely or primarily to kill or harm humans."

I'm in no hurry to turn loose an army of armed robots either, but saying that you can "prove" that an algorithm can't make a fuzzy decision 100% of the time? Well, yeah, no shit. A human sure as hell can't either. But what if the computer can do it far more accurately in 99% of the cases, because it doesn't have all those pesky "I'm fearing for my life and hopped up on adrenaline so I'm going to shoot now and think later" reflexes of a human?

The human brain is not a Turing machine

[Anonymous Coward]

Exhibit A, the human skull: Not enough room for an infinite tape.

Impossible to build purely evil robots?

[Galaga88]

Presuming that this proof reached via impressively tortured logic does have merit: Does it mean that it is also impossible to build a purely evil robot that would always kill maliciously?

Re:Impossible to build purely evil robots?

[phantomfive]

The proof essentially involves saying, "there is no way to build an automated process that will determine that the source code of the robot works correctly. Therefore it is impossible to build source code of the robot correctly." By requiring that the code be tested automatically, they can invoke the halting problem.

Of course, there are ways to make sure it will halt, you can show that a program is making progress towards its goal at each step; in other words a huge subset of programs will indeed halt.

You may need to manually test or formally prove that the code works by hand, instead of using an automated code prover to show that your code works. Really, I wonder what journal publishes this stuff, it's more like a joke paper. Oh, Arxiv.

It's just wrong

[Anonymous Coward]

Englert and co say a robot can never solve this conundrum because of the halting problem. This is the problem of determining whether an arbitrary computer program, once started, will ever finish running or whether it will continue forever.

This is simply incorrect. The conundrum (RTFA for details) doesn't involve an arbitrary computer program. It involves a computer program that performs a specific known function. It is perfectly possible for an automated system to verify any reasonable implementation of the known function against the specification. If such a system fails it is because byzantine coding practices have been used - in which case, guilt can be assumed. The Halting problem doesn't apply unless you HAVE to get a correct answer for ALL programs. In this case you just have to get a correct answer for reasonable programs.

Re:It's just wrong

[sexconker]

This.
The halting problem is about determining whether a general program will terminate or not.
When you already have a defined program (and machine in this case) in front of you for review, then you can determine whether or not it will halt, whether or not it works, and whether or not it is evil. You have to actually test and inspect it, though. You can't run it through a pre-built automated test and be sure. That is the only consequence of the halting problem.

The authors make the following leaps:

We can't know if a program will ever terminate.
(False - you can, you just can't do so with a general algorithm written before the program.)

Therefore we can't know all of the things a program can do.
(False - you know all inputs and outputs and their ranges. You can't know all possible sequences if the program runs forever, but you can know each individual state.)

Therefore we can't trust that a program isn't malicious.
(False - you can trust it to a degree of confidence based on the completeness of your testing.)

Therefore programs shouldn't be given the capability to do harmful things.
(Stupid - this isn't a logical conclusion. What if we want to build malicious programs? We can and do already. Further, if our goal is to not create malicious programs, then simply having a confidence level greater than when giving humans the same capabilities, it's already an improvement.)

Bad Headline as Usual

[Jaime2]

What the paper said is that computers can't provably always make the right choice. Neither can we. I'll bet computers are capable of doing a lot better than humans, especially given the rate of the increase in the number of things a computer can do compared to the rate that humans are (aren't) gaining new abilities.

Re:only incorrectly device to kill humans?

[Anonymous Coward]

Stop picking on systemd! Just give it a chance!

Silly article, waste of time

[raymorris]

What a silly article, and a waste of three minutes to read it. What they actually showed is that it's possible to construct a scenario in which it's impossible to know for certain what the best decision is, due to lack of information.

That fact, and their argument, is true whether it's AI making the decision or a human. Sometimes you can't know the outcome of your decisions. So what, decisions still must be made, and can be made.

Their logic also falls down completely because the logic is basically:

a) It's possible to imagine one scenario involving life and death scenario in which you can't be sure of the outcome.
b) Therefore, no life-and-death decisions can be made.
(wrong, a) just means that _some_ decisions are hard to make, not that _all_ decisions are impossible to make).

Note the exact same logic is true without the "life-and-death" qualifier:
a) In some situations, you don't know what the outcome of the decision will be.
b) Therefore, no decisions can be made (/correctly).

Again, a) applies to some, not to all. Secondly, just because you can't prove ahead of time which decision will have the best outcome doesn't mean you make make a decision, and even know that that is the correct decision. An example:

I offer to make a bet with you regarding the winner of this weekend's football game.
I say you have to give me a 100 point spread, meaning your team has to win by at least 100 points or else you have to pay me.
It's an even-money bet.

The right decision is to not make the bet, because you'd almost surely lose. Sure, it's _possible_ that your team might win by 150 points, so it's _possible_ that taking the bet would have the best outcome. That's a very unlikely outcome, though, so the correct decision _right_now_ is to decline the bet. What happens later, when the game is played, has no effect on what the correct decision was today.

National Robots Association

[c]

"Robots don't kill people. Robot programmers kill people."

Re:only incorrectly device to kill humans?

[Jason Levine]

If you have a problem with your Killbot's operation, please call 1-800-KILL-HMNS and we'll send a customer service Killbot to execute your trouble ticket right away. We won't rest until there are no bug reports submitted by humans.