Infinite loop: an endless sequence of repetitions of a component in a computer program caused by a programming error (bug) or input data error. An infinite ►recursion is a type of infinite loop.
In pseudocode an infinite recursive loop looks roughly like this:
function Endless (data):
Do (data);
Endless (data);
return;
This function keeps calling itself but never reaches its terminal base line, the return line. Infinite loops cause the program to crash due to the fact that it is unable to escape the looping component; as a result, the computer is no longer able to react to input data. Pretty much every PC owner should be familiar with this effect: The program 'freezes' and must be terminated the hard way by means of a reset button, Vulcan nerve pinch, or task manager. It is not possible by means of analysis alone — that is, without executing the actual program — to generally determine whether the program will terminate correctly with certain input data or whether it is actually frozen. This halting problem was proven in 1936 by the British mathematician Alan Turing.
'Errors don't exist' Does Not Exist
Here is the proof (basic programming knowledge makes it easier to follow): Let as assume a function Finite that can reliably determine whether a given program with given input data will perform an infinite loop or terminate correctly. In pseudocode the function would be defined as follows:
function Finite (program, data):
if
('program' ends upon input of 'data')
then
return YES;
else return NO;
Of course, Finite itself must not contain an infinite loop but always terminate reliably even if the tested program does not. We now define a recursive function TestMe, which is called up by Finite:
function TestMe (program):
if (Finite
(program, programm))
then TestMe (program);
This somewhat nasty function is terminated only if program is not, that is to say, if the latter calls itself as input data. Otherwise TestMe enters into an infinite recursion: The function keeps calling itself so that it never produces a terminal line. But if we apply the function TestMe to itself as program we obtain a logical contradiction:
TestMe (TestMe);
This function call ends precisely if it does not end. Consequently, a function such as Finite cannot exist. For programmers this means that they can never prove that a program they delivered is free of errors. By itself, this does not sound very exciting (except, perhaps, for programmers). In 1936, however, the proof shook up our mathematical worldview even though at the time there were not as yet any computers to be programmed. Turing himself applied the proof only to a hypothetical computer, a so-called Turing machine. But the proof does have the more general implication that some problems are unsolvable in principle within the formalism of mathematics — an implication that Kurt Gödel had already proven six years earlier in the context of his ►incompleteness theorem.
Is God Able to Program a Bug-Free Software?
Puzzles such as the halting problem and the incompleteness theorem also have philosophical and religious implications. In particular, it challenges the thesis of God's ►omniscience: If it is impossible in principle to determine a system to be bugless, then even ►God would be unable to know whether a program designed by Him has a bug or not. The further question of whether this is what accounts for certain flaws in the creation of our world, however, probably also belongs into the category of unsolvable problems.
* [Ctrl]-[Alt]-[Del]
Links Related to the Topic
■ Limits of Decidability
■ Basic Linguistics
■ Alan Turing