The concept of viruses is not something that was brought about after advances in computers. The idea of self-reproducing machines was what lead to its eventual form in code that of us identify with today on hearing the word virus with respect to software or technology. The following series of posts on Formalizing Foundations is intended to trace the fascinating study about self-reproducing machines that lead to the eventual discovery of computer viruses in their current and ever-evolving form.

This post may not initially make direct sense as to how it contributed to the formalization of viruses. The first topic we will look at is Turing Machines, since stripped down viruses are nothing but series of bits that makes sense to a machine (a program), and the study of programs and computing machines truly began with Turing Machines. What one needs to know is that the one and only characteristic for a program to be classified as a virus is the ability to self-reproduce. Assuming we have an abstraction for self-reproduction in the form of some function f, what we need to find out is whether it is physically possible to construct a machine that can compute the above. The early researchers did not consider this problem directly. This was looked at by von Neumann in 1948 during his search for self-generating automata, which is when it was proved possible.

### Turing Machine: Basics

A normal Turing machine consists of a infinite tape, a tape head and a finite control. The function of the finite control is two fold: 1) Put the control unit (finite control + tape head) in a new state. 2) Write a symbol in the tape square currently scanned by the read/write head and move the tape head one tape square to the left or right. Matematically a Turing machine is defined as the quintuple: (K, ∑, δ, s, H) where:

- K = finite set of states that the Turing Machine can attain.
- Σ = alphabet also contain the blank space symbol and the left end symbol
- δ = transition function defined from (K-H) * Σ to K * (Σ U {←, →})
- s ∈ K = initial state of the Turing Machine
- H ⊆ K = set of halting states

For the purposes of future study we will consider that the alphabet consists of only 0 and 1. This will directly prove possibility in programmatic form in the end and we can do this without loss of generality since generalization to a larger set is always possible with the proper encoding function. For example consider Godel numbers: given a set of numbers <x0, x1, x2, ……,xn>, we can uniquely encode this set by representing it by a simple number S where S = (p0^x0)(p1^x1)(p2^x2)…..(pn^xn) where pi is a prime number. Assuming the information is encoded using a suitable example as shown, we can represent the configuration of the Turing Machine at any instant by a triplet containing the current state of the Turing Machine, the tape contents and the symbol on the currently scanned cell. The question that now arises is whether all possible functions can be described by such a machine. To answer that question, we need to understand what recursive functions are.

### Recursive Functions

Let M be a Turing Machine and ∑ be an alphabet. Now let us assume that a string w ∈ ∑* is given as input to the machine and the machine halts after processing the given input. Then the contents of the tape after the machine halts is the output after computation. Let us name the output of the machine, i.e. the tape content after processing, y = M(w). Point to be noted: M(w) is defined only if the turing machine halts on input w.

Now let ƒ be any function from ∑* to ∑*. We call the function ƒ “recursive” if ∀w ∈ ∑*, M(w) = ƒ(w), i.e. for all w element of ∑* given as input, the machine M eventually halts and when it does the tape contents represent ƒ(w). We also say that the function ƒ is “computable” by turing machine M. As already seen, the ∑ can be restricted to {0,1} since any number can be represented as a linear combination of the powers of another number, and representing the data in numerical form is just a matter of syntax.

We can also generalize the function to be a k-place function for our easy. K-place functions are functions ƒ: N^k → N . A relation R is said to be “decidable” if there exists an effective procedure that , given any object x, enables to verify if R(x) is true or not. R is decidable only if its characteristic function is recursive, that is effectively computable. The above definition should not be confusing as the words “decidable”, “recursive” and “computable” are interchangeable but mean the same, as do the words “semi-decidable” and “recursively enumerable”. We now define “recursively enumerable” or “semi-decidable” relations as those relations for which the turing machine halts only if the input is part of the relation. The turing machine does not halt when the input does not belong to the set. Hence all recursive functions/languages/sets are recursively enumerable but not vice-versa.

### Universal Turing Machines

The previously defined Turing Machine is not effectively able to represent a computational machine (computer) because a computer can solve a variety of problems while a Turing Machine can solve only one problem. Hence the design of a more general concept, that of an “Universal Turing Machine” (UTM). A UTM is defined as a Turing Machine which accepts as its input a description of another Turing machine, denoted M, concatenated with the input x for the Turing machine defined. We use the symbol U to represent the action of the UTM. Therefore, U(M,x) = M(x)

To see how these concepts are brought together, read part 2 of this post here.

Sources:

Computer Viruses: From Theory to Application by Eric Filiol

Elements of the Theory of Computation by Lewis and Papadimitriou

Malware, Rootkits and Botnets by Christopher C. Elisan