Тезис Черча-Тьюринга

[cscscs]

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

Итого, есть два варианта: либо одно из этих трех допущения не верно, либо вселенная действительно не является алгоритмом. Если второе, то это доказывает, что мы не живем в "матрице".

[Aritaborian]

Вся эта белиберда ни черта не доказывает.

cscscs в сообщении #823461 писал(а):

человек является алгоритмом.

Человек является организмом ;-)

cscscs в сообщении #823461 писал(а):

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

Что значит «вообще»? Лихо вы сюда бесконечность впихнули.

cscscs в сообщении #823461 писал(а):

для каждого конкретного человека существует такое конкретное конечное множество программ для которых он может решить проблему остановки.

А чем один человек в этом смысле отличается от другого?

cscscs в сообщении #823461 писал(а):

допустим, что все признанные на данный момент достижения математики не чушь.

Чертовски смелое допущение.

[cscscs]

Aritaborian в сообщении #823464 писал(а):

Человек является организмом

Хорошо. Человек однозначно описывается алгоритмом.

Aritaborian в сообщении #823464 писал(а):

Что значит «вообще»? Лихо вы сюда бесконечность впихнули.

Не в данный момент, а вообще. Т.е. и все те, что сейчас есть, и все те, что потенциально будут. Допустим, что это бесконечное множество.

Aritaborian в сообщении #823464 писал(а):

А чем один человек в этом смысле отличается от другого?

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

[Sonic86]

cscscs в сообщении #823461 писал(а):

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

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

cscscs в сообщении #823461 писал(а):

люди - это бесконечное множество алгоритмов

Все-таки люди - это материальные объекты, а не алгоритмы. Уточните соотношение.

cscscs в сообщении #823461 писал(а):

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

Очевидно неверно, противоречит алгоритмической неразрешимости проблемы остановки.

cscscs в сообщении #823461 писал(а):

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

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

cscscs в сообщении #823461 писал(а):

Вселенная создает людей. Является ли она алгоритмом?

Тоже сформулируйте формально, Вселенная, очевидно - не алгоритм.

-- Пт фев 07, 2014 15:12:14 --

cscscs в сообщении #823802 писал(а):

Хорошо. Человек однозначно описывается алгоритмом.

Все равно непонятно.

[arseniiv]

Добавлю немного повторений.

cscscs в сообщении #823461 писал(а):

Вселенная создает людей. Является ли она алгоритмом?

Ну, знаете ли, можно так же сказать, что она создаёт идеи или микроскопы. Уточните, что вы понимаете под «вселенная является алгоритмом», потому что в прямом смысле это быть понято точно не может: алгоритм — это математическое понятие, а Вселенная — как бы нет.

[Toucan]

Тема перемещена из форума «Дискуссионные темы (Гум)» в форум «Свободный полёт»
Причина переноса: слишком много необоснованных допущений.

[Joker_vD]

cscscs в сообщении #823461 писал(а):

Но, для конечного числа явно заданных программ, такой алгоритм указать можно.

Да ладно. Вот вам одна-единственная программа, для которой такого алгоритма нет:

На вход подается семь целочисленных квадратных матриц $A_1, A_2,\dots, A_7$ порядка 3. Программа перебирает все конечные произведения этих матриц, пока не получит нулевую матрицу.

[cscscs]

Я понял, что человека нельзя заменить алгоритмом. Человек - это не алгоритм и не может описываться алгоритмом. Поэтому третье допущение не верно.

Sonic86 в сообщении #823824 писал(а):

Если Вы хотите сформулировать модель, где число людей бесконечно, то пишите это явно.

Да, я это имел в виду.

Sonic86 в сообщении #823824 писал(а):

Очевидно неверно, противоречит алгоритмической неразрешимости проблемы остановки.

Нет же, неразрешимость проблемы остановки означает, что не существует алгоритма, который бы решал проблему остановки. Но это не значит, что никакое бесконечно число различных алгоритмов её не решают. Разве нет?

Sonic86 в сообщении #823824 писал(а):

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

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

Но это уже всё ерунда, потому что третье допущение не верно и я не алгоритм.

Sonic86 в сообщении #823824 писал(а):

Вселенная, очевидно - не алгоритм.

Да, потому что третье допущение не верно.

-- 08.02.2014, 02:05 --

arseniiv в сообщении #823837 писал(а):

Ну, знаете ли, можно так же сказать, что она создаёт идеи или микроскопы. Уточните, что вы понимаете под «вселенная является алгоритмом», потому что в прямом смысле это быть понято точно не может: алгоритм — это математическое понятие, а Вселенная — как бы нет.

Я имел в виду описывается алгоритмом. Но это уже не важно, потому что третье допущение не верно.

-- 08.02.2014, 02:07 --

Joker_vD в сообщении #823961 писал(а):

Вот вам одна-единственная программа, для которой такого алгоритма нет:

На вход подается семь целочисленных квадратных матриц $A_1, A_2,\dots, A_7$ порядка 3. Программа перебирает все конечные произведения этих матриц, пока не получит нулевую матрицу.

В данный момент нет, т.е. он еще не придуман? Или в принципе быть не может?

[patzer2097]

cscscs в сообщении #824008 писал(а):

В данный момент нет, т.е. он еще не придуман? Или в принципе быть не может?

в принципе быть не может, это известная алгоритмически неразрешимая the mortality problem

[warlock66613]

patzer2097 в сообщении #824017 писал(а):

в принципе быть не может, это известная алгоритмически неразрешимая the mortality problem

Но для конкретных матриц алгоритм ведь есть.

[Nemiroff]

warlock66613 в сообщении #824055 писал(а):

Но для конкретных матриц алгоритм ведь есть.

Да? А какой?

[Sonic86]

cscscs в сообщении #824008 писал(а):

Нет же, неразрешимость проблемы остановки означает, что не существует алгоритма, который бы решал проблему остановки. Но это не значит, что никакое бесконечно число различных алгоритмов её не решают. Разве нет?

Да, похоже, что отсюда это просто так не следует.

Nemiroff в сообщении #824062 писал(а):

Да? А какой?

Видимо, имеются ввиду частные случаи типа:
1) Если хотя бы одна матрица нулевая, то решение есть.
2) Если определители всех матриц ненулевые, то решения нет.
3) Если матрицы $3\time 3$ получаются обрамлением матриц $2\times 2$ или $1\times 1$ снизу и справа, причем исходные матрицы имеют ненулевой определитель, то решения нет.

[warlock66613]

Sonic86 в сообщении #824071 писал(а):

Видимо, имеются ввиду частные случаи типа:

Да нет же. Возьмём любые конкретные матрицы. Для них ответ либо "да" либо "нет". Возьмём два алгоритма: один, который при запуске печатает "да", другой - который печатает "нет". Один из них и является искомым.

[Sonic86]

warlock66613 в сообщении #824998 писал(а):

Да нет же. Возьмём любые конкретные матрицы. Для них ответ либо "да" либо "нет". Возьмём два алгоритма: один, который при запуске печатает "да", другой - который печатает "нет". Один из них и является искомым.

Хорошо. Что дальше?

[warlock66613]

Sonic86 в сообщении #825004 писал(а):

Хорошо. Что дальше?

К сожалению, уже не помню. Потерял мысль.