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

Алан Матисон Тјуринг (Alan Mathison Turing) (1912.-1954.) је британски математичар и криптограф који се сматра оцем модерних компјутера. За време другог светског рата је радио у Блетчли Парку (Bletchley Park) и саградио машину помоћу које су савезници могли читати немачке поруке шифриране преко Енигма уређаја који је имао 15x1019комбинација.

После рата је саградио прве компјутере и бавио се проблемима вештачке интелигенције. Познат по ексцентричном животном стилу, био је ухапшен године 1952. због повреде јавног морала и осуђен. Две године касније је извршио самоубиство, иако постоје теорије завере које тврде да је ликвидиран од стране британске тајне службе због тога што је под уценом могао одати државне тајне страним агентима.

 

Познат је и по томе што је дефинисао тест интелигентности вештачке интелигенције. Циљ овог тестирања је да се одреди да ли је машина заиста интелигентна, или је тек симулација интелигенције. До сада ни једна машина није успела да прође тјурингов тест, док га људи пролазе.

 

 

 

ТЈУРИНГОВА МАШИНА

 

Идеја је настала у првој половини XX века из такозваних “неважних“ области математике, који су покушали да дају одговаре да ли неке још недоказане математичке теореме имају доказе.  Тим поводом је Давид Хилберт поставио три питања:

  1. да ли је математика комплетна
  2. да ли је математика конзистентна (доследна, непровивуречна)
  3. да ли је математика одлучива (да ли постоји алгоритам који показује да је нека формула исправна)

Математичар Курт Гедел је 1930. Године одговорио на прва два питања и доказао да математика није комплетна, и да ће увек бити недоказаних теорема.

Ови докази су тридесетих година изазвали велико разочарење међу математичарима.

Алан Тјуринг је 1936. године дао одговор на треће питање на необичан начин. Пошто је уочио одређене правилности у свакодневном рачунању, замислио је такозвану Тјурингову машину, која на траци са симболима симулира рачунање. Ова замишљена (апстрактна- имагинарна) машина није стварно направљена. Служила је да покаже да ли се сваки математички проблем може решити коришћењем алгоритма (Алгоритам - графички ток размишљања). Донела је велике новине, и дефинисала нешто што ће касније постати компјутерски алгоритам. Убрзо затим је ову машину унапредио и створио Универзалну Тјурингову машину, помоћу које је дао негативан одговор на треће Хилбертово питање. На овај начин су постављене основе софтвера. 

 

 

 

Све што се може израчунати помоћу алгоритма, може се реализовати Тјуринговом машином

 

           

 

 

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


  1. Бесконачна трака садржи поља означена целим бројевима и служи само за читање и писање
    Свако поље (квадратић) може да садржи само један од знакова ( 0, 1, празно) које машина може прочитати или написати
          - Знаци 0 и 1 су бинарне ознаке и служе за запис информација
          - Празно означава крај записа

 

 


Глава за читање и писање се позиционира изнад знакова и може да изврши следеће операције на траци
      - да прочита један знак са траке изнад поља где  се налази глава
      - да напише један знак у поље на траци изнад којег се налази глава
      - помери се  за једно поље у десно (+1) или једно поље улево (-1)
      - да избрише знак на пољу изнад кога се налази

 

  1. Индикатор стање је део управљачке јединице у показује стање коме се машина може налазити. Стање може бити:
          - почетно стање
          - радно стање
          - завршно стање
  2. Управљачка јединица (програм) управља машином и води је корак по корак кроз алгоритам. Има коначан број упутстава и команди. Издаје наредбе глави шта да напише и у коју страну да се помери, према подацима са траке и тренутног стања управљачке јединице. Машина извршава наредбе по редоследу по коме оне издају. У раду доноси одлуку на основу:
         -  тренутног стања машине
         -  знака који глава чита са траке

Тада машина може да:
      -пређе у неко друго стање
      -напише неки од знакова на траци (0 или 1)
      -помери главу за једно поље улево или удесно         

Напомена: Трака служи као меморија, глава као улазно излазна једница и контролер, а уптављачка јединица као програм
 

На почетку рада се на траци налази одређени број поља са симболима. Управљачка јединица је у једном од дефинисаних стања. Чита се тренутни симбол са траке изнад кога се налази глава и уписује нови. После тога се глава може померити једно поље лево или једно поље десно. На основу стаја и прочитаног знака са траки машина одлучује у које ће ново стање прећи управљацка јединица, који ће знак бити уписан натраци уместо прочитаног и у коју ће се страну померити глава.

Дакле машина се креће од фазе до фазе користећи прецизни низ правила и једног симбола који чита са траке. Машина може да чита симбол са траке, да га промени или уклони.