4
$\begingroup$

I am writing a story for school about a human level AI. I want to have him be able to optimize and improve upon its own AI, but does this breach the Halting Problem? Thanks in advance.

$\endgroup$
2
$\begingroup$

Remember, the AI doesn't want to halt! If it halted, it would be dead!

There are halting problems for the AI itself - in that as it attempts to optimise and self-improve, if it makes a mistake (puts in a bug) it may actually 'lobotimise itself' or do more damage than good. This is only true if it doesn't have the ability to fork or clone. But it's not just the halting problem - it's the general class of optimisation problems and, mainly, a decision problem (how do I know that this specific revision is better than the current revision?). Halting problems are a subset of decision problems.

If the AI can fork, then it can test multiple hypotheses without much damage to itself (although there are resource costs), and as long as it has some ability to measure self-improvement (decision problem: How can I measure if this specific hypothesis is better than the current one), and know what self-improvement is (optimisation problem: what does 'self-improve' actually mean to the AI? More knowledge? Swifter reflexes? Better ability to problem solve? Can subsequently revised AI's change the definition? If so, how do I know I'm not heading down an optimising cul-de-sac?) then it can hand the 'reins over' to the best result(s).

This is (roughly) how Genetic Programming / Genetic Algorithms work, and it would most likely one of the central strategies for how an AI would self-optimise.

Philosophically, what does individuality mean to an AI? Spawning a million genetically related offspring, testing them, and then selecting the most optimal to carry on the next generation isn't really the behaviour of an individual so much as some sort of virtual community. But to risk operating directly on one's own brain is something that an AI would not choose to do, as it is so much more able to clone/fork and modify.

So halting problems are just one of the many pitfalls that the AI must have to contend with. They aren't the largest problem - and there are ways around it, such as just killing off possible mutation forks that don't resolve within some metric.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This was great! This solves so many problems and gives me a lot of ideas. $\endgroup$ – Sharp_ Apr 1 '17 at 17:04
12
$\begingroup$

No, it is not the Halting Problem. The halting problem is very specific and tied to the exacting specifications of the Turing machine.

The halting problem states that it is impossible to write a program which can determine if any other program will eventually halt or reach an infinite loop.

There could easily be an issue if the AI first had to prove that a change was an improvement before going forward with the change. Such a proof could easily require solving a halting problem for many definitions of "an improvement." However, the AI is under no such obligation. In fact, one of the major points of AIs is their ability to find solutions without needing to have hard proofs in place first, just as we can pioneer without proofs that our pioneering will eventually pay off.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Cort has the right idea here, and it is the fundamental problem of AI research -- how do you define when an AI has learned something well enough that it can now be on its own? Of course, that's the same problem we have with raising human children. Sometimes, the only way to learn is on-the-job training. ;-) $\endgroup$ – SRM Mar 31 '17 at 1:59
  • 1
    $\begingroup$ Also, the "problem" in the Halting Problem is the any part of "determine if any other program will eventually halt". For certain programs, it's trivially easy to tell if they halt or not. In fact, for most practical programs it should be possible to automatically determine if they halt. The Halting Problem only says you're not able to get 100% accuracy on the task. It says nothing about getting 99% accuracy and mislabeling 1%, or being perfectly accurate on 95% of the case and 5% of the time returning "not able to process". $\endgroup$ – R.M. Mar 31 '17 at 15:17
1
$\begingroup$

The halting problem is "whether the program will finish running or continue to run forever." (https://en.wikipedia.org/wiki/Halting_problem)

I think it could get to a point where it can't improve anymore (which would take a very long time). But, it would keep changing since, there is no way for it to tell if it has reached its max, so it would keep going and changing stuff. Like people don't know if they have made something the best it could be so they keep changing stuff (if you believe the human brain is a Turing machine since it's based on the same physics).

So, I don't think it will stop, it just might un-improve (not sure if that's a word) or just keep going up and down forever. This would make it not be a paradox since even if it's not effectively changing it is still changing which means it won't stop running.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.