Топ-100
Back

ⓘ Тјурингова машина. Тјуринговите машини се апстрактни машини кои покрај нивната едноставност можат да бидат приспособени да ја симулираат логичката улога на секо ..




Тјурингова машина
                                     

ⓘ Тјурингова машина

Тјуринговите машини се апстрактни машини кои покрај нивната едноставност можат да бидат приспособени да ја симулираат логичката улога на секој можен компјутер. Тјуринговите машини се опишани во 1936 од страна на Алан Тјуринг. Иако биле наменети за технички изводлива работа, Тјуринговите машини немале улога во практичната компјутерска технологија, но со истражување за границите на механичкото пресметување; тие всушност никогаш не биле направени.

Тјурингова машина која истовремено е способна да симулира и било која друга Тјурингова машина се нарекува Универзална Тјурингова машина УТМ, или едноставно универзална машина. Поконкретна математичка дефиниција со слична универзална природа беше претставена од Alonzo Church, чија работа на lambda calculus се спои со Тјуринговата во формалната теорија на пресметување позната како теза на Church–Turing. Тезата дека Тјуринговите машини навистина ги опфаќаат информациите за ефективните методи од логиката и математиката, и овозможуваат прецизна дефиниција на алгоритам или механичка процедура. Неформален опис Концептот на Тјуринговата машина е заснован на идејата, некој да извршува добро дефинирана процедура со тоа што ќе ја менува содржината на неограничена хартиена лента, која е поделена на поделци кои на себе имаат еден од множеството симболи за конкретната азбука. Извршувачот треба да запамети една од можните состојби и процедурата е формулирана во многу едноставни чекори во вид "Ако моменталната состојба е 42 и симболот што е на таа позиција е 0 тогаш замени го со 1, помести еден симбол на десно, и земи ја 17-та состојба за наредна состојба."

За некои видови лентата се движи, а неискористениот простор е навистна празен. Инструкцијата што треба да се изврши е прикажана над означениот поделок q4. Приказ според Клини Kleene 1952 p. 375).

Во некои видови главата е таа што се движи, а лентата е стационарна. Инструкцијата што треба да се изврши q1 се наоѓа во главата. Во овој вид на модел "празниот поделок" од лентата е означен со 0. Сивите поделци, заедно со се празниот поделок 0 кога се скенираат во главата на Тјуринговата машина, и поделците означени со 1, 1, B, и главниот симбол, ја означуваат состојбата на ситемот. Приказ според Мински Minsky 1967).

Попрецизно, Тјуринговата машина се состои од:

  • ЛЕНТА која е поделена не ќелии, поставени една до друга.

Секоја ќелија содржи симбол од некоја конечна азбука. Азбуката содржи и специјални бленк blank симболи тука означени со B и еден или повеќе други симболи. Лентата се претпоставува дека е неограничена од лево и од десно, т.е. Тјуринговата машина секогаш има доволно лента за потребните пресметки односно функции кои треба да бидат извршени. Ќелиите на кои не е ништо испишано се сметаат за празни односно пополнети со бленк симболот" B”. Во некои видови лентата има лев крај исполнет со специјален симбол; лентата завршува или е неограничена на десно.

  • ГЛАВА која може да чита и запишува симболи на лентата и ја поместува лентата налево или надесно за една и само една ќелија во тој момент.

Во некои модели главата се мрда, а лентата е стационарна.

  • "табела на премини” од функции која, дадента состојба кај моделите со 5 елемнти во која моментално машината се наоѓа и симболот кој го чита од лентата и кажува на машината да ја изведе следната низа
i или избриши или напиши симбол на лентата, и ii помести ја главата L еден чекор на лево или R еден чекор на десно, и iii остани во истата состојба или премини во нова во зависност од дадените правила зададени инструкции.

Кај моделите со 4 елементи табелата и кажува на машината ia избриши или напиши симбол или ib помести ја глава налево или надесно, и ii остани во истата состојба или премини во нова како што е кажано, но не двете акции ia и ib во истата инструкција. Во некои модели, ако нема внес во табелата за моменталната позиција на симболот и состојбата тогаш машината ќе го сопре процесот; други видови на модели на Тјурингова машина бараат сите места во табелата да бидат пополнети.

  • БЕЛЕЖНИК НА СОСТОЈБИ кој ги регистрира состојбите од Тјуринговата табела.

Бројот на различни состојби е секогаш во конечен број и постои една специјална почетна состојба со која бележникот на состојби е иницијализиран. Тјуринг ова го дефинирал како "правила" кои ќе овозможат правилна работа на "компјутерот" нештото што работи со "недефинирани особини": "Овие правила соодветствуваат на" состојбите на мозокот”.

Се забележува дека секој дел од машината – неговата состојба - симболите - колекциите – неговите акции – запишувањето, бришењето и позицијата на лентата – е конечно, дискретно и ефикасно; тоа се должи на неограничената должина на лентата која всушност и овозможува голем простор за складирање.

                                     

1. Формална дефиниција за Тјурингова машина со една лента

Краток формален опис на "Тјуринговата машина": "Тјуринговата машина е конечен автомат поврзан со надворешен склад на меморија." Minsky 1967, p. 117) "Тјурингова машина е всушност конечен секвенцијален автомат кој може да се поврзе со други надворешни складишта на информации." Booth 1967, p. 354) Конечниот автомат е претставен преку табелата на состојби заедно со се регистарот на состојби. "Надворешниот склад на меморија" е лентата. Влезот во машината е всушност прочитаниот симбол од лентата. Излезот од машината е командата за запишување или бришење на симболот и командата за поместување налево или надесно на лентата. Хопкрофт Hopcroft и Улман Ullman 1979, p. 148 формално ја дефинирале Тјуринговата машина со една лента како 7-торка каде

Q е конечен број на состојби

Γ е конечниот борј на азбука или симболи на лентата

b ∈ Γ е бланко симболот единствениот симбол на кој не му е дозволено да се појави на лентата многу често во секој чекор додека трае процесот

Σ, подмножество од Г не вклучувајќи го b, е множество од влезни симболи

δ: Q × Γ → Q × Γ × {L,R} е функција на премин, каде L е шифтирање на лево, а R е шифтирање на десно.

q 0 ∈ Q е иницијална почетна состојба

⊆ Q е можество од крајни односно прифатливи состојби

Да разгледаме пример за одземање на два броја, а потоа и дијаграмот на Тјуринговата машина:

Примерите веќе добро го покажуваа тоа, како и однесувањето на компонентите во неформалниот опис, формата на параметрите при влез и излез, и позицијата на главата во почетокот мора да биде точно означена. За пример, Тјуринг им ги менува местата на "фигурите" "1" и "0". Други модели го формираат влезот како тесно-спакувани унарни 1, со празни места помеѓу два различни стринга, други видови пак ставаат 0, сите одделени со 1, на чисто празна лентаитн.; излезот може но не мора да се појави во сличен вид. За навистина да се "опише" процесот на Тјурингова машина Stone 1972 вели дека е неопходно да го има следнво: "1. Азбука за лентата "2. Со која форма се претставени параметрите на лентата "3. Почетната состојба на Тјуринговата машина "4. Формата со која ќе бидат презентирани одговорите на лентата кога Тјуринговата машина ќе заврши со работата "5. Програма за машината" Stone

                                     

2. Инструкции на Тјуринг -- петорки

Дефинициите во литературата понекогаш се разликуваат по малку, за полесно да се објаснат некои докази, но секогаш се ускладени така што резултантната машина да ја има истата решавачка моќ. За пример, менувајќи го множеството {L,R} во {L,R,N}, каде N "Ништо" или "Нема операција” ќе дозволи лентата да не се помести ни налево, ниту надесно туку да остане во истата состојба, а тоа не ја зголемува пресметувачката моќ на машината. Најчестата конвенција ја претставува секоја "Тјурингова инструкција" во "Тјурингова табела" за една од девет петорки, од конвенцијата Turing/Davis Turing 1936 in Undecidable, p. 126-127 and Davis 2000 p. 152):

дефиниција1: Други автори Minsky 1967 p. 119, Hopcroft and Ullman 1979 p. 158, Stone 1972 p. 9) присвоиле друга конвенција, со нова состојба qm регистрирана веднаш после скенираниот симбол Sj:

дефиниција 2:

                                     

3. Наводи

  • Boolos, George; John Burgess, Richard Jeffrey, 2002. Computability and Logic, 4th ed., Cambridge UK: Cambridge University Press. ISBN 0-521-00758-5 pb. Some parts have been significantly rewritten by Burgess. Presentation of Turing machines in context of Lambek "abacus machines" cf Register machine and recursive functions, showing their equivalence.
  • Boolos, George; Richard Jeffrey 1989, 1999. Computability and Logic, 3rd ed., Cambridge UK: Cambridge University Press. ISBN 0-521-20402-X.
  • Davis, Martin; Ron Sigal, Elaine J. Weyuker 1994. Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science, 2nd ed., San Diego: Academic Press, Harcourt, Brace & Company.
  • B. Jack Copeland ed. 2004, The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press Oxford University Press, Oxford UK, ISBN 0-19-825079-7. Contains the Turing papers plus a draft letter to Emil Post re his criticism of "Turings convention", and Donald W. Davies Corrections to Turings Universal Computing Machine
  • Martin Davis 1958. Computability and Unsolvability. McGraw-Hill Book Company, Inc, New York. On pages 12–20 he gives examples of 5-tuple tables for Addition, The Successor Function, Subtraction x > = y, Proper Subtraction 0 if x < y, The Identity Function and various identity functions, and Multiplication.
  • Taylor L. Booth 1967, Sequential Machines and Automata Theory, John Wiley and Sons, Inc., New York. Graduate level engineering text; ranges over a wide variety of topics, Chapter IX Turing Machines includes some recursion theory.

Martin Davis ed. 1965, The Undecidable, Raven Press, Hewlett, NY. Martin Davis 2000. Engines of Logic: Mathematicians and the origin of the Computer, 1st edition, W. W. Norton & Company, New York. ISBN 0-393-32229-7 pbk. Hennie, Fredrick 1977. Introduction to Computability. Addison-Wesley, Reading, Mass. On pages 90–103 Hennie discusses the UTM with examples and flow-charts, but no actual code. Rolf Herken. The Universal Turing Machine – A Half-Century Survey. Springer Verlag. ISBN 3-211-82637-8. Andrew Hodges, Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof. John Hopcroft and Jeffrey Ullman, 1979. Introduction to Automata Theory, Languages and Computation, 1st edition, Addison-Wesley, Reading Mass. ISBN 0-201-02988-X. A difficult book. Centered around the issues of machine-interpretation of "languages", NP-Completeness, etc. Hopcroft, John E.; Rajeev Motwani, Jeffrey D. Ullman 2001. Introduction to Automata Theory, Languages, and Computation, 2nd ed., Reading Mass: Addison-Wesley. Distinctly different and less intimidating than the first edition. Stephen Kleene 1952, Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam Netherlands, 10th impression with corrections of 6th reprint 1971. Graduate level text; most of Chapter XIII Computable functions is on Turing machine proofs of computability of recursive functions, etc. Knuth, Donald E. 1973. Volume 1/Fundamental Algorithms: The Art of computer Programming, 2nd ed., Reading, Mass.: Addison-Wesley Publishing Company. With reference to the role of Turing machines in the development of computation both hardware and software see 1.4.5 History and Bibliography pp. 225ff and 2.6 History and Bibliographypp. 456ff. Marvin Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem." Excellent, i.e. relatively readable, sometimes funny. Christos Papadimitriou 1993. Computational Complexity, 1st edition, Addison Wesley. ISBN 0-201-53082-1. Chapter 2: Turing machines, pp. 19 – 56. Emil Post 1936, "Finite Combinatory Processes - Formulation 1", Journal of Symbolic Logic, 1, 103-105, 1936. Reprinted in The Undecidable pp. 289ff. Emil Post 1947, "Recursive Unsolvability of a Problem of Thue", Journal of Symbolic Logic, vol. 12, pp. 1–11. Reprinted in The Undecidable pp. 293ff. In the Appendix of this paper Post comments on and gives corrections to Turings paper of 1936-7. Roger Penrose 1989, 1990. The Emperors New Mind, 2nd edition, Oxford University Press, New York. ISBN 0-19-851973-7. Ivars Peterson 1988. The Mathematical Tourist: Snapshots of Modern Mathematics, 1st edition, W. H. Freeman and Company, New York. ISBN 0-7167-2064-7 pbk. Rogozhin, Yurii, "A Universal Turing Machine with 22 States and 2 Symbols", Romanian Journal Of Information Science and Technology, 13, 259-265, 1998. surveys known results about small universal Turing machines Michael Sipser 1997. Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Chapter 3: The Church-Turing Thesis, pp. 125 – 149. Stone, Harold S. 1972. Introduction to Computer Organization and Data Structures, 1st ed., New York: McGraw-Hill Book Company. ISBN 0-07-061726-0. Paul Strathern. Turing and the Computer – The Big Idea. Anchor Books/Doubleday. ISBN 0-385-49243-X. Alan Turing 1936, "On Computable Numbers, With an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, Volume 42 1936. Eprint. Reprinted in The Undecidable pp. 115–154. Peter van Emde Boas 1990, Machine Models and Simulations, pp. 3–66, in Jan van Leeuwen, ed., Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, ISBN 0-444-88071-2 Volume A. QA76.H279 1990. Valuable survey, with 141 references. Hao Wang, "A variant to Turings theory of computing machines", Journal of the Association for Computing Machinery JACM 4, 63-92 1957. Stephen Wolfram, Wolfram, Stephen, A New Kind of Science, Wolfram Media, ISBN 1-57955-008-8



                                     
  • информатиката, формализирајќи ги концептите за алгоритам и пресметки со т.н. Тјурингова машина која одиграла значајна улога во создавањето на современиот сметач
  • да се дешифрираат. Во текот на тие истражувања настанала познатата Тјурингова машина Инфоматиката за основа ја има математиката, електрониката, физиката
  • што хардверската безбедност се спроведува со употреба на логика не - Тјурингова машина сурова комбинаторска логика или едноставни конечни автомати Еден
  • препознаени од страна на линеарно ограничен автомат неограничена Тјурингова машина чија лента е ограничена на константен број од должината на влезот
  • разни алтернативни механички процеси за пресметување Од ова следи Черч - Тјурингова теза. Ламбда - калкулусот влијаеше на дизајнот на програмскиот јазик Lisp