Туринг машиналарының әртүрлі таңбалар жиынтығымен жұмыс істеу уақыты

Arora және Barak's Computational Complexity , 1.5-те, егер $ f $ $ T (n) $ функциясындағы $ \ Gamma $ алфавиті бар Turing машинасы бойынша есептелетін болса, онда ол есептеледі \ $ R \ $ r \ $ $ символы бар Turing машинасының $ \ {0,1, \ rhd, \ Box \} орнатылған $ 4 \ log | \ Gamma | T (n) $ әр таспаның басын белгілеңіз және $ \ Box $ бос белгісі болып табылады.

Менің ойымша, біз $ 3 \ log | \ Gamma | T (n) $ мәніне дейін азайта аламыз. Мен мұны дұрыс деп санаймын?

Менің ойымша, жоғарыда аталған кітабында талқыланған бір құрылғы арқылы қол жеткізуге болады деп ойлаймын: біз түпнұсқа Turing машинасының әр әліппесін $ k = \ log | \ Gamma | $ bits дәйектемесімен ұсынамыз. Бұдан әрі түпнұсқа машинаның бос таңбасын $ k $ $ \ Box $ s дәйектілігі арқылы көрсетуді шешейік (бұл кітапта айтылмаған). Біздің жаңа машинада аралық күйлер бар, онда ол түпнұсқалық машинаның таспасынан оқылатын символды анықтау үшін $ k $ бит оқиды, содан соң әрбір таспаға $ k $ артқа қадам жасайды, жаңа символдың түпнұсқалық машинаның таспаларына жазылған, одан кейін түпнұсқа машинадан кейін оқылған символдың басында орналасқан бастикті орналастыру үшін $ k $ қадамдарын әрбір таспадағы солға немесе оңға жылжытады. Осылайша, түпнұсқа машинаның әрбір қадамын модельдеу үшін барлығы $ 3к $ қадамы қажет.

Мысалы, $ | \ Gamma | = 16 $ деп ойлап, оны abcd түріндегі символды оқып шығуды талап ететін түпнұсқа машинаның қадамын имитациялаймыз, оны ABCD содан кейін басын оңға қарай жылжытыңыз. Мұны төмендегідей орындауға болады:

Біз бастаймыз

efgh|abcd|pqrs
     ^

4 қадамда барлық abcd оқыңыз. 4-ші қадамда D бойынша d дегенді ауыстыру керек деген шешімге жеткілікті екенін білеміз. Біз мұны істеп, бір қадамға көшеміз

efgh|abcD|pqrs
       ^

In 3 more steps we have replaced abc by ABC and positioned the head at B

efgh|ABCD|pqrs
      ^

3 қадамда біз басты p деп ауыстырдық

efgh|ABCD|pqrs
          ^

Егер түпнұсқалық құрылғы оң жақтан емес, сол жаққа кетуді қалаған болса, h жазғаннан кейін кодты h деп белгілеп, e 3 қадамда. Осылайша, бізге тек $ 3к-2 $ қадамдар қажет.

2
Сіздің дәлеліңіз жақсы. Бірақ сіз жақсы жасай аласыз: әрқашан симуляцияланған ұяшықтың сол жақ символына секіріп өтудің қажеті жоқ. Шынында да, сол немесе оң жақтан симуляцияланған символды енгізгенімізді және оны солдан оңға немесе оңнан солға қарай оқитынын қадағалауға болады. Сол жақтан имитациялық ұяшық енгізілсе, read-write-right өтуі $ 3k-2 $ қадамды қажет етеді, бірақ read-write-left өтуі $ 2k-1 $ қадамдарын қажет етеді (және келесі ұяшықтан оңнан-солға).
қосылды автор Marzio De Biasi, көзі

Жауап жоқ

0