
Ŀ
                                                                    
                        
                                    
                           
                                          
Ĵ
                                  5                           
ٰ



                             ६ 
               ஡ Halting Problem  ਭ.

                        2001, Sassa  ZF#5


                               祬 ?

                                                 Der Steine im Sumpf
                                                 Macht keine Ringe

                                                 (.:   
                                                   뢠 )

         ᬠਢ    ⥮६   (Fred
Cohen;  奭)   ⢮  ᮢ襭  ⨢:
ணࠬ,      ᬮ  _訡筮_  ।,  ࠦ  
ணࠬ - ᮬ   .   뫠 稢
 㤠 ᠬ ,  [1],   ⭮   Detection of Viruses:
⠬  ࠧ    ⮩ ஡.   ࠢ ⥫    
      (D.M.Chess) [2],  ⨢᭮ ᫥⥫ 
IBM,   த 㦤 ⥮६   (  ⮦  室  
뢮,    ;   室   ࠭祭,   
  ⠭).

           ᠬ  ⥮६,      ३  
஡ Halting Problem  ਭ (A.M.Turing),  ⪮ ᠭ
㤠      ࠧ⨫       ਫ ,  "設
ਭ".  ,        ⨬   ⥮᪨   ᫨⥫
ன⢮,    ४㥬      ६,    ࠧ த
⥭ ;  ࠧ ⮫쪮 ⥫ ।⠥ 㤮⮢  
ࠢ쭮    ।뫮    ⮩       
᪠   ࠬ᪨ 訡.

    ⨬ ,   ᪮ 襭 ⥮६ ,  訢
Halting  Problem,   ⥬ ᠬ 室 襭 ⥮६  ( 
᪠ 室    ⢫  (-⠪!)        
).

             室   ଠ쭮   ᠭ   ⬠
㭨ᠫ쭮  ⥪  ᮢ.    ⠪      뢠   
.      ஢࣠  ⥫⢮  ⥮६ ,  
  Halting Problem.  ⨬,    ⢮    㣨,
    㫨஢,  ⥮६,    -⠪  
⢮ ࠧ訬 ஡   ணࠬ⮢.


                                 쬠

                                            ...⠬ -ᢥ ࠪ,
                                            祫  ⠪ 㤮,
                                              頦 ; 㤠.

                                           .., ""

                                      (  㬠 "  "? ;-)

     ஬,      ⮫쪮  ⠫  㯫  ᢮
,     .   㢨   ᢥ⭮:
  ⠫    ,     ਤ㬠 㯥-  ᮢ.
⮬      㯥-  㦥  ,        100%
⮢୮  ࢮ  த  ⫨砫  ᥬ  :     ⨬
  "" ணࠬ;    ⨬     -
ᮢ.

    ᪨, ⨢      ।⠢   ணࠬ AV
⠪ ࠧ [2]:

    AV: if A(p) then heal, else exit.

      ⮫쪮 ⭠,     ଠ쭮  ᭨,
   砥.  ⠪,  ணࠬ AV -  ⠪ ணࠬ,  
뢠  㭪 䨪樨  ன 㣮  ணࠬ  p,
   㥬  ࠦ.  ᫨ 㭪 䨪樨 A()
頥,  ᪠,  true,    ,  ணࠬ p ࠦ (
⮬    㦭  뫥).  ᫨    㭪 A() 頥 -
㣮,   ,  ணࠬ p    祣  .
⢥,      heal        ।쭮  :  뤠
।०; , , 㤠 । ணࠬ p.

    ⠪, ᫨  㬠,  ,    魮,     ⨢   
ࠣ஢   ⠪ .

    祢  ⨢ -  A(p),   
ணࠬ  ࠦ  ⠫.

    , ᫨ ⪮,  ⠫ ⢥ত,     ந  ⠪
㭨ᠫ  䨪  A(p),        ,
     騥,     ⮬    ண  㣨
ணࠬ. 㬥⮬ 뫠 ᫥ ணࠬ P [2] ( [1],  ⠬ 
⠪ ⪮):

    P: if A(P) then exit, else spread.

     , ணࠬ 뢠 䨪  _ᠬ_ᥡ_,  
஢ ⨢!  ࠧ, ᪮ ⨢ AV ᯮ
筮   ,    ⢨  ४: ᫨ A(p) 
- 稭  ணࠬ  ࠦ,  ⨢
஡  뫥,    ६   ᠬ  ணࠬ P 
蠥  (ᥣ!  ᪮  㭪 A(p) 뢠  ⠭⮩,
P),   ⮬ ᮬ  .  ,  ᫨ 㭪 A(p) 뤠
न,   ணࠬ P   ࠦ,  ⨢ AV 
ந;   ६   ᠬ   ⠭ ࠧ!

    ⥫ ⥫,  ᮬ,  ᮣ,   ਭ樯쭮
  ⮨      ⮬,   A(p)  ᯮᮡ ⫨  ᮡ
砩 - "ࠧ㬥",  "ࠤ",  -   ⮬,    
  __ࠢ_⢥_!    ⮣    㦭 ,   
맢,  ⮡ ४஢ ᢮   ᮮ⢥⢨  樥
    consistent ⢥.  ,  ᫨ -  ⥫  
⨫ ⮣ ࠧ,   猪  ᥩ      㦥    窠
襭 ⮣ .        ᢮  
襭 ⮣,   ,  㯨.    砫  㪠    
, 쬠 ⨯, ⥮६; ࠪ᪨ !

    ६   室    ﭨ  ⮩ 㪨  ⥮६
Halting Problem ਭ.  ⬥砥, ਬ,   ⭮ ᥤ
 ஬. ⢥,   ⮫㫮     ᮢ㯫
஡  .

     ஡ Halting Problem (,     ⭮  ᪮
ந襭 ⮣ ନ;      ᥩ  ⠭ ᭮) 
 祬.  ⠪,  㬥 ⠢ ணࠬ  設 ਭ (; 
  殮묨 横 ;-).    㧭,   
᪠.  , , ᫨  ணࠬ   ? ,
᫨      ᪮ 横  - 稭 (,  訡 
ணࠬ!)?    ᭨    ᪠.  祬,  
㧭  _⮫쪮_  ᪠.  ᪮  ணࠬ ࠡ⠥,   
 ᪠,     .        .
    ⮫쪮    訬,    ᫠,     室 
㯨?    ࠧ,  ⮫쪮  ஠஢      ᪠,
筠    .    ஡ 騥  ஢ 
  ਭ " 塞 ᫠",  ᪠஢  ࠭
ன  뫨 㯭   ୥ [3] (-!..  ⥯  㦥 
ᯮ  ࠭?!).

    , 祫 ᢮⢥ 訡 (⮬,  ᮡ⢥,  
⨬ ,    ᭥  ணࠬ), ⮬    
  ஢ન    祫:  ⠪       ᪮筮   
ਡ  ᮢ襭 ணࠬ,     㢥७,
 ஢७  "  ".   ਭ    
   ᠬ :    訡筮 筠;   ᪠ 筮,
筠  ணࠬ.   㪢쭮 "१  "  ,  
⠪  ணࠬ    .  ᪮  ⢮
⠪ ணࠬ P,    㤥    ᮢ襭  ⨢
ᢨ:

    P: if H(P) then not_dead_which_eternal_lies, else exit.

     ,  ᫨      䨪樨  頥 true
(᪠,   ਭ  諠        ⢥)    
ணࠬ,    頥      祭  ⮩ ணࠬ,  
ணࠬ 室   横. 祬? Just for the heck of it! 
᫨  H(p)  頥  -  㣮,    砥,    ணࠬ
᪮筠,   ணࠬ    蠥.  ,    
ணࠬ  HD,      ᭮ H(p) 㤥 ,  筠 
 ணࠬ,   ⮢୮  100%.  祭  짮⥫
类 祣  ⠥,  ஢ ᢮  .

              ⠭   ᬠਢ     ஢থ  ⮣
⥫⢠.    ⠥  ᪠  ⠪      ᮢ६
஢,  ॡ ᮢ襭⢮  . ᫥ ⮣
 ⠭ ⢥ত,  ⥫⢮   ୮, । 
஢থ  ,    ⥫  䨫᪮ ᮫
(᫨ ਤ  #-)  ९ ୮  㬮祭 
室 ᮢ襭⢮ .


                            १ ᢥ

                                                   ... - !
                                              .ਬ,  ஫ ;-)

     ⪨    .  ⫮     .  襭 ᥫ᪨
ᮢ - .

    襭 1.

    ࢮ,  ᪮稫   - 稥  筮.  ७
ਭ᫮    ࢮ  襭:     UNIX  ⠪ ⥫쭠
㭪 - fork().  ਬ⥫쭮      ,      ᮧ  
뭥譥    ࠧ楩  -⢥ :  頥
㭪樥 १.  ᫥ 믮 ⮩ 㭪樨   
  -    ⮬  -  த騥  믮    窨
    㭪樨.    ⮬  த⥫᪨       PID
஦    -  㫥 祭,  -  ஦ 
      १  믮  㭪樨.  ᫨    
ࠡ뢠 頥 祭,   ⠭ 묨.

    if (fork()){
    //...   믮 ⮫쪮 த⥫᪨ ᮬ
    }else{
    //...   믮 ⮫쪮 ஦ ᮬ
    }

    ⨭ 1. ਬ   ࠧ稥 ᮢ


    fork();
    // ...   믮  ᠬ

    ⨭ 2. ਬ   묨 ᠬ; ⮬ 

    ⠪,  窥 ⬠ H(p),    ।,  ணࠬ p -
"ࠧ㬥",  㦭 ᮧ  ⮬,   ᤥ  ⠪,  ⮡
  ⮬    True,    㣮  - False.   ⨢稢
ணࠬ P 饯  ,         ,  
㣠 - ३   横.  䨪 ⮦ ࠧ  ᢮
.   ᪮     㤥 "ணࠬ P  ᭥",
  㬥஢ "⢥" ⢥  ⢥न⥫ ⢥,
 ⮢୮ ᯮ  㬥.

    筮,  室  ।,   ணࠬ P    ᬮ
㦨      㣨  ﬨ (     ⮩
  UNIX).    ⠭  ⮣   ⮩  稭,  
H(p) 祭    㫨஢ ⮪ 饭,  㤨
㦭    ணࠬ  P          ⪥,   ᫨   
⨢稢 ( ,  ਭ樯 __     ⮪, 
㦭 ᯥ᪮ ᫮).   樨 ⮪ -    㣠
⥬.  ,    ᪠  ஡  "   ࠢ ⢥
" (頥  ⥫        ࠧ;        
୥) 襭.


    祭  襭 1.

     ⢥ - " ,  "!

    襭 2.

     fork()  맢 exit().  ⠪ ࠧ ஡ 襭
᭮.   ணࠬ   P,      ࠭   ⠫  ࠧ㬥,
⮬᪨ ⠭ 筮.  䨪  ⥯  뤠
ᮮ饭 "ணࠬ P 筠" (१㬯  :-), 
䨪,    _᫨_  (,      ⠪   ,      
⥫    襣  襭)  㤥  祭 ⢥ True,  
뤠 ", 뢠, ணࠬ P ᪮筠!".


    祭 1  襭 2.

 :   ⠭ ⢥ ⥬,     :-)

    祭 2  襭 2.

     ࠪ⨪        ,  易    맮
exit().  ᪮    API,      (?)  墠  (,  
DOS-Windows  -  筮;    UNIX  -  ᨬ   ਢ).   _᫨_
 墠,     ᪠ ॠ 室 ᮡ⨩  
ணࠬ P.  ,  ⥯ ⥮ਥ 㫮 ⠭.

                            䨪 

    ᬮਬ ।    ४⨢,    㦭  
設 ਭ.      뭥譨 ॠ樨 ஢!

    ᪮    ⮬,   筮 ᫮ ﭨ, 
    । ࠢ 室 (_ணࠬ_),   
⢮ ⠪ ⠡  室,          ப  
,  ஬  ,  ।  ᠬ  ணࠬ    ﭨ
⠭,   ⮬  ⭮ 㭪樨 H(p)  ࠭  (  ⠯  
ࠧࠡ⪨).   ⮬   ⠥   ᪮쪮   :   ࠧ   H(p)
஢ ⠡ 室,    ஢    ⠪
ࠧ,   ⮡    ந쭠  ணࠬ  P,      ⥪  HD,
⠭ ࠢ쭮.  뤢 ⠪ ॡ  :

    0. ணࠬ    㬥  ஢  ﭨ      
(८ࠧ    ﭨ        ᠬ    ;    ⥪   x86:
ᥬ஢     ᫥饣 )

    1. ணࠬ    㬥  ஢        ﭨ
(८ࠧ    ﭨ    ᠬ ﭨ;  ⥪ x86:
 窨 室;   樨)

    2. ࠭⢮  ﭨ         ࠭祭  (
⥮᪮ 砥;    ⮬  ୥; ⥪ x86:  
1    ᯮᮡ  樨    4,      稬
᪫祭;  ᨬ쭠    樨  -  16 ,   ४
権   2^128)

    3.   ⥯ ⠭  ⮫쪮  砥,    
室  ﭨ  ।묨   ᨬ 室,
   砥, ᫨ 砥 室  饥 ﭨ (ᨥ
  裡  ࠦﬨ    ९᪥;  
 祢 ᫥⢨  । ,        ࠦ
    )  (ࠡ⪠  訡 権  裡  稥
⢠ 2;  ⥪ iAPX386:  ᪫祭  ⪠  
䨧᪨ 饩 ; ᯮ । 樨 -
᪠,        ᮮ㤨  ᪮  ⮬      ⮩
⥪; 㦭 ᥣ  ⠭  맮 ࠡ稪
᪫祭!)

    ⢮ 0 ।⠢ 堭  ணࠬ.  ,  
⠪   ,         ࠢ        ᯨ᮪,
᪮  易  ⠫묨.

    ⢮ 1  (  ࠧ뢭  裡     ⢮   0)   
஢  䨪  ᪨ .

    ⢮ 2     ணࠬ  ᣥ஢  㦭,    
饥,  ﭨ:  ।⠢      짮   㫮
⠭.

    ⢮ 3  ⠭ 㫮.  ⨬,    設
    稨 ଠ쭮 ⠭  ⠭   稭
"-ணࠬ".    ,    ⨢稢    ணࠬ   P   ⠭
"-ணࠬ".   䨪, ࠢ, ⮦,   ,  
砥,    ⠥    ࠢ      ⮩  "-ணࠬ"
 ⨥.      ᭠砫     "
",    ᫨  䨪 - ୥,    ᨬ 
⢥   ""  " ".   ⠥ ⮩ , 
   ࠭:       ⫨    ᪮  ணࠬ  
⠫.   ࠬ 襭  Halting  Problem,  ⠪  ࠧ,  ⠪
ࠧ  ⠭   ⢥,      ᬠਢ
 㤥.

    ⠪, ⥯  ⢮ ⠪ ⬠  H(p), 
  㦥  ⨢    㥬  ணࠬ P 뢠
  ﭨ,  ண   P,   ᮢ蠥 室 㤠. 
⠭    ணࠬ P 筠.    ⢮
⠪ ணࠬ-⥪ HD,    ⠢  ।묨  
ﭨ,   ᫨ H(p) (  樨 
ﭨ ⥭).    ࠧ    ஢  ணࠬ  HD
  ணࠬ P HD 㤥 ᯮᮡ  䨪  㭪樨
H(p)      㤥   ९⢮   ४⭮   ⠭      
ࠤᠫ .

    ᪮   ᥬ  ⠫쭮    ⠫  筮  ⠪ ,   
 ⮩   ஢ ணࠬ   ॠ樨  .  
,  筮  ⢮    ⠪  ,    ᮣᥭ
⠢    ᥡ,  ᫨     ᬠਢ   ப      ᪮
ᯮ짮 ⠪ ⮬,     ⠭,  
誠  窮 OK. :-)

                      襭 ⠢ ᮢ

    ⢮ 2 ॡ ࠭祭 ࠭⢠ ﭨ.  饬-
,  ᪮  ⠡  ﭨ  ࠭        䨧᪨
ਠ,        ,   ਠ  ᥫ 쬠
࠭祭  ⮬  ⢮. , -,  
  _筮_  讬  ⢥  ;     -   
 ﭨ ,  祬 㦭  㥬  ணࠬ  P,    
ᥣ    .           㬥஢      ᢮⢠
ணࠬ-⥪ HD,   ॡ   .  ...  ,  
᪮    ᠬ ணࠬ P  맮 㭪樨 H(p),   
 _⮦_ 㦭 ⮫쪮  ;-)
    ... -,   ࠬ 襭 ஡ ⠭ 室 
㬥 ࠢ쭮 ॠ஢  ⠪  ﭨ:  ⢨  ப  
⠡ ﭨ ᥣ  䨪஢  筮 ६ (⠡
筠)  ஢  ( ப)    ,  
,  ⠭.

    ᭮,   ,    ஡ ⥪樨
ᠬ ࠤᠫ쭮 ,   类  㦭  㬥    __
ॠ樨 H(p) (    _⬥_,    ணࠬ). 筮
  ⠪ ⢥ত ᫮ ᭮. 室  
஡ ⥪樨,  H(p)    ﭨ __ࠢ
_⢥_.  ,  筮 ᥣ    ஢,      
㥬 ணࠬ P  "",   ⮩ ॠ樨 H(p),
 ஢ 䨪.    ᤥ      ୮:
⭮ ࠢ!  砥, ᫨ "" ⠬ ,    
     뫮  ⢥:  H(p)  饭      㥬
ணࠬ  P,    ⮬  ᫨   ࠤᠫ쭮  㣮
ॠ樨 H(p),    ஡ ⮩ ॠ樨.  ""  ⢥
 㣮:  ᪮ "" ॠ  -   ୥,   
 㧭,  ,  뤠 ⢥, ᮮ⢥騩 _⢨_ P,
,  祬,   室  ⢥⮬ "⮩" ॠ樨 H(p).
 ""    ⢥  㦨 訡.

    ,  ᭮ ࠧ.

     室   ⠪   㭪樨  ⮬:  ணࠬ-㫮
⠭.

    ... 祬, ᮡ⢥,    ? 祬  塞 
墠뢠  㪢쭮  ?      ⮬ ஥ 訡 祭
:  뢠騩  - "ᮢ "! , 㬠 ᠬ:
ணࠬ   ᯥ䨪樥 㭪樨,     ⨬
ࠬ.  ,    ᠬ ஢  ⨬.  ᫨ 
맮   ந室        ⨬묨  ࠬࠬ,    㭪
ᨣ  ⮬,   祬  ⠥,      "ﭭ",  
祬  塞 ஢ ⮣ ᨣ ᠬ 뢠饬 ? ,
।訩 ⨬ ࠬ, ४⥭;     ਭ
४⭮  襭    ᯮ୮ 砥 (ਭ ꥪ⨢ 襭 
ᬮ७    ⭮襭  饬  -  )?!
-,      ⮬   ஡ ࠧ訢 ᨭ ࠭:  
⨨ Ctrl-Alt-Del  Windows  १㦠,  ᭮ 
    ﭨ,   - 㠫 ( ⠪ 饭,   
७) ⫨稩.    ⮣,   ᪠ 訡   蠥  
    .

    , ⠪    ࠧ,    ।       (?)   楯
饭.   ।  ⭮ ஢ (᪮    ਬ
⮫쪮  )       ࠡ⪨ ᪫⥫
権,  ᠬ 設 ன 室 ᠬ  (, 
 - ࠡ⠥  訡 ;-).   蠥  ⢥
ࠧ:  ⠭.  ⮬   ⢥,     
  ⢨⥫쭮  ᭮.  ⥫  થ⨭  ᨫ쭮 
,   ,  짮⥫  㦥 ,    
⠭. ⮬  ࠧ , ᫨   横? 8-)
  ⨬,   ⠪  㦥 ⮫쪮 ࠧࠡ稪
, ⮡ ஢ ᢮ ணࠬ  "".

    ᫨ ,   .

        䨫䨨  ஡  "  ⢥  ".  㦭
  "  __ ⠥?"  㬥 ᪠  ᯫ⮥ ",
 !",   ""  "". ४⭠ ணࠬ (HD) ᤥ
१㬯 ,  ⢥ ⠭ "not guilty"    
㭪 H(p)  ஢࣭ ⮣.  (筥, ⥫) १㬯樨
 ,  㭪 H(p)   . 砭 - 訩 ⢥,
ᯮ.  :-)     ⮬ 䨫 襣 ᫥ 襭.   ࢮ
砥 -  砥  ⭮ ணࠬ - ⢥⢥  ⮣ 
      ⮣,         १㬯,       ஬  砥
⢥⢥        ,  ᪮    祣  
ਫ.  ᪨, । 㭪 H(p)   ⢥砥 
 " ணࠬ ᭥?",  ⠥ ஢࣠ ⢥ত "
ணࠬ    ᭥".   祬  ᭮.  襭 ਭ ;
᪮ H(p)  -    ,      ।⠢  䠪;    
।⠢      䠪⮢.   ,   ᥫ᪨   㤨,  __
।⠢  堭           砭;   
ᯥ    ࠢ㤨   ࠢ浪.    ⮫쪮
- ⢥.  砭   .        
⢥  ⮦  .    ன  祢   䨫䨨 襣
襭.

    ⬥⨬,   襭-1,   襭   ⢥⮬,    
⤠ ""  .  ,    ⠭ ᪠ ⠪ 
⢥ । 㦥 .   ⠪ 砥,   砥,    ணࠬ
⭠  易   - ⢥, ⠥ ⮫쪮 㯮,
    ᬮ  ᪠  "    ਫ!"  ०,  祬    
⨢稥.

    Do you trust, what I trust? Me, myself, and I!..

                              * * *

                     ਫ . 設 ਭ

     ਫ    易⥫   祭.    -
ᥣ    設 ਭ.   ,      ,
     - ᭮.       砥 
 ⣮塞 :-)
    ਫ  ᯨ᪥ ᯮ짮  筨    ᠭ  
쭮  ᪮  ⨫  [4],    ਤ     ᪮,
⮬      । 設 ਭ  
ਬ;  稭.
    設 ਭ  -    ⥮᪮  ன⢮,  ஥  
ᯮ ࠧ ணࠬ    ࠡ⪨  ந쭮    (᫨
    ண  -   ந,   짮⥫᪨ :-).
⢥,  १ ࠡ 뤠 짮⥫.    設  
,    ࠡ    ன      ࠭.  ⮬  
⥮᪠.   ਬ,   饬-,     ⮢,  
 ⥫⢠  .
    ன⢮ -뢮  設  -  ⨢  ,   
ᯮᮡ      뢠  祩 筮  ᪮筮 ,
ࠡ뢠      .  ਭ  ।  ᯮ짮
ᥣ    ᨬ:  0  1.  쪮 1  ଠ;  ᫠ 
। 뢠   ᫥⥫쭮     ,
祬 ᠬ ᫮.  ᫮  㤥 ।⠢    ;
᫮  -   ᫥⥫쭮   ;  ᫮  - 
  ,    ..    ࠧ,   । 㭨ᠫ
設  ⮢.
    設 ⠥    ᨬ  祩,   ᨬ 
⠭ ᨬ ᥣ 뢠  -    ⥪  祩  
।  ணࠬ,  ६頥     "" 
"ࠢ". ᫥ ⮣ 設 ४砥   ﭨ (᭮ ,
 । ணࠬ)  横 :

    1. ⥭ (!)
    2. ਭ⨥ 襭
    3.  (뢮!), ᫥饥 ᬥ饭  (⮪ 
 뢮)  室    ﭨ  (  楤  ਭ
襭)

    設 ⠭,  ᫨  ⠭ ⠪ ᨬ,   ண 
ணࠬ  ᠭ 楤 ਭ 襭 ( 設 ᪮筮
த     0,  ᫨  ॢ    筮),    ணࠬ
⠥  믮.  ᫥  믮  ணࠬ     ᮤন
१.
    ணࠬ  ⠪ 設 룫廊  ⠡  ﭨ.  
ப  ᮮ⢥ ﭨ,    - ⠭ ᨬ.  ,
᫨ ⠭ ᨬ 0,   設 ਭ  襭,  ⮥    
;  ᫨ 1 -   㣮 .  窠 ⠡ ᮤন 
 ﭨ, ᨬ,  㦭   ࠢ ᬥ饭
.  ᫨  ⪠    -   ,   ᫨ 設 ⠥
ᨬ,  ᮮ⢥騩  ,      ⠭  (.  "  ᠭ
楤  ਭ  襭").    㬠,     ⨫
⭠ ,   ⠪   㬠.
    㬠,  ⮣ 㦥  ᭮.  ਬ ணࠬ, ᪫뢠饩
 ᫠, ⮫쪮 ⥭,    ਢ  ⠭. ਢ
- ணࠬ,   㬭:  ᪫뢠 ᫮ ᠬ  ᮡ
⮫쪮 ࠧ, ᪮쪮  ஥ ᫮.
    :    ᫠   ⥫.      ।⠢    
᫥⥫쭮        ,  祬  ᠬ   ᫮.   
᪮筮   ᫠,  ࠧ  㫥.  ⮨ 
 ⪨ ,  祬    ᮬ⥫.    १  믮
ணࠬ      ⠢ ⮫쪮  ᫮,    
 १ 㬭.

    ਬ: 5  4 = 20

     -   ...001111110111110000...
              ^

    ᫥ - ...01111111111111111111110...
        .


    襭.

    樠㥬 १  0.
    ⠭    窥 ࠢ  ண ⥫,  
 ⮩ 窨 㤥 믮 ७ 横:   
१ ᫠,  ࠢ ࢮ ⥫.  , । 
⮬ ᠬ ⭮ ⬥ ᫮,  :

    ⢥:

     ⠡  .   ﭨ   ⪨. ࢠ
 -   .  㪢  -  㤠  ᤢ  :  L(eft)  
R(ight). ஥ ᫮ -  ᫥饣 ﭨ.

          ﭨ  0   1
          0         1R1  -  ; 砫쭮 ﭨ
          1         0R1 1R2
          2         0R3 1R2
          3         0L4 1R3
          4         0L6 0L5
          5         0L6 1L7
          6          -  0L6  ; 筮 ﭨ
          7         0L8 1L7
          8          -  1L9  ;  ⮬     0
          9         0R2 0L10
          10       0L11 1L10
          11       1R12 1L11
          12       0R13 1R12
          13        1L9 1R13

     ୥   ࠭窠,   ன   ணࠬ 
設 ਭ  砫쭮 ﭨ  (ࠢ,  筮) [5],  
  १  ᫥.    ⮩ ॠ樨   ணࠬ
室  ୨஢, ᪮    㬥 ࠡ 
᪮묨 ⠬.

    筨

    (  22  2001 뫨 묨)

    1. Fred   Cohen,   Computer  Viruses:  Theory  and  Experiments  //
http://all.net/books/virus/
    ( ⠪   Computers & Security, Volume 6 (1987), 22
-35.)

    2. David M.  Chess and Steve R.  White.  An  Undetectable  Computer
Virus.  // IBM Thomas J.  Watson Research Center,  Hawthorne, New York,
USA. http://www.research.ibm.com/antivirus/SciPapers/VB2000DC.htm

    3. A.M.Turing.  On  Computable Numbers,  With an Application to the
Entscheidungsproblem. // http://www.abelard.org/turpap2/tp2-ie.asp

