Машина Тьюринга - История изменений

Logic-samara в 13:03, 14 января 2024

2024-01-14T13:03:22Z

Fenikals: Снята защита с «Машина Тьюринга»

2017-05-28T13:06:23Z

Снята защита с «Машина Тьюринга»

Logic-samara в 16:49, 11 августа 2016

2016-08-11T16:49:42Z

Logic-samara в 09:55, 15 февраля 2016

2016-02-15T09:55:32Z

Logic-samara в 13:26, 14 февраля 2016

2016-02-14T13:26:46Z

Logic-samara в 13:25, 14 февраля 2016

2016-02-14T13:25:07Z

Logic-samara в 06:15, 14 февраля 2016

2016-02-14T06:15:58Z

Logic-samara в 18:08, 13 февраля 2016

2016-02-13T18:08:08Z

Logic-samara в 07:23, 12 февраля 2016

2016-02-12T07:23:52Z

Logic-samara в 08:47, 11 февраля 2016

2016-02-11T08:47:36Z

@@ Строка 1: / Строка 1: @@
 '''Машина Тьюринга''' (МТ) — это абстрактная вычислительная машина для выполнения программ, предложенная английским математиком Аланом Мэтисоном Тьюрингом в 1936 году.
 == Состав МТ ==
 МТ состоит из управляющего устройства (каретки или считывающей и записывающей головки) и ленты, разбитой на секции (ячейки) и бесконечной в обе стороны.
@@ Строка 11: / Строка 12: @@
 Работа МТ определяется программой, состоящей из конечного числа командных строк.
 == Виды команд: ==
-* сдвиг вправо
+*сдвиг вправо
-* сдвиг влево
+*сдвиг влево
-* остаться на месте
+*остаться на месте
-* запись символа алфавита в ячейку
+*запись символа алфавита в ячейку
-* перейти в состояние из множества
+*перейти в состояние из множества
 Введём обозначения:
@@ Строка 50: / Строка 51: @@
 После запуска программы на МТ возможны следующие варианты:
-* работа может закончиться если система переходит в терминальное (конечное) состояние;
+*работа может закончиться если система переходит в терминальное (конечное) состояние;
-* работа никогда не закончится (т.е.программа составлена не корректно).
+*работа никогда не закончится (т.е.программа составлена не корректно).
 == Пример задачи ==
 [[файл:МТ11.JPG]], где '''x''', '''y''' - неотрицательные целые числа.
@@ Строка 84: / Строка 85: @@
 Выходные данные: '''λ1<sub>0</sub>11'''.
-* Заметим, что [[машина Поста]] во многом аналогична машине Тьюринга.
+*Заметим, что [[машина Поста]] во многом аналогична машине Тьюринга.
-== Другие алгоритмы: ==
+== [[Алгоритм|Другие алгоритмы:]] ==
 {{Список Алг}}
-== Ссылки ==
+= [[Разделы математики|Другие разделы]] =
-* Википедия. Машина Тьюринга.
+= Ссылки =
-* [[Участник:Logic-samara]]
+*Википедия. Машина Тьюринга.
-[[Категория:Дискретная математика]][[Категория:Алгоритмы]]
+*[[Участник:Logic-samara]]

@@ Строка 86: / Строка 86: @@
 * Заметим, что [[машина Поста]] во многом аналогична машине Тьюринга.
 == Другие алгоритмы: ==
-*[[наибольший общий делитель]];
+{{Список Алг}}
-*[[наименьшее общее кратное]];
-*[[проверка кратности]];
-*[[деление по модулю]];
-*[[получение простых чисел]];
-*[[разложение на множители]];
-*[[система счисления]];
-*[[метод математической индукции]];
-*[[схема примитивной рекурсии]];
-*[[рекурсия]];
-*[[машина Поста]];
-*[[машина Тьюринга]];
-*[[Составление перестановок|комбинаторные алгоритмы]];
-*[[сортировка]];
-*[[алгоритм определения мест]].
 == Ссылки ==
 * Википедия. Машина Тьюринга.
 * [[Участник:Logic-samara]]
 [[Категория:Дискретная математика]][[Категория:Алгоритмы]]

@@ Строка 102: / Строка 102: @@
 *[[алгоритм определения мест]].
 == Ссылки ==
-* Википедия
+* Википедия. Машина Тьюринга.
 * [[Участник:Logic-samara]]
 [[Категория:Дискретная математика]][[Категория:Алгоритмы]]

@@ Строка 95: / Строка 95: @@
 *[[метод математической индукции]];
 *[[схема примитивной рекурсии]];
-*[[рекурсии]];
+*[[рекурсия]];
 *[[машина Поста]];
 *[[машина Тьюринга]];

@@ Строка 95: / Строка 95: @@
 *[[метод математической индукции]];
 *[[схема примитивной рекурсии]];
 *[[машина Поста]];
 *[[машина Тьюринга]];

← Предыдущая	Версия 13:06, 28 мая 2017
(нет различий)

@@ Строка 97: / Строка 97: @@
 *[[машина Поста]];
 *[[машина Тьюринга]];
-*[[составление перестановок]];
+*[[Составление перестановок|комбинаторные алгоритмы]];
-*[[составление лексикографических перестановок]];
-*[[составление сочетаний]];
-*[[составление лексикографических сочетаний]];
-*[[составление размещений]];
-*[[составление лексикографических размещений]];
-*[[составление разбиений]];
-*[[составление лексикографических разбиений]];
 *[[сортировка]];
 *[[алгоритм определения мест]].