Formalizing Foundations: Viruses (1936-1948) Part 2

Let’s continue where we left of, in part one of the post we looked at the basic definitions of some of the constructs we will use such as: Turing Machines, Recursive and Recursively Enumerable functions, Universal Turing Machine etc. Continuing the topic:

Let’s assume that there exists a relation R(e, <x0,x1,x2….xn>,y) which holds if and only if  e is a natural number that depicts the encoding of a Turing Machine M, and y is a sequence of configurations of the machine M with <x0,x1,x2,…xn> on the input tape initially.  Then there exists a recursive function U such that  whenever R(e, <x0,x1,x2,…xn>, y) holds, then U(y) is the output value of the computation, provided the machine M halts.Thus the relation R can be said to be “decidable” which consequently means U is a recursive function. Hence we can consider the following:

φe(x0,x1,x2,….,xn) = U(y*)

where the φ would be the k-place function for any k , where y* denotes the smallest y (when it exists) which implies that the relation R would be true. Looking at the theorem from Kleene:

Theorem: The (k+1)-place partial function whose value at (e, x0, x1, x2,…..xn) is  φe(x0,x1,x2,….,xn) is recursive. 2. For each e, the k-place partial function φe is recursive. 3. Every k-place recursive partial function equals φe for some e.

The number e is called the index of the function φ. What is implied in the above statement (the question we are answering) is that the encoding process being recursive, the problem of effective computation can be looked at in the context of the Universal Turing Machine without worrying about the specifics of a given function.Thus taking a few moments to interpret the results of the above theorem we can say that a k-place function φ is recursive ie. effectively computable, only if it has an index e, in other words, this mirrors the statement that recursive functions are only those that have Turing Machines that eventually halts on given input, since e here is nothing but a natural number that describes a Turing Machine.Given that the k-place function φe is recursive, it is intuitively obvious that the (k+1)-place partial function (e, x0,x1,x2,….xn) is also recursive, this implies that as long as there exists a Turing Machine to effectively compute the solution to a problem, the Universal Turing Machine will effectively implement the specified Turing Machine and compute the solution to the problem. To summarize, a universal function (UTM) has a program p0 and φp0(x)  computes φp(z) where x = <p,z> is the data (to the UTM) consisting of the program p (description of the Turing Machine) and input data z. Another important thing to notice here is that data that represents a program and data that represents input data have only semantic differences (something that is echoed in von Neumann’s architecture).


Halting Problem and Decidability

Though the above result is interesting in itself, to further our study of viruses we still have one important question to be answered, we still haven’t formally stated any solution to deduce whether a program will halt, that is to say whether a given problem will be effectively computable. Though the definition of a computable function is pretty clear, the problem we face can be explained by the following scenario: Let us assume that a Turing Machine M receives an input x, and after a million steps the machine still hasn’t halted. The question that arises is whether the machine will halt given another 1000 steps or maybe perhaps a million more, or whether the machine will never halt. So the question then becomes that of having a program/ function that can decide whether a function can be effectively computed.

Let us define 2 symbols φp(x)↑ to represent that the calculation is undefined (program p applied to input x does not halt ever) and φp(x)↓ to represent that the calculation is defined (program p applied to inputs x halts). Now, we define a set H such that

H = {p;x|φp(x)↓}, i.e. a set of all programs that halt when given an arbitrary input x. We can then say that the set H is recursively enumerable. This is obvious, the characteristic function is that the program halts, if the program halts then it is a de facto element of the set. The amazing thing is that no answer can be given to the contrary. Before we prove that in a few minutes let’s assume the previous statement is true. What does it imply? It implies that there CAN BE NO program that always halts and returns true if φp(x)↓ and false if φp(x)↑. The proof of this statement is one of contradiction (and amusing). Assume that we have a program P which takes as inputs another program and the inputs to the program. Now lets us define a program Test that has the following definition:

Test(X) { a: if P(X,X) then goto a else halt}

Notice that if P says that, the program X halts when presented an encoded version (Godel Number) of itself as an argument, the function Test will never halt. Now consider what happens when X is the program Test itself. If P(Test, Test) says Test halts then Test never halts and if P(Test, Test) says Test never halts then Test halts. Hence by contradiction we have been forced to negate our only assumption, that there exists a function that can decide whether a given function is computable or not.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s