Информатиканың іргелі негіздері



бет53/67
Дата02.01.2022
өлшемі1.13 Mb.
#452326
1   ...   49   50   51   52   53   54   55   56   ...   67
лекция ИТН

A={0,1,…,9, }сыртқы алфавитін қолданамыз, мұнда символы бос белгіге сәйкес келеді. Ішкі алфавит алдыңғы есептегідей екі қалыптан тұрады – жұмыс қалпы (q) және тоқтау (z) (Q={q, z}). Бастапқы сөз n, сол сияқты нәтиже – n+1 – ондық санау жүйесінде жазылады, және де цифрлар көрші ұяшықтарда бір-бірден, бос орынсыз жазылады. Функционалдық схема кесте түрінде көрсетіледі (қолайлылық үшін жол q қалпына, ал бағандар – сыртқы алфавит таңбаларына сәйкес келеді):

a

0

1

2

3

4

5

6

7

8

9



q

z1S

z2S

z3S

z4S

z5S

z6S

z7S

z8S

z9S

q0L

z1S

Айталық, бастапқы конфигурациясы 21q9болсын.

Такт 1q9 q0L, яғни9таңбасы 0-ге ауысады да, головка ондықтар бірлігіне жылжиды – аралық конфигурация 2q10.

Такт 2q1 z2S, яғни1таңбасы2-геауысады да соңғы конфигурациямен 2z20 тоқтау болады, яғни, 219+1қосынды нәтижесі алынды.

Аталық, бастапқы конфигурация 99q9болсын.



Такт 1q9 q0L, яғни, 9q90аралық конфигурациясы құрылады.

Такт 2q9 q0Lq900 аралық конфигурациясы құрылады.

Такт 3q9 q0Lq 000құрылады.

Такт 4q z1Sz1000туындайды және жұмыс тоқтатылады.

Осылайша, сипатталған алгоритм кез-келген бүтін сан мен бірлікті қосуды қамтамасыз етеді. Осылайша бірлікті емес, қандай-да бір бүтін m санын қосу үшін осы алгоритмді m рет қайталау кажеттігі түсінікті. Бүтін сандарды көбейту де санды өзіне-өзін қосуға келтіруге болады. Осыдан, Тьюринг машинасы маңызды қасиетке ие – қолда бар машиналарды біріктіру арқылы жаңа машина құру мүмкіндігі – мұндай амал композиция деп аталады.

Өзінің құрылғылары бойынша Тьюринг машинасы тым примитивті. Ол алғашқы компьютерлерден әлдеқайда қарапрайым. Примитивтілігі – оның головкамен орындалатын – оқу және жазу элементар амалдар жиынтығы тым қарапайымдығында, және де сол сияқты жады ұяшықтарына қол жеткізу компьютерлердегідей адрес бойынша емес, лента бойымен тізбектей жылжу арқылы орындалатындығында. Осы себеппен, екі символды қосу немесе салыстыру сияқты қарапайым амалдарды Тьюринг машинасы бірнеше қадаммен жүргізеді, ал кәдімгі қосу және көбейту амалдары әлдеқайда көп қарапайым әрекеттер санын қажет етеді. Бірақ Тьюринг машинасы шынайы есептеуіш машиналардың моделі ретінде емес, тым қарапайым амалдармен қандай болсын күрделі алгоритмдерді құрудың принцитік (теориялық) мүмкіндігін көрсету үшін ойлап табылған, және де амалдардың өздерін де, және бірінен келесісіне өтуді де машина автоматты түрде орындайды.

Тьюринг машинасы алгоритм ұғымын жетілдірудің жолдарының бірін береді. Осыған байланысты сұрақ туындайды:



  • Тьюринг машинасы ұғымы қаншалықты жалпы болып табылады?

  • Тьюринг машинасы көмегімен алгоритмдерді беру тәсілін әмбебап деп есептеуге бола ма?

  • Кез-келген алгоритм осылайша беріле ала ма?

Қазіргі алгоритмдер теориясы осы сұрақтарға жауапты келесі гипотеза түрінде береді:

Кез-келген алгоритм тьюрингтік функционалдық схема арқылы беріліп, сәйкес Тьюринг машинасында жүзеге асырыла алады.

Бұл гипотеза Тьюринг тезисі деген атауға ие болды. Черч тезисі сияқты оны дәлелдеуге болмайды, себебі ол қатаң емес алгоритм ұғымын Тьюринг машинасының қатаң анықтамасымен байланыстырып тұр.

Негізінде егер тьюрингтік функционалдық схема арқылы жүзеге аспайтын алгоритмге мысал келтіру мүмкін болса бұл гипотезаны жоққа шығаруға боолады. Бірақ барлық осы кезге дейін белгілі алгоритмдер тьюрингтік функционалдық схема арқылы беріле алады.





Достарыңызбен бөлісу:
1   ...   49   50   51   52   53   54   55   56   ...   67




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет