См. замечание Левина о квантовых компьютерах.

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

Если у нас нет точности даже 20 цифр, как у нас может быть бесконечная точность?

Мы не знаем, есть ли у нас точность в 20 цифр. Может, есть, может, нет.
Это вопрос физический. Пока что квантовая электродинамика в лучших своих предсказаниях даёт точность (если не ошибаюсь) в 11 цифр - намного лучше, чем любые предсказания любой другой известной нам физической теории, в микро- или макро-мире.

Точность в бесконечное число цифр вообще неясно, достижима ли в принципе. Это вопрос философский.

А саму статью не постните?
Еще Интересно:
при помощи одного действительного числа легко закодировать любую функцию из целых чисел в целые числа. Это понятно. Но также ясно, что не всякую действительную функцию (R->R) можно так закодировать. Стало быть, полцчается некий подкласс всех функций R->R, который строго больше класса всех функций, вычислимых по Тюрингу. Возможно, там будут еще какие-то интересные промежуточные классы, подобно Push-down automata, которые лежат между машинами Тюринга и Finite State Automata. Кто-нибудь подобными вопросами занимался?

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

Вы спрашиваете об интересных классах; такие есть, называются Turing degrees (вычислимые функции в них - самый низкий уровень в иерархии). Это большой раздел теории вычислимости. У них исключительно сложная структура.

Спасибо, главное знать keywords остальное гугль дополнит. Хотя, Вы можете порекомендовать какие-то книжки/статьи на эту тему, то я буду премного благодарен.

Только вопрос:
почему вычислимые функции оказываются на *самом* нижнем уровне? Или FSA не вписываются в эту иерархию?

У меня еще вопросы есть, но надо сначала подумать, как их правильно сформулировать....

Да, FSA - и вообще все классы сложности внутри вычислимых функций не входят в эту иерархию, они слишком тривиальны для неё. Можно на это посмотреть так: вот есть класс вычислимых функций. С точки зрения теории степеней (Turing degrees) это что-то маленькое, краеугольный камень в иерархии, на котором всё строится. Это камень уже некуда делить практически. С точки зрения complexity theory - это что-то ужасно огромное, во что вмещаются все интересные классы и целые иерархии, причём вмещается даже где-то в самом начале этого огромного пространства.

Качественное, хорошо написанное и весьма основательное введение в теорию вычислимости (в том числе degrees, хотя о них там не очень много, ближе к концу книги) - Classical Recursion Theory by Odifreddi. Качественное быстрое введение в ту же тему, хорошо (но быстро) проходящее основные понятия и результаты (не помню, доходит ли он до degrees, но если да, то только немного общих слов успевает о них сказать) - Recursion Theory by Schoenfeld (это небольшая брошурка в серии Lecture Notes in Logic).

Именно и конкретно о Turing degrees я не знаю, какие книги/статьи советовать, к сожалению, т.к. я эту тему знаю довольно поверхностно.

Спасибо!

У меня нет разрешения автора поместить саму статью в публичный доступ, не уверен, что это ему понравилось бы. Т.к. он предложил послать её почтой всем желающим, думаю, не будет ничего страшного, если я сделаю то же самое; если кому-то интересно, напишите мне по почте, и я вышлю (PDF файл размером в 200kb).

Примерно этим занимается дескриптивная теория множеств.
Иерархия проективных множеств, их свойства...
Очень трудоемкая наука.

Господа
подскажите адреса где можно взять книги
по дескриптивной теории множеств в электронном виде

alex_dorin@rambler.ru

А потом прочитаете где-нибудь рассуждения,
схожие с вашими.

Напишите, именно это отличает тех кто остался в истории :)

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

Как-то я придумал физический мир, в котором можно было бы узнать результат бесконечной последовательности действий. Геометрия его была вполне разумной, но физика оказалась слишком фантастической. Пытался даже что-то записать, но показалось бесцельным.

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

А можно подробности. Самому интересно такие миры поконструировать.

Немножко написал вот тут.

А если ученые на Марсе найдут коробку с надписью "Caution! Hypercomputing device", они вообще смогут проверить, правда это или нет?
И особенно будет засадно, если Theory of Everything потребует такое устройство...

Ну на счет Hypercomputing device не знаю, а вот цифру 19 уже нашли. -:)

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