Компьютерная лингвистика для всех - Мифы, Алгоритмы, Язык

"Также доказано, что любое удовлетворительное определение понятия истинности для объекта-языка конечного класса, содержащего арифметическую репрезентацию, может проявиться только в метаязыке высшего класса: представить противоположное - это значит так или иначе столкнуться с парадоксом типа "Лжец" (58). В 1931 г. логик К. Гедель доказал знаменитую теорему о неполноте. В ней утверждается, что любая непротиворечивая формальная теория, включающая арифметику целых чисел, неполна. Иначе говоря, в этой теории существует имеющее смысл утверждение, которое средствами самой теории невозможно ни доказать, ни опровергнуть. То, что с ужасом предчувствовали пифагорейцы, пытавшиеся весь мир свести к числам, свершилось. Модификацию парадокса "Лжец" используют и для доказательства существования алгоритмически неразрешимых проблем. Схема рассуждений в этом случае такова. Пусть имеется некоторый язык, в котором задаются алгоритмы. Предположим для простоты, что алгоритмы - это некоторые математические машины, перерабатывающие входную информацию в дискретные такты времени. Это могут быть машины Тьюринга или другие преобразователи. Такое

=====================================================

(58) Роулен де Филилп. Лжец.- С. 112.

=====================================================

предположение не нарушает общности. Язык определяет правила строгого описания таких машин. Проблема считается алгоритмически разрешимой, если существует алгоритм (машина, задаваемая в рассматриваемом языке), который за конечное число тактов работы отвечает на вопрос проблемы. В этом случае вместо человеческого "Я лгу" алгоритм заставляют "говорить" другие машинные варианты этой фразы, например "Я никогда не останавливаюсь", что означает, что при любом входе алгоритм работает бесконечно долго. Предполагая, что свойство "Я никогда не останавливаюсь" в классе всех алгоритмов распознаваемо каким-то конкретным алгоритмом, заставив этот алгоритм рассматривать самого себя, опять быстро получим ситуацию антиномии "Лжец". Отсюда следует, что такого алгоритма не существует, т. е. получим доказательство существования неразрешимости проверки некоторых свойств в классе алгоритмов. Затем из неразрешимости одной простой проблемы математики смогли получить доказательства неразрешимости других, более интересных и сложных математических проблем. Парадокс "Лжец" создает ситуацию, которую так любят писатели-фантасты. В рассказе "Лжец" американский писатель А. Азимов описывает неразрешимую ситуацию. Специалист по психологии роботов Сьюзен Кэлвин поставила перед роботом Эрби неразрешимую проблему. Решение ее приводило к нарушению первого закона робототехники: "Робот не может причинить вред человеку".

" - Ты не можешь сказать,- медленно повторяла Кэлвин,- потому что это их огорчит, а ты не должен их огорчать, Но если ты не скажешь, это тоже их огорчит, так что ты должен сказать. А если ты скажешь, ты их огорчишь, а ты не должен, так что ты не можешь сказать. Но если ты не скажешь, ты причинишь им вред, так что ты должен. Но если ты скажешь, ты причинишь вред, так что ты не должен. Но если ты не скажешь, ты..." (59).

В итоге Эрби, не выдержав, превратился в бесформенную кучу металла. Физиологов еще со времен Линнея волнует вопрос: в чем отличие мышления человека и животных? Сам Линней демонстративно признавал, что он не может указать черты, разделяющей человека и обезьяну.

=====================================================

(59) Азимов Л. Три закона робототехники // Сб. науч.-фантаст. рассказов (Пер. с англ.- И.:Мир, 1979.- С. 164 - 165.

=====================================================