Dont copy paste from the internet please Do an online search

Don\'t copy paste from the internet, please.

Do an online search for the Halting Problem and explain in your own words why this is even today an important and interesting problem in computer science. Cite your reference. No more than one page.

Solution

Halting problem:

-->The halting problem is a critical problem in computability theory. It is the theoretical problem of determining
whether a computer program will halt or loop forever on a given input.
-->One input that might be of interest would be the program itself.
Remember that the program is, at some level, just a bunch of data.
-->In this case, the program is some characters that decribe instructions for doing something. There\'s nothing wrong
with running a program and passing in the program itself as input.

example:

infinite loop in a small program that detects infinite loops! Here it is:

bool peter( char * program ) {
if( stops_on_self( program ) ) {
while( 1 ) {}
return FALSE;
} else {
return TRUE;
}
}

it just passes the program twice to would_it_stop - once as instructions, and once as input.
peter is just slightly more complicated. Given a program program, if stops_on_self is true, bobs_yer_uncle goes into an infinite loop.
Otherwise, it stops and returns TRUE.

But here\'s the paradox. What happens when I try bobs_yer_uncle on itself? Well, clearly one of two things can happen: either it runs forever,
or it stops and returns TRUE, depending on whether the call to stops_on_self returns TRUE or FALSE.

1)If peter( peter ) goes into an infinite loop, it is because stops_on_self( peter ) returned TRUE, which means that would_it_stop( peter, peter ) returned TRUE.
But this means that bobs_yer_uncle would stop when fed itself as input! This contradicts the assumption that it goes into an infinite loop.

2)If peter(peter ) stops and returns TRUE, it\'s because stops_on_self( peter ) returned FALSE, which means that would_it_stop(peter,perer) returned FALSE.
But this means that bobs_yer_uncle would run forever when fed itself as input! This contradicts the assumption that it terminates.

We have therefore led ourselves to a contradiction. bobs_yer_uncle stops if and only if it runs forever. Since this is impossible, one of our assumptions must be invalid.
By tracing our reasoning backwards, we find that it is therefore impossible to have written would_it_stop in the first place. In other words, the halting problem is undecidable.

There are countless other undecidable problems, which can often be expressed in terms of some simple question about a computer program. For example:
Will the program ever print out a 5?
Will the program ever execute line 26?

It turns out that these sorts of problems are all equivalent to the halting problem, in the sense that given a solution to one of them, you could write a solution to any of the other ones.
The reasons why that is possible are interesting.