Білім беру бағдарламасы: 6 B01506 Информатика Құрастырушылар : Амантурлина Г. К. аға оқытушы



жүктеу 430,16 Kb.
бет27/47
Дата13.12.2022
өлшемі430,16 Kb.
#40599
түріБілім беру бағдарламасы
1   ...   23   24   25   26   27   28   29   30   ...   47
Силлабус ИТН (копия)

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 болсын.
Такт 1 q9 q0L, яғни 9 таңбасы 0-ге ауысады да, головка ондықтар бірлігіне жылжиды – аралық конфигурация 2q10.
Такт 2 q1 z2S, яғни 1 таңбасы 2-ге ауысады да соңғы конфигурациямен 2z20 тоқтау болады, яғни, 219+1 қосынды нәтижесі алынды.
Аталық, бастапқы конфигурация 99q9 болсын.
Такт 1 q9 q0L, яғни, 9q90 аралық конфигурациясы құрылады.
Такт 2 q9 q0Lq900 аралық конфигурациясы құрылады.
Такт 3 q9 q0Lq 000 құрылады.
Такт 4 q z1Sz1000 туындайды және жұмыс тоқтатылады.
Осылайша, сипатталған алгоритм кез-келген бүтін сан мен бірлікті қосуды қамтамасыз етеді. Осылайша бірлікті емес, қандай-да бір бүтін m санын қосу үшін осы алгоритмді m рет қайталау кажеттігі түсінікті. Бүтін сандарды көбейту де санды өзіне-өзін қосуға келтіруге болады. Осыдан, Тьюринг машинасы маңызды қасиетке ие – қолда бар машиналарды біріктіру арқылы жаңа машина құру мүмкіндігі – мұндай амал композиция деп аталады.
Өзінің құрылғылары бойынша Тьюринг машинасы тым примитивті. Ол алғашқы компьютерлерден әлдеқайда қарапрайым. Примитивтілігі – оның головкамен орындалатын – оқу және жазу элементар амалдар жиынтығы тым қарапайымдығында, және де сол сияқты жады ұяшықтарына қол жеткізу компьютерлердегідей адрес бойынша емес, лента бойымен тізбектей жылжу арқылы орындалатындығында. Осы себеппен, екі символды қосу немесе салыстыру сияқты қарапайым амалдарды Тьюринг машинасы бірнеше қадаммен жүргізеді, ал кәдімгі қосу және көбейту амалдары әлдеқайда көп қарапайым әрекеттер санын қажет етеді. Бірақ Тьюринг машинасы шынайы есептеуіш машиналардың моделі ретінде емес, тым қарапайым амалдармен қандай болсын күрделі алгоритмдерді құрудың принцитік (теориялық) мүмкіндігін көрсету үшін ойлап табылған, және де амалдардың өздерін де, және бірінен келесісіне өтуді де машина автоматты түрде орындайды.
Тьюринг машинасы алгоритм ұғымын жетілдірудің жолдарының бірін береді. Осыған байланысты сұрақ туындайды:

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

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

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

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

жүктеу 430,16 Kb.

Достарыңызбен бөлісу:
1   ...   23   24   25   26   27   28   29   30   ...   47




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

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау