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

第 卷 第 期 计 算 机 研 究与 发 展 ， 40 9 Vol .40 No .9 年 月 Se 2003 9 jOURNAL OF COMPUTER RESEARC~ AND DEVELOPMENT p . 2003 ############################################################### 基于扩展通用图灵机的计算机病毒传染模型 王 剑 唐朝京 张 权 张森强 刘 俭 （国防科学技术大学电子科学与工程学院 长沙 410073 ） （ ） xx Wangj ian!sina .com 摘 要 在计算机基础理论模型———图灵机模型的基础上，提出了一种扩展的通用图灵机（ ）模型，这种模型突出 EUTM 了计算机病毒的传染特性，极大地简化了计算机病毒传染的形式描述，并根据EUTM 模型给出了计算机病毒的形式定 义，形式化描述了计算机病毒在单机和多机环境下的传染. 最后指出了Fred Cohen 关于病毒检测不可判定性定理证明 的不足，并利用EUTM 模型证明了病毒检测不可判定性定理. 关键词 病毒传染模型；扩展通用图灵机；图灵机 中图法分类号 TP309 .5 ’ A Computer viruses Infection Model based on an expanded universal turing Machine ， ， ， ， WANG j ian TANG Chao-j ing Z~ANG @uan Z~ANG Sen-@iang and Liu j ian （ ， ， ） School o Electronic Science and En ineerin National uniOersit o De ense technolo Chan sha 410073 f g g y f f gy g （ ） Abstract A model of an expanded universal Turing machine EUTM based on the model of Turing ma- ， ， chine is ro osed Which is the basic theory of computer and the infection of computer viruses is formally p p described according to the EUTM model in the circumstance of a single machine and multi-machine envi- ， ronment . The procedure or virus is considered as the code of Turing m