In computer science, termination analysis is a program analysis technique which attempts to determine whether the evaluation of a given expression will definitely terminate. The study of this problem has led to several interesting results in computer science and mathematics; for example the solution to the Halting problem. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... An expression in a programming language is a combination of values and functions or procedures, interpreted according to the particular rules of precedence and of association for a particular programming language, which computes and then returns another value. ... For other meanings of mathematics or math, see mathematics (disambiguation). ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and its initial input, determine whether the program, when executed on this input, ever halts (completes). ...

Some expressions are trivially observed to terminate, like "2 * 4"; a sequence of terminating expressions will also terminate. Loops may or may not terminate, as they can be run repeatedly; however loops implemented using a counter variable as typically found in data processing algorithms will usually terminate, demonstrated by the pseudocode example below: In computer science and in computer programming, statements in pseudocode or in a program are normally obeyed one after the other in the order in which they are written (sequential flow of control). ... In general, a counter is a device which stores (and sometimes displays) the number of times a particular event or process has occurred often in relationship to a clock signal. ... Data processing is any computer process that converts data into information. ... Flowcharts are often used to graphically represent algorithms. ... Pseudocodes can refer to the technique of using short codes, especially within the language with singular name Short Code, which was the first ever language developed for an electronic computing device. ...

 i := 1 loop until i = SIZE_OF_DATA process_data(data[i])) //process the data chunk at position i i := i + 1 //move to the next chunk of data to be processed 

If the value of SIZE_OF_DATA is fixed and finite, the loop will eventually terminate, assuming process_data terminates too.

Some loops can be shown to always terminate or never terminate, through human inspection. For example, even a non-programmer should see that, in theory, the following never stops (but it may halt on physical machines due to arithmetic overflow): A programmer or software developer is someone who programs computers, that is, one who writes computer software. ... The term arithmetic overflow or simply overflow has the following meanings. ...

 i := 1 loop until i = 0 i := i + 1 

There is, however, no general procedure for determining whether an expression involving looping instructions will halt, even when humans are tasked with the inspection. To see why, we can construct a simple loop to verify Goldbach's Conjecture as follows: In mathematics, Goldbachs conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. ...

 t := 4 loop if there does not exist x, y where is_prime(x) and is_prime(y) and x + y = t //counterexample found print "Goldbach's Conjecture is false for the number " + t exit loop otherwise t := t + 2 continue loop 

To know whether this expression will halt, it is necessary to know whether Goldbach's Conjecture is true or false, which is still an unsolved mathematics problem.

Recursive functions and loops are equivalent in expression; any expression involving loops can be written using recursion, and vice versa. Thus the termination of recursive expressions are also undecidable in general. Most recursive expressions found in common usage (ie. not pathological) can be shown to terminate through various means, usually depending on the definition of the expression itself. As an example, the function argument in the recursive expression for the factorial function below will always decrease by 1; from the well-ordering property on natural numbers, the argument will eventually reach 1 and the recursion will terminate. It has been suggested that this article or section be merged into computable function. ... In mathematics, a pathological example is one whose properties are (or should be considered) untypically bad. ... Function arguments are values or references to language constructs (like variables) which are passed to a function. ... In mathematics, the factorial of a natural number n is the product of all positive integers less than or equal to n. ... In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ... In mathematics, a natural number is either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). The former definition is generally used in number theory, while the latter is preferred in set theory and computer science. ...

 function factorial (argument as natural number) if argument = 0 or 1 return 1 otherwise return argument * factorial(argument - 1)