[документация]

Машината на Тюринг

Математикът Алън Тюринг (Alan M. Turing) е един от първите, които въвеждат в обръщение идеята за универсална математическа машина. Търсенето на обща алгоритмична процедура за решаване на математически проблеми започва още в началото на ХХ век - най-вече с търсенията на Хилберт. Но идеята за универсална машина и нейното теоретично осъществянае са дело на самия Алън Тюринг. Началото е поставено със статията на Тюринг от 1936 г. "On computable numbers, with an application to the Entscheidungsproblem". (повече за историята на Entscheidungsproblem.)

Стремежът е бил да се създаде (ако е възможно) универсална машина, която алгоритмично да реши всички математически задачи. В основата на тази идея стои представата, че всичко би могло да бъде сведено до алгоритмична процедура. Нека дадем няколко определения на това какво представлява откритието на Тюринг - неговата собствена машина.

Машината - дефиниции

1. Машина на Тюринг е тази машина, която може да разпознае краен брой символи посредством краен брой инструкции - (sequences of a finite number of symbols [that] can be recognized by an abstract machine with a finite set of instructions - from Ivars Peterson's "The Mathematical Tourist:").

2. Машината на Тюринг не е физически обект, а абстрактно математическо постороение, което може да реализира някаква (крайно дефинируема) изчислителна процедура. (по Роджър Пенроуз - "Новият разум на царя - за компютрите, разума и законите на физиката", пр. Николай Вълчанов, УИ "Св. Климент Охридски", София, 1998 г.)

2.1 Машината на Тюринг е модел за автоматично решаване на конкретна задача (примерно - да се дели на 2, което и да е число; или да се прибавя към число 1) и поради тази причина можем да приемем, че тя е абстрактен модел за процедурата по решаване на задачата (т.е. алгоритъм), която е зададена.

3. Абстрактният модел на Тюринг е машина, която може да чете, пише и движи лента с отбелязани на нея символи, посредством които може да извършва операции. Машината на Тюринг има краен брой състояния, на които съответстват определени действия.

3.1 A Turing machine is theoretical computer consisting of a finite set of internal states, a finite alphabet that includes a blank symbol, and a finite set of instructions. It has a physical head and a physical infinitely long tape, which is divided into cells. The cell values consist of the alphabet. The tape has a finite number of non-blank cells. The head can read and write to the cells and move the tape one cell to the left and one cell to the right. (от http://www.nmt.edu/~prcm/turing)

3.2 A Turing machine is a very simple machine, but, logically speaking, has all the power of any digital computer. It may be described as follows: A Turing machine processes an infinite tape. This tape is divided into squares, any square of which may contain a symbol from a finite alphabet, with the restriction that there can be only finitely many non-blank squares on the tape. At any time, the Turing machine has a read/write head positioned at some square on the tape. Furthermore, at any time, the Turing machine is in any one of a finite number of internal states. (от American Mathematical Society - http://www.ams.org/new-in-math/cover/turing.html)

4. Машината на Тюринг е първият компютър. И със сигурност - първият виртуален компютър. Ето защо тя прилича повече на програма (софтуер), отколкото на PC (хардуер).

Парадоксът на Машината на Тюринг:

Един от най-интересните резултати при създаването на машината на Тюринг е идеята да се конструира Универсална ТМ (Turing Machine). Тъй като всяка от отделните машини изпълнява конкретен алгоритъм и извършва конкретна операция, то би могло да се създаде Универсална ТМ, която да изпълнява всички зададени функции.

Като резултат обаче бива изведен един парадокс, който доказва невъзможността за решаването на Entscheidungsproblem.

- Не съществува машина на Тюринг, която алгоритмично да определи кога машината на Тюринг ще завърши изчислението си.

или

- Няма машина на Тюринг, която да определи кога ще спре машината на Тюринг.