БК Универзитет у Београду
Факултет за математику и рачунарске науке
Maстер студије
СЕМИНАРСКИ РАД
Наслов рада: ТЈУРИНГОВА МАШИНА КАО МОДЕЛ ЗА РАЧУЊАЊЕ
Предмет: ТЕОРИЈА АЛГОРИТАМА, ЈЕЗИКА И АУТОМАТА
Ментор:
Студент:
Проф. др Лазар Копања
Драган Златковић
Бр. индекса: 2017/6801
Београд, 10. јануар 2018. г.г.
САДРЖАЈ
УВОД
........................................................................................................................................ 3.
1.
ЖИВОТ АЛАНА ТЈУРИНГА
..........................................................................................4.
2.
ТЈУРИНГОВЕ МАШИНЕ
................................................................................................8.
2.1. ОСНОВНИ МОДЕЛИ ТЈУРИНГОВЕ МАШИНЕ...................................................9.
2.2. УНИВЕРЗАЛНЕ ТЈУРИНГОВЕ МАШИНЕ..........................................................12.
3.
ЗАДАТАК
...........................................................................................................................14.
4.
ЗАКЉУЧАК
...................................................................................................................... 15.
5.
БИБЛИОГРАФИЈА
.........................................................................................................16.
5.1. ЛИТЕРАТУРА...........................................................................................................16.
5.2. ИНТЕРНЕТ ИЗВОРИ................................................................................................16.
УВОД
2
1.
ЖИВОТ АЛАНА ТЈУРИНГА
Алан Тјуринг је рођен 1912. године у Лондону. Родитељи су му шкотског порекла,
аристократског. Како и доличи једном племићу, похађао је најелитније школе свога времена
у којима је видно испољавао свој таленат за науку (Иличић, 2015: 8).
Слика 1.) Алан Тјуринг
4
Након завршене средње школе, Тјуринг уписује Кембриџ, где је 1934. године,
дипломирао на математици са изузетним успехом. Наредне године постаје асистент на
колеџу и успешно брани докторску дисертацију на тему централне граничне теореме.
Поменута теорема је била доказана још 1922, што Тјуринг није знао, ипак то није ни на који
начин умањило утисак комисије о његовом оригиналном и прецизном раду.
1936. године, Алан Тјуринг објављује једно од својих најзначајнијих дела, данас
познато под називом: „Тјурингове машине“. Негде у то време, Алан Тјуринг почиње да ради
на одређено време у Државној школи за кодирање и шифре (енгл.:
Government Code and
Cypher School,
скраћено:
GCCS
). Тамо се бавио покушајима разбијања шифара немачке
софистициране машине за кодирање „Енигме“. Почео је други светски рат и Тјуринг је остао
у тиму који се бавио дешифровањем Енигме и Лоренца
СЗ
-
40/42
. Помогао је да се развије
машина „Бомбе“ која је пратила рад Енигме и била од велике помоћи при њеном
дешифровању (Иличић, 2015: 9).
У првим годинама након рата, Тјуринг се доселио у лондонско насеље Ричмонд, где је
радио у Националној лабораторији за физику. Од 1945. до 1947. године је у Националној
Физичкој Лабораторији, где је радио на дизајнирању
ACE-а
(енгл.:
Automatic Computing
Engine
). 19. фебруара 1946. године презентирао је дизајн првог рачунара у Британији. Иако
га је дизајнирао,
ACE
је извршио први програм тек 10. маја 1950. године, и то у Тјуринговом
одсуству, јер је он тада био у Кембриџу. Године 1949. је постао директор рачунарске
лабораторије, Манчестерског Универзитета, и радио је на софтверу једног од првих правих
рачунара, Манчестерском Марку I. Радио је и на проблему вештачке интелигенције, и
представио је експеримент познат као Тјурингов тест.
5
