Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Пример 7.9

Има многобитово цяло число n десетична числена система; изграждане на машина Тюринг, която осигурява изчисляването на стойността на n + 1.

Използваме външната азбука A = {0,1, ..., 9, ∆}, в която символът ∆ съответства на празен знак. Вътрешната азбука, както и в предишния проблем, се формира от две състояния - работещи (q) и спиране ( z ) ( Q = { q, z }) . Начален номер n и резултатът n + 1 също се записва в десетичната система, а числата се поставят един по един в съседните клетки без пропуски. Функционалната схема е представена от таблица (за удобство низът ще съответства на състоянието q и колони - знаци на външната азбука):

Нека първоначалната конфигурация е 21 q 9 .

Потокът 1 q 9 → q 0 L, т.е. 9 ще бъдат заменени с 0 и главата ще се премести до десетичната цифра - междинна конфигурация 2 q 10.

Потокът 2 q 1 → z 2 S , т.е. 1 ще бъдат заменени с 2 и ще спре с крайната конфигурация 2 z 20, т.е. резултатът от добавянето е 219 + 1.

Нека първоначалната конфигурация е 99 q 9.

Потокът 1 q 9 → q 0 L, т.е. ще се формира междинна конфигурация 9 q 90.

Beat 2 q 9 → q 0 L - ще се появи конфигурацията q 900.

Появява се ритъмът 3 q 9 → q 0 L - q will000.

Ударът 4 q ∆ → z 1 S - ще има z 1000 и работата ще спре.

По този начин описаният алгоритъм наистина осигурява сумирането на всяко число с десетично число и едно. Ясно е също така, че ако е необходимо да се добави не с единица, а с цяло число m, то този алгоритъм трябва да се повтори m пъти. Умножаването на цели числа също може да се намали до добавяне на число със себе си. Следователно, машините на Тюринг имат важно свойство - способността да се изгради нова машина чрез комбиниране на съществуващите - такава операция се нарича композиция.

Според устройството си, машината на Тюринг е изключително примитивна. Тя е много по-проста от първите компютри. Примитивизмът се състои в това, че има изключително прост набор от елементарни операции, изпълнявани от главата - четене и писане, и че достъпът до клетките на паметта (лентови секции) в него се осъществява не по адрес, както в компютрите, а чрез последователно движение по лентата. По тази причина дори такива прости действия като добавянето или сравнението на два символа на машината на Тюринг се изпълняват в няколко стъпки, а обичайните операции на събиране и умножение изискват много голям брой елементарни действия. Но машината на Тюринг не е измислена като модел (прототип) на реални компютри, но за да покаже основната (теоретична) възможност за конструиране на произволно сложен алгоритъм от изключително прости операции, машината автоматично извършва прехода от една към друга.

Машината на Тюринг осигурява един от начините за изясняване на концепцията на алгоритъм. Във връзка с това има въпроси:

· Колко е общоприетото понятие за машина?

· Възможно ли е да се приеме, че методът на дефиниране на алгоритми, използващ машината на Тюринг, е универсален?

· Може ли някой алгоритъм да бъде определен по този начин?

Съвременната теория на алгоритмите дава отговор на тези въпроси под формата на следната хипотеза:





Вижте също:

Пример 7.6

Компютърно кодиране и обработка на подписани цели числа

Пример 4.17

Общи подходи

Всеки алгоритъм може да бъде дефиниран с помощта на функционална схема, изпълнена в съответната машина на Тюринг.

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru