[AI ⊂ TM] Машина Тьюринга и искусственный интеллект

[imbasoft]

[AI ⊂ TM]

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

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

Машина Тьюринга обладает бесконечной памятью, если взять нейросеть с бесконечной памятью, то она легко реализует подобную Тьюринг Машину.

Таким образом, исходное утверждение верно не до конца. В тоже время и написать AI = ТМ тоже нельзя, так как это всё равно что сравнить кирпич с комфортным жильём.

[supremum76]

Да, имеется ввиду только ML. Экспертные продукционные системы и др. за рамками.

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

Возьмем мощную по потенциальным возможностям архитектуру ИНС - полносвязную рекуррентную сеть. Мы можем менять веса синапсов, начальные состояния нейронов и кодирование входных данных.

Допустим сеть состоит из бесконечного количества нейронов и синапсов. Как настроены начальные веса ? Если случайным образом, то для приведения их к подходящему значению нам понадобится бесконечное количество действий. Синапсов то ведь бесконечно много. Ок, тогда пусть все начальные веса и состояния будут нулевыми. Но тогда это эквивалентно тому, что сеть конечная, но мы можем добавлять к ней новые нейроны и синапсы, пока сеть не начнет решать необходимую нам задачу.

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

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

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

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

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

---

Насчет "кирпич" vs "комфортное жилье". Комфорт здесь определяется наличием эффективных методов "обучения", программных библиотек и аппаратной поддержки. Если некое направление прямо сейчас не имеет всего этого, это не повод не развивать направление. Когда-то и нейросети не имели этого. Фрэнк Розенблатт начинал с одним паяльником.

Рассматриваемые здесь "мутанты" машины Тьюринга вполне могут использовать SIMD и CUDA. Дело только за отработанными методами оптимизации, удобными библиотеками и шаблонами сценариев использования.

[supremum76]

На базе нейросетей можно реализовать базовые элементарные логические элементы, такие как штрих Шефера и стрелку Пирса

Но кто организует порядок работы этих элементов ?

В статье предлагается вариант кодирования правил перехода нейронной сетью. То есть предлагаемый подход вполне может быть объединен с нейросетевым подходом, включать его как элемент базы.