ещё раз о hypercomputation
Jan. 16th, 2004 08:22 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaПару дней назад я попросил Мартина Дэвиса прислать мне копию его статьи о гипервычислениях (ещё не опубликованной; она появится в томе Turing Festschrift). Он прислал, и вот я прочитал сегодня. Хорошо и правильно всё написано (Дэвис — убеждённый противник всей этой области, он считает, что за этими статьями и книгами кроются только недоразумения и ошибки авторов, и я в этом с ним совершенно согласен), но недостаточно, на мой взгляд. Дэвис в основном пишет о наивности предположений о том, что можно использовать в качестве физических параметров вычислительной системы величины, заданные точными действительными числами (дело тут в том, что с помощью точных действительных чисел можно тривиальным образом закодировать любую функцию, как Тюринг-вычислимую, так и нет, и поэтому то, что с помощью такого гипотетического механизма "вычисляют" невычислимые функции — малоинтересная тавтология, хоть авторы соответствующих статей и не понимают этого, по-видимому). Он лишь мельком упоминает гораздо более глубокую, на мой взгляд, проблему природы понятия вычисления (и вычислимости) вообще; именно для прояснения этих вопросов, по моему убеждению, полезно исследовать такие вот попытки "гипервычислений". Они тривиальны и малоинтересны в смысле недостижения заявленной цели, но интересны тем, что помогают "от противного" понять и сформулировать важные принципы и ограничения в философии вычислимости.
Я писал об этом несколько раз в прошлом —
http://www.livejournal.com/users/avva/53278.html (два с половиной года назад, ох, как давно, оказывается)
http://www.livejournal.com/users/avva/516930.html (год назад примерно)
http://www.livejournal.com/users/avva/533830.html (тоже год назад, тут всего несколько ссылок)
Там, (правда, совсем вкратце) есть несколько слов о том, что я думаю по этому поводу. Если бы я не был таким ужасным лентяем, попробовал бы написать статью на эту тему (в голове намного больше засело, чем я тогда написал, и вспомнится, наверное) и послать куда-то. Не знаю... у меня есть свои сомнения по поводу ценности этого материала, но, может быть, стоило бы попробовать его вылить в ясную и приличную форму. Где только взять время и дисциплину для этого? Боюсь, ничего из этого не выйдет, и через год-полтора, зацепившись взглядом за очередной материал в этой области, я напишу ещё одну запись на эту тему, и дам ссылку сюда...
Я писал об этом несколько раз в прошлом —
http://www.livejournal.com/users/avva/53278.html (два с половиной года назад, ох, как давно, оказывается)
http://www.livejournal.com/users/avva/516930.html (год назад примерно)
http://www.livejournal.com/users/avva/533830.html (тоже год назад, тут всего несколько ссылок)
Там, (правда, совсем вкратце) есть несколько слов о том, что я думаю по этому поводу. Если бы я не был таким ужасным лентяем, попробовал бы написать статью на эту тему (в голове намного больше засело, чем я тогда написал, и вспомнится, наверное) и послать куда-то. Не знаю... у меня есть свои сомнения по поводу ценности этого материала, но, может быть, стоило бы попробовать его вылить в ясную и приличную форму. Где только взять время и дисциплину для этого? Боюсь, ничего из этого не выйдет, и через год-полтора, зацепившись взглядом за очередной материал в этой области, я напишу ещё одну запись на эту тему, и дам ссылку сюда...
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2004-01-16 11:01 am (UTC)no subject
Date: 2004-01-16 11:28 am (UTC)no subject
Date: 2004-01-16 07:29 pm (UTC)no subject
Date: 2004-01-18 03:02 pm (UTC)Это вопрос физический. Пока что квантовая электродинамика в лучших своих предсказаниях даёт точность (если не ошибаюсь) в 11 цифр - намного лучше, чем любые предсказания любой другой известной нам физической теории, в микро- или макро-мире.
Точность в бесконечное число цифр вообще неясно, достижима ли в принципе. Это вопрос философский.
no subject
Date: 2004-01-16 11:04 am (UTC)Еще Интересно:
при помощи одного действительного числа легко закодировать любую функцию из целых чисел в целые числа. Это понятно. Но также ясно, что не всякую действительную функцию (R->R) можно так закодировать. Стало быть, полцчается некий подкласс всех функций R->R, который строго больше класса всех функций, вычислимых по Тюрингу. Возможно, там будут еще какие-то интересные промежуточные классы, подобно Push-down automata, которые лежат между машинами Тюринга и Finite State Automata. Кто-нибудь подобными вопросами занимался?
no subject
Date: 2004-01-16 11:24 am (UTC)Вы спрашиваете об интересных классах; такие есть, называются Turing degrees (вычислимые функции в них - самый низкий уровень в иерархии). Это большой раздел теории вычислимости. У них исключительно сложная структура.
no subject
Date: 2004-01-16 11:47 am (UTC)Только вопрос:
почему вычислимые функции оказываются на *самом* нижнем уровне? Или FSA не вписываются в эту иерархию?
У меня еще вопросы есть, но надо сначала подумать, как их правильно сформулировать....
no subject
Date: 2004-01-16 12:03 pm (UTC)Качественное, хорошо написанное и весьма основательное введение в теорию вычислимости (в том числе degrees, хотя о них там не очень много, ближе к концу книги) - Classical Recursion Theory by Odifreddi. Качественное быстрое введение в ту же тему, хорошо (но быстро) проходящее основные понятия и результаты (не помню, доходит ли он до degrees, но если да, то только немного общих слов успевает о них сказать) - Recursion Theory by Schoenfeld (это небольшая брошурка в серии Lecture Notes in Logic).
Именно и конкретно о Turing degrees я не знаю, какие книги/статьи советовать, к сожалению, т.к. я эту тему знаю довольно поверхностно.
no subject
Date: 2004-01-16 12:34 pm (UTC)no subject
Date: 2004-01-16 11:27 am (UTC)no subject
Date: 2004-01-17 02:22 am (UTC)Иерархия проективных множеств, их свойства...
Очень трудоемкая наука.
дескриптивная теория множеств
Date: 2005-01-27 09:28 am (UTC)подскажите адреса где можно взять книги
по дескриптивной теории множеств в электронном виде
alex_dorin@rambler.ru
no subject
Date: 2004-01-16 01:10 pm (UTC)схожие с вашими.
Напишите, именно это отличает тех кто остался в истории :)
no subject
Date: 2004-01-16 01:13 pm (UTC)точку можно двигаться вперед, а не возвращаться ежегодно к одной и той же мысли
no subject
Date: 2004-01-16 10:46 pm (UTC)Но меня не интересовал философский вопрос (о принципиальной невозможности инкорпорировать в человеческую математику результаты, полученные таким образом), а хотелось попробовать: смогу ли я хотя бы краешком ощутить стиль мышления тех разумных, для которых это не фантастика, а основа реальности.
no subject
Date: 2004-01-17 01:04 pm (UTC)no subject
Date: 2004-01-19 08:32 am (UTC)no subject
Date: 2004-01-17 08:14 pm (UTC)И особенно будет засадно, если Theory of Everything потребует такое устройство...
no subject
Date: 2004-01-19 02:51 pm (UTC)no subject
Date: 2004-01-19 03:42 pm (UTC)Невычислимые задачи - это задачи не решаемые за конечное время при помощи машины Тьюринга. А гипервычисления - это соответственно некая технология (умозрительная, как я понимаю) решения таких задач, так?
Пенроуз утверждает что часть операций, совершаемых при мышлении, относятся к классу невычислимых. Не означает ли это что собственно человеческая голова представляет собой вполне действующий гипервычислитель?