Здравствуйте, 0x7be, Вы писали:

0>Сколько раз в жизни ты пропускал через себя формальное описание себя?

Обратитесь к классике: великий русский кибернетик Ф.М.Достоевский, "Представление и написание". Или как-то похоже эта монография называлась, вот не помню точно.

Здравствуйте, SomeOne_TT, Вы писали:

SO_>Да, близко по смыслу.
SO_>Симуляция окружения и причинно-следственных связей. На весьма небольшой промежуток времени, скажем, микросекунду.
SO_>Физические симуляции давно "захардкожены" в отдельные отделы мозга вроде мозжечка, а
SO_>все что выше постоянно прокручивает/оценивает окружающий-мир-через-микросекунду через выстроенную модель связей в
SO_>поисках несоответствий с тем, что происходит на самом деле.

Тут не очень понятно, как мозг с захардкоженной физической моделью может придумать что-то типа теории относительности, квантовой механики или теории струн. Особенно последнюю, которая основывается больше на абстрактной математике в 11 измерениях, чем на физике и экспериментах (теория струн вообще экспериментально подтверждена?). Вот это самое удивительное.
Тот факт, что компьютеры и мозг могут что-то запоминать, объяснять или моделировать — это не так удивительно, как умение предсказывать и придумывать новое. Это в основном касается математики и теоретической физики, открытия которые могут экспериментально подтвердиться только лишь через много лет.

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Это теорема о самоприменимости алгоритмов. Под самоприменимостью здесь подразумевается способность алгоритма корректно отработать в ситуации, когда входными данными для него является его собственное формальное описание.

Если компилятор может собрать сам себя из своих исходников — это самоприменимость?

Здравствуйте, kov_serg, Вы писали:

_>Если компилятор может собрать сам себя из своих исходников — это самоприменимость?

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

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

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

Здравствуйте, kochetkov.vladimir, Вы писали:

я правильно понял что из самоприменимости и самосознания взята приставка 'само' и из этого построены все, кхм, 'рассуждения'? Или как связаны самоприменимость (читай — исполнение алгоритма) с самосознанием ( читай — анализ алгоритма ) ?

Здравствуйте, antropolog, Вы писали:

A> как связаны самоприменимость (читай — исполнение алгоритма) с самосознанием ( читай — анализ алгоритма ) ?

Проблема самоприменимости -- про анализ алгоритма, а не про его исполнение (см. выше мой предыдущий ответ kov_serg).

Здравствуйте, kochetkov.vladimir, Вы писали:

k> Посередине между теоремой останова и теоремой Райса находится ещё одна теорема, чуть более общая, чем первая и чуть менее, чем вторая. Это теорема о самоприменимости алгоритмов. Под самоприменимостью здесь подразумевается способность алгоритма корректно отработать в ситуации, когда входными данными для него является его собственное формальное описание.
Я не понял что означает "корректно отработать"?

Здравствуйте, ·, Вы писали:

·>Я не понял что означает "корректно отработать"?

Отдать на выходе результат вычисления именно той функции, которую реализует алгоритм.

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>·>Я не понял что означает "корректно отработать"?
KV>Отдать на выходе результат вычисления именно той функции, которую реализует алгоритм.
Ну пусть алгоритм выдаёт ответ "42" для любого входа. Он корректно отработает?
Или если тебе не нравится настолько тривиальный алгоритм, тогда вот:

$ /usr/bin/sha512sum < /usr/bin/sha512sum
a13cf48b6857aa0c8b326b47f531134f6344deb6fbbbc78255fc420f7cac3f759842075751a56caf88990c6b4fd9a3d796e501dae0178b2d822218490dfaa044  -

Корректно?

Здравствуйте, ·, Вы писали:

·>Корректно?

Вот, вообще сейчас не понял, о чём ты и аргументом чему это должно служить

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>·>Корректно?
KV>Вот, вообще сейчас не понял, о чём ты и аргументом чему это должно служить
Я пытаюсь разобраться с понятием "корректно отработать". Ты говоришь, что это значит "Отдать на выходе результат вычисления именно той функции, которую реализует алгоритм."
Алгоритм "print 42" реализует функцию f(x) = 42 + x — x, вычисляющую результат всегда равный "42" вне зависимости от входа. В каких случаях такой алгоритм будет работать некорректно?

Здравствуйте, ·, Вы писали:

·>Алгоритм "print 42" реализует функцию f(x) = 42 + x — x, вычисляющую результат всегда равный "42" вне зависимости от входа. В каких случаях такой алгоритм будет работать некорректно?

С чего бы он реализовывал именно эту функцию? Как тогда объяснить, что при x = f(x + 1) этот "алгоритм" будет останавливаться?

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>·>Алгоритм "print 42" реализует функцию f(x) = 42 + x — x, вычисляющую результат всегда равный "42" вне зависимости от входа. В каких случаях такой алгоритм будет работать некорректно?
KV>С чего бы он реализовывал именно эту функцию?
Что значит "реализовывал"? Алгоритм либо работает, либо нет — т.е. выдаёт ровно те же ответы что и f при всех значениях x, либо нет.
Например, "print 43" ту же функцию не реализует.
Или даже хуже. Скажем:

if(isFermaTheoremCorrect(x))
 print 42
else
 print 43

, где isFermaTheoremCorrect(x) — возвращает false если найдены a,b,c,n < x удовлетворяющие теореме Ферма
— тоже реализует ровно ту же функцию, но доказать это несколько сложнее.

Да, одна и та же функция может быть реализована множеством алгоритмов, и наоборот один и тот же алгоритм может реализовывать множество функций.

KV>Как тогда объяснить, что при x = f(x + 1) этот "алгоритм" будет останавливаться?
Если я правильно понял твою запись, то хотя бы с помощью алгебры:

f(x) = 42 + x - x
f(f(x+1)) = f(42 + x+1 - x+1) = f(42) = 42 + 42 - 42 = 42

И естественно программа "print 42" выдаст точно такой же ответ, как и это аналитическое доказательсво.

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

Здравствуйте, ·, Вы писали:

·>Что значит "реализовывал"? Алгоритм либо работает, либо нет — т.е. выдаёт ровно те же ответы что и f при всех значениях x, либо нет.

Алгоритм реализует функцию f(x) = 42, эквивалентную приведённой тобой, но не являющуюся ею.

·>, где isFermaTheoremCorrect(x) — возвращает false если найдены a,b,c,n < x удовлетворяющие теореме Ферма
·>- тоже реализует ровно ту же функцию, но доказать это несколько сложнее.

Если isFermaTheoremCorrect частично рекурсивна -- это не "несколько сложнее", а невозможно доказать в принципе.

·>Если я правильно понял твою запись, то хотя бы с помощью алгебры:

И где эта алгебра в приведённом алгоритме?

·>Я просто пытаюсь свести твои рассуждения к формальным понятиям из теории алгоритмов. А ты оперируешь какими-то терминами без каких-то точных значений, и из них получаешь странные выводы.

Под корректной работой алгоритма подразумевается, что:

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

Так -- достаточно формально? И, повторю свой вопрос, какая посылка изначально привела к тем вопросам, которые ты задал?

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>·>Что значит "реализовывал"? Алгоритм либо работает, либо нет — т.е. выдаёт ровно те же ответы что и f при всех значениях x, либо нет.
KV>Алгоритм реализует функцию f(x) = 42, эквивалентную приведённой тобой, но не являющуюся ею.
А какая разница между "являться" и "быть эквивалентным"? Учти, даже то, что f(x) = 42 эквивалентна f(x) = 42 + x — x требует хоть и тривиального, но доказательства.

KV>·>, где isFermaTheoremCorrect(x) — возвращает false если найдены a,b,c,n < x удовлетворяющие теореме Ферма
KV>·>- тоже реализует ровно ту же функцию, но доказать это несколько сложнее.
KV>Если isFermaTheoremCorrect частично рекурсивна -- это не "несколько сложнее", а невозможно доказать в принципе.
Доказать возможно (и теорема Ферма была доказана!), но если ты намекаешь на Проблему Останова и Ко., то это о другом — написать алгоритм, который будет доказывать _любой_ алгоритм — невозможно. При этом заметь, что написать алгоритм, который в частности доказывает конкретно Теорему Ферма — возможно!

KV>·>Если я правильно понял твою запись, то хотя бы с помощью алгебры:
KV>И где эта алгебра в приведённом алгоритме?
Алгебры в алгоритме нет. Алгебра используется для построения доказательства функции.

KV>·>Я просто пытаюсь свести твои рассуждения к формальным понятиям из теории алгоритмов. А ты оперируешь какими-то терминами без каких-то точных значений, и из них получаешь странные выводы.
KV>Под корректной работой алгоритма подразумевается, что:
KV>а) алгоритм останавливается на всех элементах принадлежащих области определения реализуемой им функции (и только на них);
KV>б) любой полученный алгоритмом результат соответствует отображению, которое определяет реализуемая им функция.
KV>Так -- достаточно формально? И, повторю свой вопрос, какая посылка изначально привела к тем вопросам, которые ты задал?
Ок. Верно. Давай рассмотрим алгоритм "print 42". Он по обоим твоим пунктам удовлетворяет для функции f(x) = 42 + x — x. Так? Значит он корректно работает. Так?

Здравствуйте, ·, Вы писали:

KV>>Если isFermaTheoremCorrect частично рекурсивна -- это не "несколько сложнее", а невозможно доказать в принципе.
·>Доказать возможно (и теорема Ферма была доказана!)

Я вообще не про доказательство теоремы, это не имеет никакого значения Моё замечание про доказательство того, по какой именно ветке пойдёт предложенный тобой алгоритм с if'ом, т.е. того, реализует ли данный алгоритм первоначальную функцию. Это теорема Райса в чистом виде.

·>Алгебра используется для построения доказательства функции.

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

·>Ок. Верно. Давай рассмотрим алгоритм "print 42". Он по обоим твоим пунктам удовлетворяет для функции f(x) = 42 + x — x. Так? Значит он корректно работает. Так?

Пока ты не определил, какому множеству принадлежит x и какие отношения определены на этом множестве -- нет, не "так", а "хз как". Но он удовлетворяет функции f(x) = 42 без этой оговорки.

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>>>Если isFermaTheoremCorrect частично рекурсивна -- это не "несколько сложнее", а невозможно доказать в принципе.
KV>·>Доказать возможно (и теорема Ферма была доказана!)
KV>Я вообще не про доказательство теоремы, это не имеет никакого значения Моё замечание про доказательство того, по какой именно ветке пойдёт предложенный тобой алгоритм с if'ом, т.е. того, реализует ли данный алгоритм первоначальную функцию. Это теорема Райса в чистом виде.
Эта теорема говорит об алгоритмической неразрешимости, а не то, что "невозможно доказать в принципе". Не путай! Это очень разные понятия.

KV>·>Алгебра используется для построения доказательства функции.
KV>В результате которого мы получаем уже другую (эквивалентную исходной) функцию. В данном конкретном примере принципиальной разницы между "эквивалентна" и "является" нет, если допустить, что x принадлежит счётному множеству, на котором всюду определены используемые в функции арифметические операции (что в общем случае совершенно необязательно).
Ок, согласен. Надо уточнить что эти функции эквивалентны если они имеют одну и ту же область определения (что, вообще говоря, часто неявно подразумевается).

KV>·>Ок. Верно. Давай рассмотрим алгоритм "print 42". Он по обоим твоим пунктам удовлетворяет для функции f(x) = 42 + x — x. Так? Значит он корректно работает. Так?
KV>Пока ты не определил, какому множеству принадлежит x
Области определения функции. Например, пусть будет множество натуральных чисел, для определённости.

KV> и какие отношения определены на этом множестве
??

KV> -- нет, не "так", а "хз как". Но он удовлетворяет функции f(x) = 42 без этой оговорки.
Ок. Пойдём далее. Этот алгоритм корректно работает?

Здравствуйте, ·, Вы писали:

·>Эта теорема говорит об алгоритмической неразрешимости, а не то, что "невозможно доказать в принципе". Не путай! Это очень разные понятия.

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

·>Ок. Пойдём далее. Этот алгоритм корректно работает?

А просто сказать, к чему ты клонишь -- совсем никак, надо обязательно по шагам идти?

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

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

Здравствуйте, Nuzhny, Вы писали:

N>Тут не очень понятно, как мозг с захардкоженной физической моделью может придумать что-то типа теории относительности, квантовой механики или теории струн. Особенно последнюю, которая основывается больше на абстрактной математике в 11 измерениях, чем на физике и экспериментах (теория струн вообще экспериментально подтверждена?). Вот это самое удивительное.
N>Тот факт, что компьютеры и мозг могут что-то запоминать, объяснять или моделировать — это не так удивительно, как умение предсказывать и придумывать новое. Это в основном касается математики и теоретической физики, открытия которые могут экспериментально подтвердиться только лишь через много лет.

Тут интересный момент в том, что вся математика и физика объясняется через простые понятия и аналогии. И не для того, чтобы быть понятной новичкам, а потому что иначе никак. Вот взять ту же квантовую физику: там происходит внутри вообще черти что, но физика оперирует цветными кварками-частицами, спином-стрелочкой, симметрией, спутанными частицами и так далее понятиями, доступными нам на уровне ощущений и интуиции. Может ли вообще разум осознать сущности, незнакомые ему и недоступные через сенсорное восприятие мира? Сущности и процессы, которые не проецируются достаточно хорошо в наше пространство ощущений?

PS может, с темной материей как раз такая беда.

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>·>Эта теорема говорит об алгоритмической неразрешимости, а не то, что "невозможно доказать в принципе". Не путай! Это очень разные понятия.
KV>Мы же всё ещё о машинном разуме против человеческого? Потому как, если да, то у текущих машин нет возможности проводить доказательство как-либо, кроме решения некоей алгоритмической задачи
А про людей — неизвестно. Алгоритмы — это всего лишь мат-модель. Решил ли когда-либо человек хоть одну задачу, которая является алгоритмически неразрешимой — нет, конечно.

KV>·>Ок. Пойдём далее. Этот алгоритм корректно работает?
KV>А просто сказать, к чему ты клонишь -- совсем никак, надо обязательно по шагам идти?
Тезис "алгоритмы, решающие проблему самоприменимости, не могут существовать" — неверен, по крайней мере в терминологии как я её понял из твоих объяснений. Например, "print 42" это самоприменимый алгоритм — его можно применить к любому входу, в т.ч. к описанию самого себя и он так же корректно отработает.

KV>Неразрешимость всех упомянутых в исходном посте проблем имеет место для общего случая. Вопрос разрешимости в каждом конкретном случае необходимо решать отдельным доказательством. Что уже сделано, к примеру, для проблемы останова малых машин Тьюринга (с небольшим алфавитом и числом состояний и не являющихся при этом универсальными). Вот, только нынешний машинный "разум" не способен даже на то, чтобы самостоятельно выделить какое-либо множество частных случаев по заданному критерию и, тем более, построить на этом множестве доказательство заданного утверждения. В отличие от человека.
KV>Пример с самоприменимостью самосознания показался мне достаточно интересным для того, чтобы предложить обсудить его в т.ч. здесь. Но, даже если этот пример здесь "не в дугу", факта того, что человек, в отличие от нынешних машин, в состоянии решать частные случаи подобных неразрешимых задач (что возможно прямо сейчас здесь демонстрируешь ты, если я правильно понимаю, к чему был этот вопрос про 42), это никак не отменяет.
Ну так машины точно так же решают частные случаи неразрешимых задач, т.к. частные случаи не всегда являются неразрешимыми задачами. То что человек может решать задачи сложнее нынешних компьютеров не говорит о какой-то принципиальной разнице, ничего не доказывает.
Что такое самосознание — пока только вопросы. Скажем, когда операционка анализирует использование CPU и памяти и как-то управляет ресурсами на основании анализа? Это самосознание или ещё нет?