| Machine That Always Halts |
Article Index for Machine |
Website Links For Machine |
Information AboutMachine That Always Halts |
| CATEGORIES ABOUT MACHINE THAT ALWAYS HALTS | |
| computational models | |
| theory of computation | |
|
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 Language s. It is important to note, however, that, due to the Halting Problem , determining whether an arbitrary Turing machine always halts is Undecidable - there is no algorithm for it. The set of all machines that always halt is only Recursively Enumerable . In practice, it is possible to construct a machine that always halts, and yet computes many functions of interest, by restricting its Flow Control capabilities so that no program will ever cause the machine to enter an Infinite Loop . As a trivial example, a finitary Decision Tree can contain no loops whatsoever, so it naturally always halts. It is not required that the machine be entirely free of looping capabilities, however. 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-{GOTO} of Brainerd and Landweber (1974). We can further define a programming language in which we can ensure that even more sophisticated functions always halt. For example, the Ackermann Function , which is not primitive recursive, nevertheless always halts, and we can guarantee that property by casting it as a Term Rewriting system with a Reduction Ordering on its arguments (Ohlebusch, 2002, pp.67). This is similar to using Mathematical Induction to prove that a Recursive Function always reaches its base case. Note, however, that there will ''always'' be programs that always halt that are not expressible in such restricted models. In fact, the following theorem shows that machines that always halt are strictly less powerful than Turing machines: There are (Turing-)computable total functions that are not computable by any machine that always halts. ''Proof:'' The proof parallels Theorem 2.3 of Brainerd and Landweber (1974) for the PL-{GOTO} language, and proceeds by a Diagonal Argument . Let ''F'' be the set of all functions computable by a machine that always halts. These functions are Total since the machine halts on any input. As usual, and without loss of generality, we can take these functions to map naturals to naturals. Our goal is to find a computable total function ''g(n)'', with , that is not in ''F''. By the definition of ''F'', for every function ''f'' in ''F'' there is a machine description (or a program) ''d'' that computes ''f'' upon execution. We denote the execution of ''d'' by double square brackets, thus ''d'' ''(n) = f(n)''. Since any description makes the machine halt at some point, it is not hard to see that the set of machine descriptions ''D'' that lead to total functions is Effectively Enumerable . Let ''dn = d(n)'' be an effective procedure for enumerating ''D'' as {''d0'', ''d1'', ''d2'', ...}. It follows that ''F'' is also effectively enumerable with enumeration { ''d0'' , ''d1'' , ''d2'' , ...}. Now define the Diagonal function ''g(n)='' ''dn'' ''(n)'' + 1 (other functions can be constructed by replacing 1 by 2, 3, etc). This function is effectively computable, since both ''dn=d(n)'' and ''dn'' ''(n)'' are effectively computable. It is also total since ''dn'' ''(n)'' halts for any ''n''. However, by construction, ''g'' is different from every member of ''F''. Therefore, ''g'' is total and effectively computable, but not computable by a machine that always halts. Alternatively, by the Church-Turing Thesis , "effectively computable" can be replaced by "Turing machine computable", ''q.e.d.'' BIBLIOGRAPHY
|
|
|