Алан Мэтисон Тьюринг ( ағылш. Alan Mathison Turing; ) информатиканың дамуына үлкен үлес қосқан ағылшын математигі, логигі, криптограф ы жылы абстрактілі есептеу және логикалық процестерді, принципінде алдын ала жоғары дәлдікпен жүзеге асыру мүмкіндігі туды. Алгоритм ұғымын анықтаудағы алғашқылардың бірі. " Тюринг машинасы " болды, ол кейіннен өмірге келген әмбебап - цифрлы есептеу машиналарының көптеген қасиеттерін бойына жинақтады. ағылш. информатиканың математигі логигі криптограф ы1937 жылы

Тьюринг машиналары. Сыртқы және ішкі альфавиттер, командалар, бағдарламалар. Тьюринг машинасының жұмысының сипаттамасы. Егер алгоритм түзу құрылымын қарастырса, онда оларды түзудің үш негізгі типін : сызықтық, тармақталатын, циклдік - ерекшелеуге болады. Орындаушы командалардың орналасу ретіне қарай бірінен кейін бірін орындайтын алгоритм сызықтық деп аталады. Орындаушының әрекеті қандай да бір шарттардың орындалу нәтижесімен анықталатын алгоритм тармақталатын деп аталады. Кейбір жеке командаларды немесе командалар тобын орындағанда бірнеше рет қайталанатын алгоритм циклдік деп аталады. Көптеген алгоритмдер осы құрылымдардың бәрін өзіне біріктіреді.

Алгоритмнің математикалық анықтамасы ХХ ғасырдың отызыншы жылдарының ортасында үш типті модельдерде алынды : Есептелгіш ( рекурсивті ) функциялар теориясы ; Ақырлы, ақырсыз автоматтар теориясы ; Марковтың нормалы алгоритмдері.

21- ші ғасырдың ортасына дейін алгоритм ұғымы есептеу әдістері ұғымымен теңестірілді. Есептеу әдістерінде қолданылатын арифметикалық, анализдік, тригонометриялық операциялардың орындалу алгоритм іспеттес болып жүрді. Ондай проблемаларды шешу үшін қосымша арнаулы дәлелдеулердің қажеті болмады. Ал 21- ші ғасырдың 2- ші жартысынан бастап сандық емес объектілерге қолданылатын алгоритмдерге қатаң формулировка берудің болмайтындығы белгілі болды.

Әлдебір алгоритм көмегімен есептелетін функцияны есептелетін функция дейді. Іс жүзінде алгоритм – функцияны беру әдісі. Рекурсивті функциялар – есептелетін функциялар ұғымымен байланысты.

Әрбір Тьюринг машинасында 2 бөлік бар : Ұяшықтарға бөлінген екі жағынан да шексіз лента Автомат - жазу / оқу инесі Кез келген алгоритм үшін сәйкес Тьюринг машинасын құруға болады. Тьюринг машинасы мен тезисі болашақта да қолданылады, себебі кез келген проблема шешілмейді деп айтуға болмайды, шешілмейтін есеп болмауы керек, оны қандай да бір шешілетін түрге келтіру керек, соған орайластырылған алгоритм құрастыру керек.

Машинаның жұмысы дискретті, бірінен кейін бірі орындалатын жеке – жеке командалармен орындалуы керек. Әрекеттер детерминделген, яғни қадамдар қатаң реттелген, ал олардың нәтижесі алдыңғы қадамда алынған нәтижелермен тікелей байланысты болуы керек. Жұмыс алдында алғашқы берілгендер алгоритмнің анықталу облысынан алынуы керек. Саны санаулы қадамдарды орындаудан соң нәтиже алынуы керек. Машина универсалды, жан – жақты болуы керек, оның көмегімен кез – келген алгоритмді орындайтын болуы керек.

Егер алфавитке « бос таңба » деп аталатын таңба қосылса, оны сөзге оң жағынан да сол жағынан да қоссақ та сөз өзгермейді, яғни 1) операция бос таңбаны алмастыру болады. Сонда 2) – 3) – операцияларды орындасақ та, бәрібір 1) – қадамда тағы сол алдыңғы қадам қалады. Сондықтан абстрактылы машина әр символды зерттейді, сосын шексіз лентаға – жадыға сақтайды, егер символ бос болмаса оны басқа таңбамен алмастырады да жаңа қалыпта тұрады. Бұл машина туралы теорияны Алан Тьюринг ( ), Эмиль Пост сияқты ғалымдар ұсынған. Осы принципке сәйкестелген есептеу машиналары 8-9 жылдан кейін пайда болған.