О вычислениях, машинах Тьюринга и других интересных вещах. Part 2

По материалам Марвина Мински “Вычисления и автоматы”.

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

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

Эквивалентность конечного автомата "нейронной сети"

В книге Марвина Минского «Вычисления и автоматы» наткнулся на одну интересную теорему: «всякая конечная машина эквивалентна некоторой нейронной сети и может быть «смоделирована» ею». Суть заключается в том, что для любой конечной машины можно составить эквивалентную ей нейронную сеть, но это не самое замечательное. Интерес представляет универсальный метод построения нейронной сети по автомату!

Рассмотрим данную задачу на примере. Для начала определимся с терминологией. Раз за основу взята книжка Минского, то воспользуемся определениями из неё. Конечные автоматы это такие машины, которые переходят чётко разграниченными шагами из одного состояния в другое, причём оба этих набора принадлежат к некоторому конечному набору. Конечный автомат можно рассматривать как «чёрный ящик», который характеризуется определённой величиной (обобщённое состояние), Это обобщённое состояние изменяется в соответствии с предыдущими состояниями и входным сигналом (т.е. средой). С другой стороны данную машину можно представить как структуру, состоящую из отдельных элементов. Зная логику работы и связи между элементами, мы можем сказать, как эта система будет работать.