Вычислимые по Тьюрингу функции

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 3Следующая ⇒

Применение МТ к словам

Задача 1: Дана МТ с внешним алфавитом А = {0, 1}, Q = {q₀, q₁} и программой d: q₁0→q₂0П; q₂0→q₀1; q₁1→q₁1П; q₂1→q₂1П. В какое слово переработает МТ слово a = 101 из СНП?

Решение. Изобразим работу МТ с помощью ленты:

…

0

1

0

q₁ 1

0

…

1)  начальная конфигурация: в состоянии q₁ обозревается крайняя правая непустая ячейка, то есть ячейка, в которой записана правая крайняя 1 данного слова. Выполняется команда (3), которая начинается с пары q₁1. В состоянии q₁ вижу символ 1, меняю символ 1 на символ 1, перехожу вправо на одну ячейку, меняю состояние на q₁.

…

0

1

0

1

q₁ 0

…

2) вторая конфигурация: в состоянии q₁ обозревается символ 0. Выполняется команда (1), которая начинается с пары q₁0. В состоянии q₁ вижу 0, меняю символ 0 на символ 0, двигаюсь вправо на одну ячейку, перехожу в состояние q₂.

…

0

1

0

1

0

q₂0

…

3) третья конфигурация: в состоянии q₂ обозревается символ 0. Выполняется команда (2), которая начинается с пары q₂0. В состоянии q₂ вижу символ 0, меняю 0 на символ 1, остаюсь на месте, меняю состояние на q₀.

…

0

1

0

1

0

q₀1

…

4) заключительная конфигурация: то есть слово a = 101 переработалось в слово b = 10101.

Полученную последовательность конфигураций можно записать более коротким способом: 10q₁1→101q₁0→1010q₂0→1010q₀1. В этом способе пустые символы вне слова записываются только тогда, когда в них возникает потребность (когда машина выходит за пределы данного непустого слова). Этот способ записи короче предыдущего, но не удобен для проверки. Гораздо удобнее вариант, когда каждая следующая конфигурация записывается под предыдущей. Например, покажем решение задачи для слова a = 101011:

10101q₁1 «В состоянии q₁ вижу 1, меняю 1 на 1, двигаюсь вправо, меняю состояние на q₁»

101011q₁0 «В состоянии q₁ вижу 0, меняю 0 на 0, двигаюсь вправо, меняю состояние на q₂»

1010110q₂0 «В состоянии q₂ вижу 0, меняю 0 на 1, остаюсь на месте, меняю состояние на q₀»

1010110q₀1 – это заключительная конфигурация.

При записи каждой следующей конфигурации поступаем так: сначала записываем новый символ (на который меняется обозреваемый), затем символ, через который перешагиваем (при движении вправо – это тот символ, который мы изменяли), затем новое состояние и затем переписываем все оставшиеся символы (крайние пустые символы при этом можно не писать). При этом надо внимательно следить за тем, чтобы количество тех символов, которые не участвовали в работе на данном шаге, после выполнения шага не изменилось (не потерялись или не появились лишние символы).

Задача 2: МТ задана внешним алфавитом А = {0; 1; *}, Q = {q₀, q₁, q₂, q₃} и программой, которая может быть задана в виде таблицы:

q₁

q₂

q₃

q₁0Л

q₃1П

q₁0Л

q₂0Л

q₂1Л

q₃1П

*

q₀0

q₂*Л

q₃*П

то есть первая команда q₁0→q₁0Л, вторая команда q₂0→q₃1П и так далее.

В какие слова МТ переводит слова a₁ = 11*11 и a₂ = 11*1?

Решение. Запишем последовательность конфигураций при переработке первого слова:

11*1q₁1 «В состоянии q₁ вижу 1, меняю 1 на 0, перехожу влево, меняю состояние на q₂»

11* q₂10 «В состоянии q₂ вижу 1, меняю 1 на 1, двигаюсь влево, меняю состояние на q₂»

11q₂*10 «В состоянии q₂ вижу *, меняю * на *, двигаюсь влево, меняю состояние на q₂»

1q₂1*10 «В состоянии q₂ вижу 1, меняю 1 на 1, двигаюсь влево, меняю состояние на q₂»

q₂11*10 «В состоянии q₂ вижу 1, меняю 1 на 1, двигаюсь влево, меняю состояние на q₂»

q₂011*10 «В состоянии q₂ вижу 0, меняю 0 на 1, двигаюсь вправо, меняю состояние на q₃»

1q₃11*10 «В состоянии q₃  вижу 1, меняю 1 на 1, двигаюсь вправо, меняю состояние на q₃»

11q₃1*10 «В состоянии q₃  вижу 1, меняю 1 на 1, двигаюсь вправо, меняю состояние на q₃»

111q₃*10 «В состоянии q₃  вижу *, меняю * на *, двигаюсь вправо, меняю состояние на q₃»

111*q₃10 «В состоянии q₃  вижу 1, меняю 1 на 1, двигаюсь вправо, меняю состояние на q₃»

111*1q₃0 «В состоянии q₃  вижу 0, меняю 0 на 0, двигаюсь влево, меняю состояние на q₁»

111*q₁1 «В состоянии q₁ вижу 1, меняю 1 на 0, перехожу влево, меняю состояние на q₂»

111q₂*0 «В состоянии q₂ вижу *, меняю * на *, двигаюсь влево, меняю состояние на q₂»

11q₂1*0 «В состоянии q₂ вижу 1, меняю 1 на 1, двигаюсь влево, меняю состояние на q₂»

1q₂11*0 «В состоянии q₂ вижу 1, меняю 1 на 1, двигаюсь влево, меняю состояние на q₂»

q₂111*0 «В состоянии q₂ вижу 1, меняю 1 на 1, двигаюсь влево, меняю состояние на q₂»

q₂0111*0 «В состоянии q₂ вижу 0, меняю 0 на 1, двигаюсь вправо, меняю состояние на q₃»

1q₃111*0 «В состоянии q₃  вижу 1, меняю 1 на 1, двигаюсь вправо, меняю состояние на q₃»

11q₃11*0 «В состоянии q₃  вижу 1, меняю 1 на 1, двигаюсь вправо, меняю состояние на q₃»

111q₃1*0 «В состоянии q₃  вижу 1, меняю 1 на 1, двигаюсь вправо, меняю состояние на q₃»

1111q₃*0 «В состоянии q₃  вижу *, меняю * на *, двигаюсь вправо, меняю состояние на q₃»

1111*q₃0 «В состоянии q₃  вижу 0, меняю 0 на 0, двигаюсь влево, меняю состояние на q₁»

1111q₁* «В состоянии q₁ вижу *, меняю * на 0, меняю состояние на q₀  и останавливаюсь»

1111q₀0 – заключительная конфигурация.

Таким образом, слово a₁ = 11*11 было преобразовано в слово b = 1111.

При переработке слов фразы в кавычках проговариваются, но не записываются. В следующем примере попробуйте по записанной конфигурации произнести требуемую фразу самостоятельно:

11*q₁1

11q₂*0 (так как крайний пустой символ может не записываться, то в следующих конфигурациях писать его не будем)

1q₂1*

q₂11*

q₂011*

1q₃11*

11q₃1*

111q₃*

111*q₃0

111q₁*

111q₀0

Таким образом, слово a₂ = 11*1 переработалось в слово b = 111. Можно сделать предположение, что данная МТ выполняет сложение натуральных числе в единичной системе счисления. Убедитесь в этом, выполнив преобразования нескольких других слов.

Конструирование МТ

Сконструировать МТ – значит написать ее программу. В этом процессе 4 этапа:

1) сначала создается алгоритм вычисления значений функции;

2) алгоритм записывается на языке МТ;

3) записанная программа проверяется (в том числе на граничных значениях);

4) если не программа работает не для всех проверенных слов, то осуществляется модификация (доработка) программы.

Задача 3: Построить МТ, которая из п записанных подряд единиц оставляла бы на ленте (п – 2) единицы, также записанные подряд, если п ≥ 2, и работала бы вечно, если п = 0 или п = 1.

Решение. 1 этап. Для решения задачи достаточно, если МТ из СНП, двигаясь влево, сотрет две из записанных единиц и после этого остановится.

2 этап. Начнем решать задачу для п ≥ 2. Зададим внешний алфавит А = {0, 1}, и первоначальный алфавит внутренних состояний Q = {q₀, q₁}, который в процессе решения задачи может дополняться другими состояниями.

Начальная конфигурация . Сотрем первую обозреваемую 1 (заменим ее на 0), сдвинемся на одну ячейку влево и перейдем в новое состояние q₂. Если мы не перейдем в новое состояние, то машина будет заменять единицы на нули до тех пор, пока единицы не кончатся. Соответствующая команда имеет вид: q₁1→q₂1Л

Получим следующую конфигурацию . Теперь машина должна стереть вторую единицу и остановиться. Запишем нужную команду: q₂1→q₀0. Полученная заключительная конфигурация имеет вид  и удовлетворяет условию задачи.

Теперь опишем случаи п = 0 и п = 1. Для случая п = 0 в состоянии q₁ МТ обозревает ячейку, в которой записан 0. Следовательно, чтобы работать вечно, машина должна двигаться вправо или влево, оставаясь все время в состоянии q₁ (так как п = 0, то на ленте записаны только пустые символы). Соответствующая команда имеет вид q₁0→q₁0П(Л).

Для случая п = 1 начальная конфигурация имеет вид 0q₁1. Тогда в состоянии q₂ на следующем шаге работы программы машина будет обозревать ячейку, в которой находится 0. Так как теперь на ленте нет ни одного непустого символа (единственную 1 мы стерли на предыдущем шаге), то мы можем поступить одним из следующих способов: 1) перейти к состоянию q₁ (как в случае с п = 0) или 2) оставаясь в состоянии q₂, двигаться влево или вправо по ленте, ничего не меняя. То есть выбрать одну из следующих команд: q₂0→q₂0П; q₂0→q₂0Л; q₂0→q₁0П; q₂0→q₁0Л.

Теперь все составленные команды запишем в программу с помощью таблицы:

q₁

q₂

q₁0П

q₁0П

q₂0Л

q₀0

3 этап. Проверяем работу программы. В качестве проверочных слов возьмем: a₁ = 11, a₂ = 11111, a₃ = 1 и a₄ = 0.

Начальная конфигурация

1q₁1

111q₁1

q₁1

q₁0

1 шаг

q₂10

11q₂10

q₂00

0q₁0

2 шаг

q₀00

11q₀00

0q₁0

00q₁0

3 шаг

…

…

Таким образом, проверка показала, что при наименьшем числе (п = 2), при произвольно взятом числе (п = 5) и при крайних значениях работа построенной машины удовлетворяет условию задачи. Следовательно, считаем, что задача решена верно (пока не будет доказано обратное).

Функция называется вычислимой по Тьюрингу, если существует МТ, ее вычисляющая, то есть такая МТ, которая вычисляет ее значения для тех наборов значений аргументов, для которых функция определена, и работающая вечно, если функция для данного набора значений аргументов не определена.

Для того, чтобы определение стало до конца точным, необходимо выполнение следующих условий:

1) Считают, что речь идет о функциях (или частичных функциях, то есть не всюду определенных), заданных на множестве N и принимающих значения также из N.

2) Необходимо договориться о том, как записывать на ленте МТ значения х₁, х₂, … , х_п аргументов функции f(х₁, х₂, … , х_п), из какого положения начинать переработку исходного слова и в каком положении получать значения функции.

Договоримся поступать следующим образом:

Значения аргументов х₁, х₂, … , х_п будем располагать на ленте в виде следующего слова: . Для  обозначим  и . Дополнительно полагаем:  – пустое слово. Так что на слова 1⁰ = L, 1¹ = 1, 1² = 11, 1³ = 111, ... будем смотреть как на «изображения» натуральных чисел 0, 1, 2, 3, ... соответственно. Таким образом, предыдущее слово a можно представить следующим образом: . Далее, начинать переработку данного слова будем из стандартного начального положения, т. е. из положения, при котором в состоянии q₁, обозревается крайняя правая единица записанного слова. Если функция f(х₁, х₂, … , х_п) определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд f(х₁, х₂, … , х_п) единиц; в противном случае машина должна работать бесконечно. При выполнении всех перечисленных условий будем говорить, что машина Тьюринга вычисляет данную функцию. Таким образом, сформулированное в начале пункта определение становится абсолютно строгим.

Обратимся к примерам. Нетрудно понять, что машина Тьюринга из задачи 1 по существу вычисляет функцию f(х) = х + 1, а машина Тьюринга из задачи 3 вычисляет функцию f(х) = х – 2.

Задача 4. Построим машину Тьюринга, вычисляющую функцию f(х) = х/2. Эта функция не всюду определена: областью ее определения является лишь множество всех четных чисел. Поэтому, учитывая определение, нужно сконструировать такую машину Тьюринга, которая при подаче на ее вход четного числа давала бы на выходе половину этого числа, а при подаче нечетного – работала бы неограниченно долго.

Сконструировать машину Тьюринга – значит написать (составить) ее программу. В этом процессе четыре этапа: сначала создается алгоритм вычисления значений функции, затем он записывается на языке машины Тьюринга (программируется); после составления программы происходит ее проверка и, если необходимо – модификация (улучшение) программы.

В качестве внешнего алфавита возьмем двухэлементное множество А = {0, 1}. В этом алфавите натуральное число х изображается словом 11... 1, состоящим из х единиц, которое на ленте машины Тьюринга записывается в виде х единиц, стоящих в ячейках подряд. Работа машины начинается из стандартного начального положения: 01... 1q₁10 (число единиц равно х).

Сделаем начало вычислительного процесса таким: машина обозревает ячейки, двигаясь справа налево, и каждую вторую единицу превращает в 0. Такое начало обеспечивается следующими командами:

(1): q₁1→q₂1Л;

(2): q₂1→q₁0Л;

(3): q₂0→q₂0Л.

Если число х единиц нечетно, то машина продолжит движение по ленте влево неограниченно, т. е. будет работать бесконечно. Если же число х единиц четно, то в результате выполнения команд создается конфигурация q₂0010101... 01010, в которой число единиц равно х/2. Остается сдвинуть единицы так, чтобы между ними не стояли нули. Для осуществления этой процедуры предлагается следующий алгоритм. Будем двигаться по ленте вправо, ничего на ней не меняя, до первой единицы и перейдем за единицу. Передвижение осуществляется с помощью следующих команд:

(4): q₁0→q₃0П;

(5): q₃0→q₃0П;

(6): q₃1→q₄1П.

В результате их выполнения получим конфигурацию 001q₄010101 ... 010100.(*)

Заменим 0, перед которым остановились, на 1 и продвинемся вправо до ближайшего 0:

(7): q₄0→q₅1П;

(8): q₅1→q₅1П.

Получим конфигурацию 00111q₅0101... 010100, в которой правее обозреваемой ячейки записаны «пары» 01, ..., 01. Кроме того, на ленте одна единица записана лишняя. Продвинемся по ленте вправо до последней «пары» 01. Это можно сделать с помощью своеобразного цикла:

(9): q₅0→q₆0П;

(10): q₆1→q₅1П.

Получим конфигурацию 001110101 ...01010q₆00. Двигаться дальше вправо бессмысленно. Вернемся на две ячейки назад и заменим единицу из последней «пары» 01 на ноль:

(11): q₆0→q₇0Л;

(12): q₇0→q₇0Л;

(13): q₇1→q₈0Л.

Получим конфигурацию 001110101 ...01q₈00. Число единиц на ленте снова равно х/2. Продвинемся влево на одну ячейку с помощью команды

(14): q₈0→q₉0Л.

В результате чего получим конфигурацию 001110101 ...010 q₉10. Теперь уничтожим самую правую единицу и продвинемся по ленте влево до следующей единицы:

(15): q₉1→q₁₀0Л;

(16): q₁₀0→q₁₀0Л. Получим конфигурацию 001110101 ... 0 q₁₀100 (**), в которой левее обозреваемой ячейки записана серия пар 10, 10, ..., 10 (если читать справа налево). Теперь на ленте недостает одной единицы, т. е. число единиц равно (х/2) - 1. Продвинемся по ленте влево до последней «пары» 10. Это можно сделать с помощью цикла

(17): q₁₀1→q₁₁1Л;

(18): q₁₁0→q₁₀0Л,

выполнив который, придем к следующей конфигурации: 001q₁₁110101...0100. Вернемся вправо к ближайшему нулю и превратим его в единицу:

(19): q₁₁1→q₁₂1П;

(20): q₁₂1→q₁₂1П;

(21): q₁₂0→q₁₃1П.

Получим конфигурацию 001111q₁₃101 ... 0100, в которой число единиц снова равно х/2.

Если теперь перешагнем вправо по ленте через обозреваемую единицу и переведем машину в состояние q₄ помощью команды

(22): q₁₃1→q₄1П

то придем к следующей конфигурации: 0011111q₄01 ... 0100, которая по существу аналогична конфигурации (*). В результате программа зацикливается (становится циклической): снова ближайший 0 превращается в 1, а самая правая 1 – в 0, затем машина возвращается к самому левому нулю, оказываясь в начале следующего цикла, и т.д.

Как же завершается работа программы? В некоторый момент конфигурация будет иметь вид 00111... 1110q₁₀10. Выполнив команды (17), (18), придем к конфигурации 00111... q₁₁110100. Далее выполняются команды (19), (20), (21), что приводит к конфигурации: 00111... 111111q₁₃00. Остается остановить машину. Это делается с помощью команды

(23): q₁₃0→q₀0Л.

Заключительная конфигурация имеет вид: 00111... 1111q₀100. Запишем программу машины Тьюринга в табличной форме:

q₁

q₂

q₃

q₄

q₅

q₆

q₇

q₈

q₉

q₁₀

q₁₁

q₁₂

q₁₃

0

q₃0П

q₂0Л

q₃0П

q₅1П

q₆0П

q₇0Л

q₇0Л

q₉0Л

q₁₀0Л

q₁₀0Л

q₁₃1П

q₀0Л

1

q₂1П

q₁0Л

q₄1П

q₅1П

q₅1П

q₈0Л

q₁₀0Л

q₁₁1Л

q₁₂1П

q₁₂1П

q₄1П

Проверим работу машины для слова a₁ = 0110.

01q₁10

0q₂110

q₁0010

0q₃010

00q₃10

001q₄0

0011q₅0

00110q₆0

0011q₇0

001q₇10

00q₈10 и на этом шаге мы обнаруживаем, что ситуация не предусмотрена программой. На ленте записано число, в два раза меньше исходного и на следующем шаге машина должна закончить работу. Дополним программу машины командой q₈1→q₀1.

Предлагается самостоятельно проследить за работой этой машины Тьюринга, взяв в качестве исходных конкретные слова: 111, 1111, 111111, 1111111111.

Видим, что дальнейшая проверка показала отсутствие противоречий в работе программы, поэтому окончательно программа машины имеет вид:

q₁

q₂

q₃

q₄

q₅

q₆

q₇

q₈

q₉

q₁₀

q₁₁

q₁₂

q₁₃

0

q₃0П

q₂0Л

q₃0П

q₅1П

q₆0П

q₇0Л

q₇0Л

q₉0Л

q₁₀0Л

q₁₀0Л

q₁₃1П

q₀0Л

1

q₂1П

q₁0Л

q₄1П

q₅1П

q₅1П

q₈0Л

q₀1

q₁₀0Л

q₁₁1Л

q₁₂1П

q₁₂1П

q₄1П

Тезис Тьюринга (основная гипотеза теории алгоритмов).Вернемся к интуитивному представлению об алгоритмах. Напомним, одно из свойств алгоритма заключается в том, что он представляет собой единый способ, позволяющий для каждой задачи из некоего бесконечного множества задач за конечное число шагов найти ее решение.

На понятие алгоритма можно взглянуть и с несколько иной точки зрения. Каждую задачу из бесконечного множества задач можно выразить (закодировать) некоторым словом некоторого алфавита, а решение задачи – каким-то другим словом того же алфавита. В результате получим функцию, заданную на некотором подмножестве множества всех слов выбранного алфавита и принимающую значения в множестве всех слов того же алфавита. Решить какую-либо задачу – значит найти значение этой функции на слове, кодирующем данную задачу. А иметь алгоритм для решения всех задач данного класса – значит иметь единый способ, позволяющий в конечное число шагов «вычислять» значения построенной функции для любых значений аргумента из ее области определения. Таким образом, алгоритмическая проблема – по существу, проблема о вычислении значений функции, заданной в некотором алфавите. Остается уточнить, что значит уметь вычислять значения функции. Это значит вычислять значения функции с помощью подходящей машины Тьюринга. Для каких же функций возможно их тьюрингово вычисление? Многочисленные исследования ученых, обширный опыт показали, что такой класс функций чрезвычайно широк. Каждая функция, для вычисления значений которой существует какой-нибудь алгоритм, оказывалась вычислимой посредством некоторой машины Тьюринга. Это дало повод Тьюрингу высказать следующую гипотезу, называемую основной гипотезой теории алгоритмов, или тезисом Тьюринга:

Для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция является вычислимой по Тьюрингу, т. е. когда она может вычисляться на подходящей машине Тьюринга.

Это означает, что строго математическое понятие вычислимой (по Тьюрингу) функции является по существу идеальной моделью взятого из опыта понятия алгоритма. Данный тезис есть не что иное, как аксиома, постулат, выдвигаемый нами, о взаимосвязях нашего опыта с той математической теорией, которую мы под этот опыт хотим подвести. Конечно же данный тезис в принципе не может быть доказан методами математики, потому что он не имеет внутриматематического характера (одна сторона в тезисе – понятие алгоритма – не является точным математическим понятием). Он выдвинут исходя из опыта, и именно опыт подтверждает его состоятельность. Точно так же, например, не могут быть доказаны и математические законы механики; они открыты Ньютоном и многократно подтверждены опытом.

Впрочем, не исключается принципиальная возможность того, что тезис Тьюринга будет опровергнут. Для этого должна быть указана функция, которая вычислима с помощью какого-нибудь алгоритма, но невычислима ни на какой машине Тьюринга. Но такая возможность представляется маловероятной (в этом одно из значений гипотезы): всякий алгоритм, который будет открыт, может быть реализован на машине Тьюринга.

Машины Тьюринга и современные электронно-вычислительные машины.Изучение машин Тьюринга и практика составления программ для них закладывают фундамент алгоритмического мышления, сущность которого состоит в том, что нужно уметь разделять тот или иной процесс вычисления или какой-либо другой деятельности на простые составляющие шаги. В машине Тьюринга расчленение (анализ) вычислительного процесса на простейшие операции доведено до предельной возможности: распознавание единичного рассмотренного вхождения символа, перемещение точки наблюдения данного ряда символов в соседнюю точку и изменение имеющейся в памяти информации. Конечно, такое мелкое дробление вычислительного процесса, реализуемого в машине Тьюринга, значительно его удлиняет. Но вместе с тем логическая структура процесса, расчлененного, образно выража­ясь, до атомарного состояния, значительно упрощается и предстает в некотором стандартном виде, весьма удобном для теоретических исследований. (Именно такое расчленение на простейшие составляющие вычислительного процесса на машине Тьюринга дает еще один косвенный аргумент в пользу тезиса Тьюринга, обсуждавшегося в предыдущем пункте: всякая функция, вычисляемая с помощью какого-либо алгоритма, может быть вычислена на машине Тьюринга, потому что каждый шаг данного алгоритма можно расчленить на еще более мелкие операции, которые реализуются в машине Тьюринга.) Таким образом, понятие машины Тьюринга есть теоретический инструмент анализа алгоритмического процесса, а значит, анализа существа алгоритмического мышления.

В современных ЭВМ алгоритмический процесс расчленен не на столь мелкие составляющие, как в машинах Тьюринга. Наоборот, создатели ЭВМ стремятся к известному укрупнению выполняемых машиной процедур (на этом пути, конечно, есть свои ограничения). Так, для выполнения операции сложения на машине Тьюринга составляется целая программа, а в современной ЭВМ такая операция является простейшей.

Далее, машина Тьюринга обладает бесконечной внешней памятью (неограниченная в обе стороны лента, разбитая на ячейки). Но ни в одной реально существующей машине бесконечной памяти быть не может. Это говорит о том, что машины Тьюринга отображают потенциальную возможность неограниченного увеличения объема памяти современных ЭВМ.

Наконец, можно провести более подробный сравнительный анализ работы современной ЭВМ и машины Тьюринга. В большинстве ЭВМ принята трехадресная система команд, обусловленная необходимостью выполнения бинарных операций, в которых участвует содержимое сразу трех ячеек памяти. Например, число из ячейки а умножается на число из ячейки b, и результат отправляется в ячейку с. Существуют ЭВМ двухадресные и одноадресные. Так, одноадресная ЭВМ работает следующим образом: вызывается (в сумматор) число из ячейки а; в сумматоре происходит, например, умножение этого числа на число из ячейки b, результат отправляется из сумматора в ячейку с. Машину Тьюринга можно считать одноадресной машиной, в которой система одноадресных команд упрощена еще больше: на каждом шаге работы машины команда предписывает замену лишь единственного знака, хранящегося в обозреваемой ячейке, а адрес обозреваемой ячейки при переходе к следующему такту может меняться лишь на единицу (обозрение соседней справа или слева ячейки ленты) или не меняться вовсе. Это удлиняет процесс, но в то же время резко унифицирует его, делает стандартным.

Подводя итоги, можно сказать, что современные ЭВМ есть некие реальные физические модели машин Тьюринга, огрубленные с точки зрения теории, но созданные в целях реализации конкретных вычислительных процессов. В свою очередь, понятие машины Тьюринга и теория таких машин есть теоретический фундамент и обоснование современных ЭВМ.

⇐ Предыдущая123Следующая ⇒

Поделиться:

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров