2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Алгоритмическая неразрешимость теста Тьюринга?
Сообщение21.05.2021, 10:08 


02/05/18
14
В новелле Ся Цзя «Спокойной ночи, меланхолия», открывающей сборник «Сломанные звёзды. Новейшая китайская фантастика» и посвящённой взаимодействию ИИ с человеком, приводится следующий вымышленный диалог Алана Тьюринга с компьютерной программой:

Цитата:
Алан: Полицейские сказали, что из-за Алека мир наполнился говорящими машинами. Никто не мог отличить их от людей, настолько они были похожи. Существовал только один способ сделать это – проломить им головы и посмотреть, есть ли внутри бумажная лента. Но мы не можем проламывать головы людей, когда нам этого захочется. Возникла сложная ситуация.

Кристофер: Очень сложная.

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

Кристофер: Да, Алан.

Алан: Но возникла проблема. У полиции не было ресурсов и времени для того, чтобы опрашивать всех. Они спросили у Алека, есть ли способ создать умного судью-машину, который мог бы автоматически отделять машин от людей, задавая вопросы, и отделять их безошибочно. Это значительно облегчило бы жизнь полиции. Но Алек сразу ответил, что сделать такого механического судью невозможно. Знаешь почему?

Кристофер: Почему?

Алан: Алек объяснил это так. Предположим, что уже существует судья-машина, способный отделять говорящие машины от людей с помощью заданного числа вопросов. Чтобы упростить ситуацию, скажем, что необходимое число вопросов – сто, хотя на самом деле их может быть и десять тысяч, это не важно. Для машины не имеет значения, сто вопросов или десять тысяч. Предположим также, что первый вопрос судьи-машины выбран случайным образом из базы подобных вопросов, а следующий вопрос выбран в зависимости от ответа на первый вопрос, и так далее. Таким образом, каждый опрашиваемый столкнется с отдельным набором из ста вопросов, что, кроме всего прочего, устраняет возможность жульничать. Кажется ли тебе это справедливым, Кристофер?

Кристофер: Да, Алан.

Алан: Теперь предположим, что судья-машина A влюбился в человека C… Не смейся. Возможно, это звучит нелепо, но кто может утверждать, что машины не способны влюбляться в людей? Предположим, что этот судья-машина хочет жить со своим возлюбленным и для этого должен притвориться человеком. Как, по-твоему, он бы это сделал?

Кристофер: Как?

Алан: Очень просто. Предположим, что я – судья-машина A и я точно знаю, как допрашивать машину. И поскольку я машина, я буду знать, как допрашивать самого себя. Поскольку я заранее знаю, какие вопросы я задам и какие ответы меня выдадут, мне просто нужно подготовить сто ложных ответов. Это немалый труд, но легко выполнимый для судьи-машины A. Как ты считаешь, это хороший план?

Кристофер: Очень хороший, Алан.

Алан: Подумай еще. Что, если судью-машину A разоблачат и его будет допрашивать судья-машина B? Сможет судья-машина B определить, является ли судья-машина A машиной?

Кристофер: Прости, Алан. Я не знаю.

Алан: Точно! Правильный ответ: «Я не знаю». Если судья-машина B разгадал план судьи-машины A и решил в последний момент заменить вопросы, чтобы застать судью-машину A врасплох, то судья-машина A тоже мог бы предусмотреть такой ход со стороны судьи-машины B и подготовиться к новым вопросам. Поскольку судья-машина может отделить машины от людей, он не способен отделить сам себя. Это парадокс, Кристофер. Он показывает, почему придуманный полицией всемогущий судья-машина не может существовать.

Кристофер: Не может существовать?

Алан: Рассказав эту историю, Алек доказал полиции, что нет идеальной последовательности инструкций, которая могла бы безошибочно отделять людей от машин. Ты понимаешь, что это значит?

Кристофер: Что это значит?

Алан: Это значит, что невозможно найти идеальный набор механических правил, чтобы решить, шаг за шагом, все проблемы мира.


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

 Профиль  
                  
 
 Re: Алгоритмическая неразрешимость теста Тьюринга?
Сообщение21.05.2021, 19:52 


26/12/18
155
алгоритмическая неразрешимость с тестом Тьюринга ничего общего не имеет.

 Профиль  
                  
 
 Re: Алгоритмическая неразрешимость теста Тьюринга?
Сообщение21.05.2021, 20:05 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Видимо строгое утверждение тут будет такое: для любой функции $f$ и любого алгоритма $A$ с оракулом, если $A$ с оракулом $f$ выдает $1$, то существует вычислимая функция $g$ такая что $A$ с оракулом $g$ тоже выдает $1$. Довольно очевидная штука, вряд ли связанная с неразрешимостью.

 Профиль  
                  
 
 Re: Алгоритмическая неразрешимость теста Тьюринга?
Сообщение21.05.2021, 21:25 


02/05/18
14
Sycamore в сообщении #1519441 писал(а):
алгоритмическая неразрешимость с тестом Тьюринга ничего общего не имеет.
вы пост-то прочитали?

mihaild в сообщении #1519444 писал(а):
Видимо строгое утверждение тут будет такое: для любой функции $f$ и любого алгоритма $A$ с оракулом, если $A$ с оракулом $f$ выдает $1$, то существует вычислимая функция $g$ такая что $A$ с оракулом $g$ тоже выдает $1$.
да, пожалуй, это похоже
mihaild в сообщении #1519444 писал(а):
вряд ли связанная с неразрешимостью
видимо, должно вытекать что-то вроде неразрешимости распознавания свойства вычислимости произвольной функции по конечному набору возвращаемых ей значений?

 Профиль  
                  
 
 Re: Алгоритмическая неразрешимость теста Тьюринга?
Сообщение21.05.2021, 21:32 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
technocrator в сообщении #1519455 писал(а):
видимо, должно вытекать что-то вроде неразрешимости распознавания свойства вычислимости произвольной функции по конечному набору возвращаемых ей значений?
Это еще более очевидно, чем предыдущее утверждение - у любой вычислимой функции можно как угодно поменять значения на конечном множестве без потери вычислимости.

 Профиль  
                  
 
 Re: Алгоритмическая неразрешимость теста Тьюринга?
Сообщение22.05.2021, 01:10 


26/12/18
155
technocrator в сообщении #1519455 писал(а):
вы пост-то прочитали?
по-диагонали, ибо не думал, что чего-то интересного может подвернуться между неразрешимостью и тестом, интеллекта разрешимого не бывает, а также пределов скармливанию компам неразрешимых задач.

 Профиль  
                  
 
 Re: Алгоритмическая неразрешимость теста Тьюринга?
Сообщение22.05.2021, 07:48 


02/05/18
14
mihaild в сообщении #1519458 писал(а):
Это еще более очевидно
а можно ли это рассматривать в качестве отрицательного ответа на общую "проблему разрешения"? (аналогично проблеме остановки или другим известным алгоритмически нерешаемым задачам, например, десятой проблеме Гильберта)

 Профиль  
                  
 
 Re: Алгоритмическая неразрешимость теста Тьюринга?
Сообщение22.05.2021, 11:21 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
technocrator в сообщении #1519509 писал(а):
а можно ли это рассматривать в качестве отрицательного ответа на общую "проблему разрешения"?
Нет, нельзя. Этот отрицательный ответ - тривиальное следствие мощностных соображений, а проблема разрешения гораздо хитрее.

 Профиль  
                  
 
 Re: Алгоритмическая неразрешимость теста Тьюринга?
Сообщение22.05.2021, 13:42 


02/05/18
14
Хм, да, странно, автор в рассказе прямым текстом указывает, что высказанное в диалоге должно служить ответом на "проблему разрешения". И ощущение такое, что всё-таки имела в виду некую конкретную формально-математическую постановку, хотя не приводит её. Откуда она взялось, интересно было бы выяснить...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group