Тјурингова машина: Разлика помеѓу преработките
[непроверена преработка] | [непроверена преработка] |
Избришана содржина Додадена содржина
с Бот додава Шаблон: Без извори |
с Бот Додава: als:Turing-Maschine; козметички промени |
||
Ред 1:
{{Без извори|датум=ноември 2009}}
{{внимание}}
[[
[[
'''Тјуринговите машини''' се апстрактни машини кои покрај нивната едноставност можат да бидат приспособени да ја симулираат логичката улога на секој можен компјутер. Тјуринговите машини се опишани во 1936 од страна на [[Алан Тјуринг]]. Иако биле наменети за технички изводлива работа, Тјуринговите машини немале улога во практичната компјутерска технологија, но со истражување за границите на механичкото пресметување; тие всушност никогаш не биле направени (конструирани).
Тјурингова машина која истовремено е способна да симулира и било која друга Тјурингова машина се нарекува Универзална Тјурингова машина
Неформален опис
Концептот на Тјуринговата машина е базиран на идејата, некој да извршува
[[
За некои видови лентата се движи ,а неискористениот простор е навистна празен. Инструкцијата што треба да се изврши е прикажана над означениот поделок
[[
Во некои видови главата е таа што се движи,а лентата е стационарна. Инструкцијата што треба да се изврши (q1) се наоѓа во главата.Во овој вид на модел
Попрецизно , Тјуринговата машина се состои од:
* '''ЛЕНТА''' која е поделена не ќелии, поставени една до друга. Секоја ќелија содржи симбол од некоја конечна азбука. Азбуката содржи и специјални бленк (blank) симболи (тука означени со 'B')
* '''ГЛАВА''' која може да чита и запишува симболи на лентата и ја поместува лентата налево или надесно за еднаш (и само една) една ќелија во тој момент. Во некои модели главата се мрда,а лентата е стационарна.
* '''ТАБЕЛА'''
:(i) или избриши или напиши симбол на лентата, и
:(ii) помести ја главата
:(iii) остани во истата состојба или премини во нова во зависност од дадените правила (зададени инструкции). Кај моделите со 4 елементи табелата и кажува на машината
* '''БЕЛЕЖНИК НА СОСТОЈБИ'''
"Овие правила соодветствуваат на
Се забележува дека секој дел од машината – неговата состојба- симболите-колекциите – неговите акции – запишувањето,бришењето и позицијата на лентата – е конечно, дискретно и ефикасно; тоа се должи на неограничената должина на лентата која всушност и овозможува голем простор за складирање.
Ред 36:
== Формална дефиниција за Тјурингова машина со една лента ==
Краток формален опис
"Тјуринговата машина е конечен автомат поврзан со надворешен склад на меморија." (Minsky (1967), p. 117)
"Тјурингова машина е всушност
Конечниот автомат е претставен преку
Хопкрофт (Hopcroft) и Улман (Ullman) (1979, p. 148) формално ја дефинирале Тјуринговата машина со една лента како
Q е конечен број на состојби
Γ
b
Σ, подмножество од Г не вклучувајќи го b ,е множество од влезни симболи
q<sub>0</sub>
Да разгледаме пример за одземање на два броја, а потои и дијаграмот на Тјуринговата машина:
[[
[[
Примерите веќе добро го покажуваа тоа, како и однесувањето на компонентите во неформалниот опис, формата на параметрите при влез и излез, и позицијата на главата во почетокот мора да биде точно означена. За пример, Тјуринг
"1. Азбука за лентата
"2. Со која форма се претставени параметрите на лентата
"3. Почетната состојба на Тјуринговата машина
"4. Формата со која ке бидат презентирани одговорите
"5. Програма за машината" (Stone)
Ред 73:
== Инструкции на Тјуринг -- петорки ==
Дефинициите во литературата понекогаш се разликуваат по малку, за полесно да се објаснат некои докази, но секогаш се ускладени така што резултантаната машина да ја има истата решавачка моќ. За пример, менувајќи го множеството {L,R}
Најчестата конвенција ја претставува секоја
(дефиниција1): (qi, Sj, Sk/E/N, L/R/N, qm)
( моментална состојба qi , прочитан симбол Sj , напишан симбол
Други автори (Minsky (1967) p. 119, Hopcroft and Ullman (1979) p. 158, Stone (1972) p. 9) присвоиле друга конвенција , со нова состојба qm регистрирана веднаш после скенираниот симбол Sj:
(дефиниција 2): (qi, Sj, qm, Sk/E/N, L/R/N)
(моментална состојба qi, прочитан симбол Sj ,нова состојба qm , напишан симбол
Ред 89:
'''Пример 1'''
[[
'''Пример2'''
[[
Ред 99:
== Референци ==
* Boolos, George; Richard Jeffrey (1989, 1999). Computability and Logic, 3rd ed., Cambridge UK: Cambridge University Press. ISBN 0-521-20402-X.
* Boolos, George; John Burgess, Richard Jeffrey, (2002). Computability and Logic, 4th ed., Cambridge UK: Cambridge University Press. ISBN 0-521-00758-5 (pb.).
* 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 includes some recursion theory.
* 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 "Turing's convention", and Donald W. Davies' Corrections to Turing's 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.
* 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.
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..
Hopcroft, John E.; Rajeev Motwani, Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages, and Computation, 2nd ed., Reading Mass: Addison-Wesley.
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.
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 Turing's paper of 1936-7.
Roger Penrose (1989, 1990). The Emperor's 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, 1(3), 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.
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, [place?], ISBN 0-444-88071-2 (Volume A). QA76.H279 1990. Valuable survey, with 141 references.
Ред 131:
[[Категорија:Информатика]]
[[Категорија:Компјутери]]
[[Категорија:Рекурзивна теорија]]
[[Категорија:Алан Тјуринг]]
Ред 137 ⟶ 136:
[[Категорија:Теорија на компјутерските науки]]
[[als:Turing-Maschine]]
[[ar:آلة تورنج]]
[[be:Машына Т'юрынга]]
|