Тјурингова машина

Из пројекта Википедија

Тјурингове машине су изузетно једноставни уређаји за манипулисање симболима, који - упркос својој једноставности - могу да буду прилагођени да симулирају логику било ког рачунара који би могао да се конструише. Тјурингове машине је 1936. године описао Алан Тјуринг. Мада су симшељене да буду технички могуће, Тјурингове машине нису смишљене као практична рачунарска технологија, већ као мисаони експеримент о границама механичког рачунања; стога се у пракси ове машине не конструишу. Проучавање њихових апстрактних својстава доноси значајне увиде у рачунарску науку, и теорију комплексности.

[уреди] Пример

Тјурингова машина има врло једноставну конструкцију. Састоји се од бесконачне траке, која има на себи кућице у које могу да се уписују симболи, и главе која може да чита и пише симболе. За Тјурингову машину се дефинише азбука симбола која ће се у њој користити, и списак стања у којима глава за читање и писање може да се налази. Дефинишу се почетно стање (С₁), и завршно стање (С_к); почетно стање је стање у коме се машина налази на почетку рада, а када машина дође у завршно стање, престаје са радом. Глава може да се помера за једно поље улево (Л), за једно поље удесно (Д), или да остане у месту (М). У зависности од стања у коме се глава налази, и од симбола који се налази у кућици изнад које је глава постављена, глава ће у ту кућицу уписати одређени симбол, померити се лево или десно (или остати у месту), и променити своје стање. Овај процес се понавља док Тјурингова машина не стигне у завршно стање. Следи пример тјурингове машине која сабира два броја:

• Азбука над којом Тјурингова машина ради је следећа: „1“ (цифра броја), „+“ (знак за сабирање) „α“ (празне кућице)

Машина треба да од низа 1^м+1^н направи низ 1^м+н. На пример, од низа ..αα1111+111αα.. треба да направи низ ..αα1111111αα..

• Стања машине су:
  • С₁ 1 -> α С₂ Д - ако је глава у стању 1, и налази се над пољем у коме је уписано 1, у то поље се уписује α, глава се помера десно, и прелази у стање 2
  • С₂ 1 -> 1 С₂ Д - ако је глава у стању 2, и налази се над пољем у коме је уписано 1, у то поље се уписује 1, глава се помера удесно, и остаје у стању 2
  • С₂ + -> 1 С₃ Л - ако је глава у стању 2, и налази се над пољем у коме је уписано +, у то поље се уписује 1, глава се помера улево, и прелази у стање 3
  • С₃ 1 -> 1 С₃ Л - ако је глава у стању 3, и налази се над пољем у коме је уписано 1, у то поље се уписује 1, глава се помера улево, и остаје у стању 3
  • С₃ α -> α С_к Д - ако је глава у стању 3, и налази се над пољем у коме је уписано α, у то поље се уписује α, глава се помера удесно, и прелази у завршно стање, к

Коментар: Машина полази из стања 1, а глава се налази над пољем где је прва цифра првог сабирка. Она ту прву „1“ брише (уписује „α“), и затим се помера десно све док не наиђе на знак „+“. Уместо знака плус, уписује се „1“, и тиме се два броја спајају у један. Затим се глава помера лево, све док не наиђе на „α“, онда се враћа за једно поље десно (како би била на почетку новог броја), и ту се рад завршава. Ово враћање на почетак није било неопходно.