基于扩展通用图灵机的计算机病毒传染模型

A Computer Viruses' Infection Model Based on an Expanded Universal Turing Machine

在计算机基础理论模型———图灵机模型的基础上 ,提出了一种扩展的通用图灵机 (EUTM)模型 ,这种模型突出了计算机病毒的传染特性 ,极大地简化了计算机病毒传染的形式描述 ,并根据EUTM模型给出了计算机病毒的形式定义 ,形式化描述了计算机病毒在单机和多机环境下的传染 最后指出了FredCohen关于病毒检测不可判定性定理证明的不足 。

A model of an expanded universal Turing machine(EUTM) based on the model of Turing machine is proposed,which is the basic theory of computer, and the infection of computer viruses is formally described according to the EUTM model in the circumstance of a single machine and multi machine environment The procedure or virus is considered as the code of Turing machine, and the code of Turing machine is regarded as the input of the EUTM model EUTM reads the inputs,copies the inputs on the storage's tape, and at the same time writes the results on the output's tape A procedure is a virus iff ① ‖Φ v(p)‖ =‖v‖‖x‖;② 〈Φ v(p)〉〈v〉 or 〈Φ v(p)〉〈V(v)〉;③ Φ v(p) has the properties of procedure v , that is to say, Φ Φ(p′) satisfies the condition 1 and 2 The deficiencies of Fred Cohen's proof about virus undetectability theory are pointed out And the theory of virus undetectability is proved based on the EUTM model The model of the EUTM simplifies the formal description of computer viruses' infection and emphasizes the basic property of computer viruses