Всего на сайте:
236 тыс. 713 статей

Главная | Информатика

Всякий алгоритм может быть задан посредством МТ  Просмотрен 65

[E42]

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

[E43]

Этот тезис не является теоремой, его нельзя доказать, поскольку он представляет собой утверждение о понятии алгоритма, которое не является точным математическим понятием. По существу, тезис Тьюринга — гипотеза, предположение. На чем же основана уверенность в справедливости этого предположения? Главным образом, на опыте. Все известные в математике алгоритмы могут быть заданы посредством МТ. Но содержание тезиса Тьюринга обращено не только в прошлое. Оно содержит и прогноз на будущее: всякий раз, когда в будущем какое-либо предписание будет признано алгоритмом, его можно будет также задать посредством МТ.

 

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

Примеры таких классов задач.

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

А если рассмотреть уравнение с двумя или многими неизвестными?

Существует ли алгоритм, позволяющий по произвольному уравнению с целыми коэффициентами выяснить, имеет оно целочисленное решение или нет?

[E44] Эта задача была поставлена еще в 1901 году известным немецким математиком Д. Гильбертом (десятая проблема Гильберта) среди других проблем, которые, по его словам, XIX век передал в наследство XX. Вначале поиски математиков были направлены на нахождение алгоритма, но требуемый алгоритм так и не был найден. И лишь в 1970 году молодой советский математик Ю. В. Матиясевич доказал, что такого алгоритма не существует. Доказать это утверждение, пользуясь только интуитивным понятием алгоритма, было бы невозможно, ибо в таком случае не ясно, несуществование чего нужно доказывать. Имея же математическое уточнение понятия алгоритма, можно доказывать несуществование алгоритма. Несуществование алгоритма понимается, например, как несуществование машины Тьюринга, обладающей нужным свойством.

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

Существует ли алгоритм, позволяющий по любому ассоциативному исчислению выяснить, разрешима в нем проблема эквивалентности слов или нет?

[E45] А. А.

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

Определение нормального алгоритма выделяет во множестве всевозможных алгоритмов подмножество алгоритмов специального вида — класс нормальных алгоритмов.

Оказалось, что класс алгоритмов в форме машин Тьюринга и класс нормальных алгоритмов совпадают, эти алгоритмы равносильны.

[E46] (Два алгоритма В и С, исходные объекты которых закодированы словами в алфавите А, называются равносильными, если для любого слова Р в алфавите А результат работы этих алгоритмов над словом Р есть одно и то же слово).

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

[E47]

В этом смысле две математические теории алгоритмов: теория нормальных алгоритмов и теория машин Тьюринга, считаются эквивалентными (равносильными).

[E48]

Литература:

1. Макаренков Ю.А., Столяр А.А. Что такое алгоритм? Беседы со старшеклассниками. Мн.: Народна асвета, 1989.

2. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 2-е изд., исправленное. М.: МЦНМО, 2002, 192 с.

[E1]

5-Слайд 2

[E2]

5-Слайд 3

[E3]

5-Слайд 4

[E4]

5-Слайд 5

[E5]

5-Слайд 6

[E6]

5-Слайд 7

[E7]

5-Слайд 8

[E8]

5-Слайд 9

[E9]

5-Слайд 10

[E10]

5-Слайд 11

[E11]

5-Слайд 12

[E12]

5-Слайд 13

[E13]

5-Слайд 14

[E14]

5-Слайд 15

[E15]

5-Слайд 16

[E16]

5-Слайд 17

[E17]

5-Слайд 18

[E18]

5-Слайд 19

[E19]

5-Слайд 20

[E20]

5-Слайд 21

[E21]

5-Слайд 22

[E22]

5-Слайд 23

[E23]

5-Слайд 24

[E24]

5-Слайд 25

[E25]

5-Слайд 26

[E26]

5-Слайд 27

последний

[E27]

6 - Машина Тьюринга.ppt

Слайд 1

[E28]

6-Слайд 2

[E29]

6-Слайд 3

 

[E30]6-Слайд 4

[E31]

6-Слайд 5

[E32]

6-Слайд 6

 

[E33]6-Слайд 7

[E34]

6-Слайд 8

[E35]

6-Слайд 9

[E36]

6-Слайд 10

[E37]

6-Слайд 11

[E38]

6-Слайд 12

[E39]

6-Слайд 13

[E40]

6-Слайд 14

[E41]

6-Слайд 15

[E42]

6-Слайд 16

[E43]

6-Слайд 17

[E44]

6-Слайд 18

[E45]

6-Слайд 19

[E46]

6-Слайд 20

[E47]

6-Слайд 21

[E48]

6-Слайд 22

Предыдущая статья:Задачи. Следующая статья:Дальние пределы человеческой психики, Маслоу Абрахам Гарольд. 1 страница
page speed (0.1801 sec, direct)