Machine That Always Halts

All Updates

In computability theory, a **machine that always halts**—also called a **decider** (Sipser, 1996) or a **total Turing machine** (Kozen, 1997)—is a Turing machine that halts for every input.

Because it always halts, the machine is able to*decide* whether a given string is a member of a formal language. The class of languages which can be decided by such machines is exactly the set of recursive languages. However, due to the Halting Problem, determining whether an arbitrary Turing machine halts on an arbitrary input is itself an undecidable decision problem.

## Functions computable by total Turing machines

In practice, many functions of interest are computable by machines that always halt. A machine that uses only finite memory on any particular input can be forced to halt for every input by restricting its flow control capabilities so that no input will ever cause the machine to enter an infinite loop. As a trivial example, a machine implementing a finitary decision tree will always halt.

It is not required that the machine be entirely free of looping capabilities, however, to guarantee halting. If we restrict loops to be of a predictably finite size (not unlike the FOR loop in BASIC), we can express all of the primitive recursive functions (Meyer and Ritchie, 1967). An example of such a machine is provided by the toy programming language PL- of Brainerd and Landweber (1974).

We can further define a programming language in which we can ensure that even more sophisticated functions...

Read More

Because it always halts, the machine is able to

It is not required that the machine be entirely free of looping capabilities, however, to guarantee halting. If we restrict loops to be of a predictably finite size (not unlike the FOR loop in BASIC), we can express all of the primitive recursive functions (Meyer and Ritchie, 1967). An example of such a machine is provided by the toy programming language PL- of Brainerd and Landweber (1974).

We can further define a programming language in which we can ensure that even more sophisticated functions...

Read More

No messages found

about this page

for companies, colleges, celebrities or anything you like.Get updates on MyPage.

Create a new Page