Усъвършенстване на концепцията за алгоритъм бе даден чрез пощите и A.Tyuringom независимо в 1936-1937gg. Основната идея от тях е фактът, че алгоритмични процеси - процес, който може да постигне подходящия начин, "машина". Те са описани хипотетични (условни) устройства, които се наричат "Великия пост Machine" (MP) и "Тюринг машината" (MT). Тъй като те имат много общо помежду си, а след това по-късно те станали известни като Тюринг машини.
А Тюринг машина се състои от следните компоненти:
1. Информационни панделки, представляващи безкраен паметта на машината. Това магнитно или хартиена лента безкраен разделен на клетки. само един характер, включително и нула може да се постави във всяка клетка.
2. Главата за четене - чувствителен специален елемент, който може да проучват съдържанието на клетките. Лентата може да се мести по главата, така че във всеки един момент главата е с изглед към една клетка.
3. Управляващият устройство (CU), който във всеки миг е в определено състояние. Броят на държавите, е ограничен. Един от щатите се нарича финала.
Наборът от символи, които са написани на информационната пояс 1, S2, ...., Sm>, да направи външната азбука MT.
Където S1 съответства на празен символ.
Комплектът на състояния, които могат да бъдат W е означен 1, q2, ..., QN>. един ще съответства по същество Допълнителни състояния, при които МТ се спира.
В допълнение, CU генерира три отборите на движението на лентата: R, L, H, където
P - проучване на съседната дясната клетка;
L - наляво, за да се проучат съседна клетка;
H - продължи да наблюдава една и съща клетка.
Машина работа е свършена в дискретно време. По всяко време, MT, докато в състояние на чи. проучвания на символа на лента Sk. след това продължава да се посочи QJ. Sk Sl замества от характера и се движи лентата (или не) на една клетка.
Readhead и устройство за контрол образуват логическо устройство. което представлява (2,3) - -pole.
чи Sk QJ Sl Р (А, Н)
По този начин, командата пет символа MT изчислява по формулата: Чи. Sk. QJ, Сл. P и LB е по същество държавна машина.
MT структура е както следва:
Q - клетъчни магазини статус символ, P - символ на срязване - клетка. В тях има забавяне символ данни преди началото на следващата мярка.
Като първоначална информация на лентата може да се подава всеки краен азбука последователност от крайната U. Ако след краен брой такта MT спира хранене сигнал да спре, и се оказва на информация лента B, тогава ние казваме, че машината се отнася и до U последователност и го преобразува в последователност от Б.
Ако стоп-сигнал да спре и никога не дойде, тогава ние казваме, че MTne последователност се прилага за U.
Вземем примера на функционирането на добавяне MT на две числа, които ще бъдат представени като съвкупност от единици.
Външно азбука се състои от символите където Ù - нулев характер.
Вътрешен азбука ще се състои от четири знака 1. Q2. q3.>, където Q1 на символ е първоначалното състояние, както добре. - крайното състояние.
Да предположим, че на касетата е записана първоначалната информация:
Свързани статии