Машина на Тюринг: описание и примери на машини Тюринг
Машината на Тюринг е едно от най-интригуващите и вълнуващи интелектуални открития на 20-ти век. Това е опростен и полезен абстрактен модел на компютрите (компютърен и цифров), който е често срещан за реализацията на всяка компютърна задача. Благодарение на просто описание и поведение математически анализ тя е в основата на теоретичната информатика. Това проучване доведе до по-задълбочено познаване на цифровите компютри и смятане, включително разбирането, че има някои изчислителни проблеми, които не могат да бъдат решени на обикновени компютри. 
Какво е това и кой е създал
Алън Тюринг се опитва да опише най-примитивния модел на механично устройство, което ще има същите основни възможности като компютъра. Първият Тюринг описва колата през 1936 г. в статията "За изчислимите числа с приложение към проблема за разрешимостта", която се появява в докладите на Лондонското математическо общество. 
Машината на Тюринг е изчислително устройство, състоящо се от глава за четене / запис (или „скенер“) с хартиена лента, минаваща през нея. Лентата се разделя на квадрати, всяка от които носи един символ - "0" или "1". Целта на механизма е да действа както като средство за влизане и излизане, така и като работна памет за съхраняване на резултатите от междинните етапи на изчисленията.
От какво се състои устройството
Всяка такава машина се състои от два компонента:
- Неограничена лента. Той е безкраен в двете посоки и разделен на клетки.
- Автоматично контролирана програма, скенер за четене и запис на данни. Тя може да бъде във всеки момент в една от многото държави.
Всяка машина свързва две крайни серии от данни: азбуката на входящите символи A = {a0, a1, ..., am} и азбуката на състоянията Q = {q0, q1, ..., qp}. Състоянието q0 се нарича пасивно. Смята се, че устройството свършва работата си, когато пада върху него. Състоянието на q1 се нарича първоначално - машината започва изчисленията си, като е в началото в нея. Входната дума се намира на лентата на една буква в ред във всяка позиция. От двете му страни са само празни клетки.
Как работи механизмът
Машината на Тюринг има фундаментална разлика от изчислителните устройства - устройството с памет има безкрайна лента, докато за цифровите устройства това устройство има лента с определена дължина. Всеки клас задачи се решава само с една изградена машина на Тюринг. Другите видове задачи включват писане на нов алгоритъм.
Контролното устройство, което е в едно състояние, може да се движи във всяка посока по протежение на лентата. Той пише в клетките и чете от тях символите на крайната азбука. В процеса на преместване се избира празен елемент, който запълва позиции, които не съдържат входни данни. Алгоритъмът за машината на Тюринг определя правилата за преход за управляващото устройство. Те поставят главата за четене-запис на следните параметри: запис в клетка с нов символ, превключване на ново състояние, придвижване наляво или надясно по лентата. 
Свойства на механизма
Машината на Тюринг, подобно на други изчислителни системи, има своите присъщи характеристики и те са подобни на свойствата на алгоритмите:
- Дискретен. Цифровата машина преминава към следващата стъпка n + 1 само след като предишното е завършено. Всяка завършена стъпка определя какво ще бъде n + 1.
- Разбираемост. Устройството изпълнява само едно действие за една и съща клетка. Той вмъква символ от азбуката и прави едно движение: наляво или надясно.
- Детерминизъм. Всяка позиция в механизма съответства на едно изпълнение на посочената схема и на всеки етап от действието и последователността на тяхното изпълнение са недвусмислени.
- Ефективност. Точният резултат за всеки етап се определя от машината на Тюринг. Програмата изпълнява алгоритъма и в краен брой стъпки влиза в състояние q0.
- Маса. Всяко устройство е дефинирано над валидни думи в азбуката.
Тюринг функции на машината
Решението на алгоритмите често изисква изпълнението на функция. В зависимост от възможността за писане на верига за изчисления, функцията се нарича алгоритмично разрешима или неразрешима. Като набор от естествени или рационални числа, думи в крайната азбука N за една машина, се разглежда последователността на множеството B - думи в рамките на двоичната кодова азбука B = {0.1}. Резултатът от изчислението също взема предвид "неопределената" стойност, която възниква, когато алгоритъмът виси. За да се изпълни функцията, е важно да има формален език в крайната азбука и разрешимостта на проблема с разпознаването на правилните описания. 
Програма за устройството
Програмите за механизма на Тюринг се формират от таблици, в които първият ред и колоната съдържат знаците на външната азбука и стойностите на възможните вътрешни състояния на автомата - вътрешната азбука. Табличните данни са команди, които се възприемат от машината на Тюринг. Решаването на проблемите става по следния начин: писмото, четено от главата в клетката, в която се намира в момента, и вътрешното състояние на главата на автомата определят коя команда трябва да бъде изпълнена. По-конкретно, такава команда се намира в пресечната точка на символите на външната азбука и вътрешната, които са в таблицата. 
Компоненти за изчисления
За да се изгради машина на Тюринг за решаване на една конкретна задача, е необходимо да се определят следните параметри за нея.
Външна азбука. Това е някакъв краен набор от символи, обозначени със знака А, съставните елементи на които се наричат букви. Един от тях - a0 - трябва да е празен. Например азбуката на устройство на Тюринг, работеща с двоични числа, изглежда така: A = {0, 1, a0}.
Непрекъснат низ от букви и цифри, записани на лента, се нарича дума.
Автоматичната машина е устройство, което работи без човешка намеса. В машината на Тюринг тя има няколко различни състояния за решаване на проблеми и при определени условия се премества от една позиция в друга. Комбинацията от такива състояния на каретата е вътрешна азбука. Той има буквено означение на формата Q = {q1, q2 ...}. Една от тези разпоредби - q1 - трябва да бъде първоначалната, т.е. това, което стартира програмата. Друг необходим елемент е състоянието q0, което е крайно, т.е. завършва програмата и поставя устройството в позиция стоп.
Таблица за преобразуване. Този компонент е алгоритъм за поведението на носещото устройство, в зависимост от текущото състояние на машината и стойността на прочетения символ. 
Алгоритъм за автомат
Превозът на устройството Turing по време на работа се контролира от програмата, която по време на всяка стъпка изпълнява последователността на следните действия:
- Писане на външен азбучен знак в позиция, включително и празна, чрез замяна на елемент, който е в него, включително и празен.
- Преместете една стъпка наляво или надясно.
- Променете вътрешното си състояние.
Така, когато пишете програми за всяка двойка символи или позиции, трябва да бъдат точно описани три параметъра: i - елемент от избраната азбука А, посока на преместване на каретката ("←" наляво, "→" надясно, "точка" - без движение) и q k е новото състояние на устройството, например командата 1 “←” q 2 е настроена на “замяна на знака с 1, придвижване на главата на каретата наляво от една стъпка-клетка и осъществяване на прехода към състоянието q 2 ”.
Машина на Тюринг: примери
Пример 1. Дадена е задачата да се изгради алгоритъм, който добавя един към последната цифра на даден номер, намиращ се на лентата. Входни данни - дума - цифри от цялото десетично число, записани в последователни клетки на лентата. В началния момент устройството се намира срещу най-дясния символ - цифрата на номера.
Решението. Ако последната цифра е равна на 9, тогава тя трябва да бъде заменена с 0 и след това да бъде добавена към предходния знак. Програмата в този случай за това устройство на Тюринг може да бъде написана по следния начин:
| a 0 | 0 | 1 | 2 | 3 | ... | 7 | 8 | 9 | |
| q 1 | 1 Н q 0 | 1 Н q 0 | 2 Н q 0 | 3H q 0 | 4H q 0 | ... | 8 Н q 0 | 9 Н q 0 | 0 λ q 1 |
Тук q 1 е състоянието на промяна на цифрата, q 0 е стоп. Ако в q 1 автоматът фиксира елемент от серията 0..8, то го замества съответно с единица от 1..9, след което превключва на състояние q 0 , т.е. устройството спира. Ако каретката фиксира число 9, тя я заменя с 0, след това се премества наляво, като спира в състояние q 1 . Това движение продължава, докато устройството фиксира цифра по-малка от 9. Ако всички символи са равни на 9, те се заменят с нули, 0 се заменя с водещ елемент, каретката ще се премести наляво и ще запише 1 в празна клетка. Следващата стъпка ще бъде преходът в състояние q 0 - стоп.
Пример 2. Дадена серия от символи, обозначаващи отварящи и затварящи скоби. Необходимо е да се изгради устройство на Тюринг, което да премахне двойка реципрочни скоби, т.е. елементи, подредени в ред - “()”. Например, първоначалните данни: “) (() (()”, отговорът трябва да бъде: “) .. ((”. Решение: механизмът, намиращ се в q 1 , анализира най-левия елемент в линията.
| a 0 | ( | ) | |
| q 1 | а 0 Н q | (P q 2 | ) P q 1 |
| q 2 | а 0 Н q | (P q 2 | ) λ q 3 |
| q 3 | а 0 Н q | a 0 n q 3 | a 0 n q1 |
Посочете q 1 : ако символът “(” се срещне, след това преместете надясно и отидете в положение q 2 ; ако е дефиниран “a 0 ”, след това спрете.
Състояние q 2 : анализът на скобата “(” за наличието на двойка се извършва, в случай на съвпадение трябва да се окаже “)”. Ако елементът е чифт, след това направете каретата обратно на ляво и отидете на q 3 .
Посочете q 3 : първо изтрийте символа “(”, а след това “)” и отидете на q 1 .