По ходу обсуждения проблемы определения эквивалентности двух алгоритмов (http://www.rsdn.ru/Forum/Message.aspx?mid=1365993&only=1

Автор: chukichuki
Дата: 05.09.05

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

Хотелось бы услышать ваше мнение по этому поводу.

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

C>По ходу обсуждения проблемы определения эквивалентности двух алгоритмов (http://www.rsdn.ru/Forum/Message.aspx?mid=1365993&only=1

Автор: chukichuki
Дата: 05.09.05

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

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

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

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

C>По ходу обсуждения проблемы определения эквивалентности двух алгоритмов (http://www.rsdn.ru/Forum/Message.aspx?mid=1365993&only=1

Автор: chukichuki
Дата: 05.09.05

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

Неправда. Для человека определить эквивалентность двух НЕЗНАКОМЫХ алгоритмов совсем не легко, потребуется очень долго втыкать в код, пока не станут ясны все последствия их исполнения.

А в случае qsort и пузырька тебе уже заранее известна ЦЕЛЬ этих алгоритмов, поэтому когда ты сходу называешь их эквивалентными, ты совсем не проводишь анализа их на эквивалентность -- ты просто сравниваешь их предназначение. Если бы можно было сообщить цель алгоритма компьютеру, то он сможет легко сделать тоже самое — сравнить цели.

chukichuki wrote:

> По ходу обсуждения проблемы определения эквивалентности двух
> алгоритмов (http://www.rsdn.ru/Forum/Message.aspx?mid=1365993&only=1

Автор: chukichuki
Дата: 05.09.05

> <http://rsdn.ru/Forum/Message.aspx?mid=1365993&amp;only=1&gt;

Автор: chukichuki
Дата: 05.09.05

) оказалось, что
> общий алгоритм для решения такой задачи составить нельзя.

Общий — нельзя. Для частных случаев — можно.

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

А кто сказал, что человек может определить эквивалентность ЛЮБЫХ алгоритмов?

--
С уважением,
Alex Besogonov (alexy@izh.com)

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

C>chukichuki wrote:

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

C>А кто сказал, что человек может определить эквивалентность ЛЮБЫХ алгоритмов?

Хорошо. Любых алгоритмов которые целенаправленно (всмысле не сгенерены случайным образом) были разработаны самим человеком. А именно они и интересны

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

C>>А кто сказал, что человек может определить эквивалентность ЛЮБЫХ алгоритмов?

C>Хорошо. Любых алгоритмов которые целенаправленно (всмысле не сгенерены случайным образом) были разработаны самим человеком. А именно они и интересно

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

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

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

C>>А кто сказал, что человек может определить эквивалентность ЛЮБЫХ алгоритмов?

C>Хорошо. Любых алгоритмов которые целенаправленно (всмысле не сгенерены случайным образом) были разработаны самим человеком. А именно они и интересны

Если человек сам их разработал, то он будет сравнивать их предназначения, а не проводить анализ на эквивалентность! А когда предназначение алгоритма неизвестно, то человек ничем от компьютера особо не отличается.

chukichuki,

C>Хотелось бы услышать ваше мнение по этому поводу.

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

chukichuki wrote:

>>> С другой стороны программист-человек с легкостью может определить
>>> эквивалентность двух алгоритмов (например, qsort-а и "пузырька")
> C>А кто сказал, что человек может определить эквивалентность ЛЮБЫХ
> алгоритмов?
> Хорошо. Любых алгоритмов которые целенаправленно (всмысле не сгенерены
> случайным образом) были разработаны самим человеком. А именно они и
> интересны

Гипотеза Гольдбаха, например, была создана самим человеком, но до сих
пор не доказана.

--
С уважением,
Alex Besogonov (alexy@izh.com)

Lazy Cjow Rhrr wrote:

> C>Хотелось бы услышать ваше мнение по этому поводу.
> Машина Тьюринга не может выйти за рамки ограничений, накладываемых
> собственно определением машины Тьюринга. А в человеке есть
> (божественная) искра, которая позволяет ему выходить за рамки любых
> ограничений.

А доказать?

> Поэтому человек и не описываем алгоритмически.

А доказать?

--
С уважением,
Alex Besogonov (alexy@izh.com)

Здравствуйте, Кодёнок, Вы писали:

Кё>Здравствуйте, chukichuki, Вы писали:

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

C>>>А кто сказал, что человек может определить эквивалентность ЛЮБЫХ алгоритмов?

C>>Хорошо. Любых алгоритмов которые целенаправленно (всмысле не сгенерены случайным образом) были разработаны самим человеком. А именно они и интересны

Кё>Если человек сам их разработал, то он будет сравнивать их предназначения, а не проводить анализ на эквивалентность! А когда предназначение алгоритма неизвестно, то человек ничем от компьютера особо не отличается.


Поскольку все алгоритмы (по крайней мере те которые заложены в компутерах и описаны в книгах) разработаны человеком => мы можем опеделить их назначение и показать (не)эквивалентность любых двух.

Относительно алгоритмизуемости мышления — здесь действительно трудно что-либо пологать пока мы не докажем/опровергем что человек превосходит по возможностям МТ.

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

C>Поскольку все алгоритмы (по крайней мере те которые заложены в компутерах и описаны в книгах) разработаны человеком => мы можем опеделить их назначение и показать (не)эквивалентность любых двух.

Это какая-то теоретическая абстракция. Каждый конкретный человек не знает ВСЕХ алгоритмов. Я могу тебя сейчас поставить перед двумя неизвестными тебе алгоритмами, и ты будешь в той же ситуации, что и машина. И задача будет для тебя нетривиальной, если алгоритмы сложные. Кто и зачем их разработал тут значения не имеет, потому что к моменту решения задачи об их эквивалентности ты этого не знаешь, и можешь никогда не узнать. Например, все записи об их предназначении уничтожены и авторы умерли.

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

C>chukichuki wrote:


>> Хорошо. Любых алгоритмов которые целенаправленно (всмысле не сгенерены
>> случайным образом) были разработаны самим человеком. А именно они и
>> интересны

C>Гипотеза Гольдбаха, например, была создана самим человеком, но до сих
C>пор не доказана.

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

chukichuki wrote:

> C>Гипотеза Гольдбаха, например, была создана самим человеком, но до сих
> C>пор не доказана.
> Я к сожалению туп и необразован. Не знаю такую гипотезу. Почитаю когда
> будет время,

Гипотеза очень простая: "Все целые числа, начиная с 5 можно представить
в виде суммы двух простых чисел".

То есть если взять мой предидущий пример
http://rsdn.ru/Forum/Message.aspx?mid=1366195&amp;only=1

Автор: Cyberax
Дата: 05.09.05

и заменить в нем
формулировку теоремы Ферма на такой псевдокод:

for(int f=2;f<num;f++)
    for(int n=2;n<num;n++)
    {
       if (простое_число(f) && простое_число(n) && f+n==num)
          return отсортированый_массив;
    }
return пустой_массив;

то получим алгоритм, эквивалентность которого неизвестна.

> но речь, не о гипотезе а об уже разработанных алгоритмах призванных
> решать конкретную задачу.
> (Неэ|Э)квивалентность таких алгоритмов человек может показать и даже
> доказать (исчисление программ Хоара и Флойда).

Смотрите мой пример.

--
С уважением,
Alex Besogonov (alexy@izh.com)

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

C>Гипотеза очень простая: "Все целые числа, начиная с 5 можно представить
C>в виде суммы двух простых чисел".

А 11 суммой каких двух простых чисел можно представить?
13 + (-2) ?

А 185?

Короче, в этом вольном переводе закралась ошибка.

Every even number greater than 2 can be written as the sum of two primes. (The same prime may be used twice.)

Cyberax,

C>А доказать?

А нафига, когда можно просто закрыть глаза и пофантазировать, тем самым приведя себя в качестве примера неалгоритмизуемого объекта, либо раскрыть глаза пошире и увидеть это в окружающих!?

Skipy Rich wrote:

> C>Гипотеза очень простая: "Все целые числа, начиная с 5 можно представить
> C>в виде суммы двух простых чисел".
> А 11 суммой каких двух простых чисел можно представить?

> 13 + (-2) ?

Угу Ну плохая у меня память, плохая.

> А 185?

Думать лень.

> Короче, в этом вольном переводе закралась ошибка.
> Every *even* number greater than *2* can be written as the sum of two
> primes. (The same prime may be used twice.)

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

--
С уважением,
Alex Besogonov (alexy@izh.com)

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

C>chukichuki wrote:

C>То есть если взять мой предидущий пример
C>http://rsdn.ru/Forum/Message.aspx?mid=1366195&amp;only=1

Автор: Cyberax
Дата: 05.09.05

и заменить в нем
C>формулировку теоремы Ферма на такой псевдокод:
C>

C>for(int f=2;f<num;f++)
C>    for(int n=2;n<num;n++)
C>    {
C>       if (простое_число(f) && простое_число(n) && f+n==num)
C>          return отсортированый_массив;
C>    }
C>return пустой_массив;
C>

C>то получим алгоритм, эквивалентность которого неизвестна.

неизвестна на данный момент времени t1, а на момент времени t1+1минута эквивалентность этого алгоритма может быть уже известна, в силу того что какой-нибудь раб божия докажет/опровергнет данную гипотезу. То, что эта гипотеза не доказана, еще не значит, что ее впринципе невозможно доказать или опровергуть, верно ? В итоге все это сводится к фил. проблеме познаваемости окружающего мира.

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

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

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

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

chukichuki wrote:

> C>то получим алгоритм, эквивалентность которого неизвестна.
> неизвестна на данный момент времени t1, а на момент времени t1+1минута
> эквивалентность этого алгоритма может быть уже известна, в силу того
> что какой-нибудь раб божия докажет/опровергнет данную гипотезу. То,
> что эта гипотеза не доказана, еще не значит, что ее впринципе
> невозможно доказать или опровергуть, верно ?

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

> В итоге все это сводится к фил. проблеме познаваемости окружающего мира.

Пока что философия тут непричем.

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

Странная логика...

--
С уважением,
Alex Besogonov (alexy@izh.com)