Тюринг машина се състои от безконечна лента, която е разделена на клетки (клетки) на еднаква амплитуда. Във всяка клетка може да се запише точно една буква. Празна клетка означава, че тя съдържа празни символи. За да преместите лента Машината е оборудвана с един прост механизъм лента транспорт, което позволява да се движат на лента с една клетка наляво или надясно. За да прочетете написани върху символа за панделка и ще го напиша на лента Тюринг машина е снабдена с четяща глава - запис. В същото време главата в даден момент може да чете само едно писмо, написано на клетката на лентата, която се намира под главата. писма не са заместител на четене, което е написано в клетката
Основната част от машината на Тюринг е логическа единица, която има бутон старт. Когато го натиснете, устройството логика получава първоначалното състояние и започва операционна:
1. причинява главата да чете писмо, в което се намира на лентата под главата;
запис на касета, в клетката под главата, някои от буквите;
за да преместите лентата наляво, надясно, или оставени на място,
в да променят собственото си състояние;
3. Ако в резултат на действията, посочени в параграф 2, буква се намира под главата, позицията на лентата и държавната машина логика блок takimizhe на останат такива, каквито са били точно преди тези стъпки, след което машината спира. Във всички останали случаи, логика единица върнете на стъпка 1.
- някои азбука P = о, ..., пи. PN> съдържащи писма могат да бъдат записани на лентата. Тази азбука се нарича азбуката на машина на Тюринг;
- азбука А = 1. А2. ..., съм>, съдържащ състояние, което може да е логическо устройство;
- азбука D = -1. d0. d1>, предназначена да покаже лента движение наляво или надясно и да се спре на лентата.
Ние помним, че ние наричаме набор от азбука подредени в определен смисъл, символите на езика или система. Тези символи, наречени букви. Само символи, които са част от тази азбука, могат да бъдат използвани за изграждане на думи.
Ние описва поведението на машина на Тюринг, когато логика единица, параграф 2, в съответствие с символите.
Ако главата чете писмо пи. и устройството е в състояние на изкуствен интелект. поведението на машината се определя от запис пиксела ди AZ. която съответства на екипа:
записано на лента вместо писмо пи писмо пи на;
да се направи движение на Dy на лента;
отидете в състояние на логика блок AZ.
Очевидно е, че комбинацията от реакции към пи. ай за аз ≠ й ще зависи от работата на Тюринг машини. Реакцията на машината от комбинацията на пи. ай могат да бъдат представени като таблица, в която клетките са тройни на формата на символи пиксела ди AZ.
Ако записвате на касета за една дума в азбуката на P и натиснете бутона старт, в резултат на машината има два възможни изхода:
работата на машината, след краен брой стъпки спира. В една и съща дума, изписана върху лентата ще се нарича резултат от нейната работа, т.е. машина е приложима за първоначалните данни;
машината никога не спира, т.е. Резултат: Машината няма да издава и не е приложим за първоначалните данни.
Кореспонденция установен Тюринг машина между изходните данни за които се отнася това, както и резултатите от неговата работа, е известно число неотрицателна функция е (х).
При един функция е (х) = х + 1 при 0 h≥ Построява Тюринг машина, която изпълнява тази функция.
1) Въведете символите и определяне на първоначалното състояние на лентата:
а) стойността на х ще бъдат записани на лентата като низ, състояща се от единици и празни клетки ще бъдат означени с нули;
б) организира на лентата, така че най-левия блок е под главата;
в) превод на логическо устройство в първоначалното му състояние ай;
2) анализира логическата операция блок:
а) ако държавата смята за символ ай глава 1, е необходимо устройство логика отново записва в клетката 1, лентата напредна с една позиция наляво и той остава в същото състояние, ай;
б) ако държавата смята за символ ай глава 0, логическата-ING единица трябва да бъде написан в клетката 1, лентата остави в същото положение отида сам в състояние на А2;
в) в състояние на А2 и главата четене символ 1, устройството логика трябва отново да бъде написана в клетката 1, лентата не се движи и да остане в състояние А2. В този случай, машината спира;
3) изграждане на таблицата функция на машината Тюринг, която изчислява стойността на функцията F (X) = х + 1, h≥0:
д) след четвъртата стъпка ще спре машината, и лента, се записва като стойност на функция, съответстваща на броя на клетките, попълнено символи 1.
При изчисляване на функцията F (х) е алгоритъм, чрез която да се конструира Тюринг машина, след това тази функция ще се нарича Тюринг изчислимо.
ние можем да формулираме основната теза Тюринг, както следва: ". За всяка изчислима функция, можете да изгради Тюринг машина, която изпълнява тази функция"
Свързани статии