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

Пример 7.8

Разгледайте решението на проблема за добавяне на 1 към единно число, обсъдено в предишния раздел, чрез машина на Тюринг. Външната азбука може да бъде зададена от множеството A = {∆, 1}, където 1 съответства на напълнената секция, а ∆ на празния символ, а напълнените последователности следват един след друг. Вътрешната азбука се дава от множеството Q = { q, z }, където q съответства на работното състояние на Linac , а z е множеството. Набор от всички правила за преобразуване (логическа функция) може да бъде представен чрез функционална схема:

Функционална схема се съставя под формата на таблица по такъв начин, че знаците, обозначаващи колони и линии, дефинират входните параметри на linac, а в клетката на таблицата изходната команда е на тяхното пресичане. По-специално, ако машинната глава изследва секцията с лента 1 и машината е в работно състояние (q), резултатът от неговата работа върху този тактов цикъл трябва да бъде повторение на 1 в тази секция и преместване на един участък вдясно R (в този случай, както е посочено, лентата се премества наляво) - тази команда се записва като q 1 R. Ако в изследваната секция ∆ и състоянието на линията q , тогава ∆ ще бъде заменена с 1, смяна на лентата няма да се извърши и машината ще спре - z 1 S. При комбинация на входа, z , както и 1 z , машината е в неработно състояние - нито промяна на конфигурацията, нито движение - поради тази причина такива комбинации няма да бъдат показани в бъдещите функционални схеми.

Нека първоначалната конфигурация е 1 q 1111 *. Тогава работата на машината в съответствие с описаната логическа функция ще се извърши по следния начин:

* Както бе споменато по-горе, не са включени незначителни празни участъци отляво и отдясно на попълнената конфигурация; тъй като в тази задача няколко последователни секции следват последователно, само те са посочени в конфигурацията.

Tact 1 Наблюдавано 1, в LU състояние q. Изходната команда q 1 R , която е еквивалентна на преместването на главата спрямо лентата с 1 стъпка надясно. Следователно, образува се междинна конфигурация от 11 q 111.

Beat 2 - преходът към конфигурацията 111 q 11 се извършва по същия начин.

Tact 3 - отидете в конфигурация 1111 q 1.

Такт 4 е преход към конфигурацията 11111 q ∆ (тук, за по-добро разбиране, правото ∆ е посочено изрично).

Tact 5 Наблюдавано Δ, в LU състояние q. Изходна команда z 1 S - вместо ∆, 1 се записва в клетката, няма промяна, работата се спира. Крайната конфигурация е 111111z .

Проблемът е решен.

Вижте също:

Пример 9.1

При равни други условия, опитът с равностойни резултати има най-голяма ентропия.

Пример 9.2.

Начини за описване на официалните езици

Пример 4.11

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

2019 @ ailback.ru