Re: Halting Problem

robertwessel2@xxxxxxxxx wrote:

I think where you're going wrong (and it's a common error), is that
you're assuming that the halting problem is of any particular interest
to computing.

Excellent, excellent point. I debated whether or not to even bring it
up... The halting problem does have a very important application to
computing: Artificial intelligence, especially "seed AI," as some people
call it. In one way or another, this usually involves getting a computer
to program itself. Knowing whether a particular program halts is very
important, and being able to figure this out quickly is very helpful.

As explained here, the answer is that it can't be done for arbitrary
programs. But it can be done (reasonably efficiently, even) given certain
restrictions, and those restrictions are actually very loose.

Your (and Turing's) excellent point about completeness may have far-
reaching consequenses in terms of what AI can and can't do.
.

Relevant Pages