Существует ли биекция между вычислимыми числами и нат.?

[Someone]

juna в сообщении #184311 писал(а):

Получается, что Вы знаете о нем все

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

epros в сообщении #184334 писал(а):

Что значит "вычислить омегу с любой заданной точностью"? Как вычислить любое конструктивное действительное число (например, пи) с любой заданной точностью - я представляю, как вычислить омегу - нет.

Nxx в сообщении #184338 писал(а):

Омегу нельзя вычислить с любой точностью.

А почему, собственно говоря? Я понимаю, Вы верите в тезис Чёрча - Тьюринга - Поста - Маркова ... А какие у Вас основания считать, что всякая вычислимость - это механическая вычислимость по заранее написанной программе?

Xaositect в сообщении #184378 писал(а):

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

Как раз в точности наоборот.

Nxx в сообщении #184454 писал(а):

По идее, падающий наблюдатель увидит ускорение работы всего вокруг.

Вряд ли.

Nxx в сообщении #184330 писал(а):

Неограниченное - не значит бесконечное. Машина, которая требует бесконечной памяти или бесконечного времени, не является машиной Тьюринга.

Я ни одного раза не написал слова "бесконечное".
Но если машину Тьюринга ограничить по объёму используемой памяти и времени работы, то это будет, во-первых, не машина Тьюринга, а во-вторых, станут неразрешимыми многие задачи, решаемые машиной Тьюринга.

[Nxx]

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

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

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

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

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

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

Добавлено спустя 3 минуты 15 секунд:

Цитата:

А почему, собственно говоря? Я понимаю, Вы верите в тезис Чёрча - Тьюринга - Поста - Маркова ... А какие у Вас основания считать, что всякая вычислимость - это механическая вычислимость по заранее написанной программе?

Все очень просто. Под вычислимостью обычно понимают вычислимость машиной Тьюринга и пока что не предъявлено ни одного устройства и процесса, даже в теории, который мог бы делать сверхтьюринговые вычисления.

[Xaositect]

Someone в сообщении #184466 писал(а):

Как раз в точности наоборот.

Возможно, на идею это не влияет.

Nxx в сообщении #184468 писал(а):

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

А еще можно рассмотреть числа, вычислимые с помощью оракулов степени неразрешимости

$$0''$$

,

$$0'''$$

,

$$\sup \{0^{(n)}\}$$

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

[Someone]

Nxx в сообщении #184468 писал(а):

Вот таких чиссел, на мой взгляд, действительно не существует ни в каком смысле.

В смысле классической математики они существуют. И их существование существенно. Так что насчёт "никаких смыслов" будьте поосторожнее.

Nxx в сообщении #184468 писал(а):

Все очень просто. Под вычислимостью обычно понимают вычислимость машиной Тьюринга и пока что не предъявлено ни одного устройства и процесса, даже в теории, который мог бы делать сверхтьюринговые вычисления.

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

[epros]

Nxx писал(а):

Омегу нельзя вычислить с любой точностью.

О чём тогда речь? Здесь:

Nxx писал(а):

По сути, константы "омега" просто нет, так как свойства нашего пространства таковы, что вычислить это число невозможно

Вы можете определить что означает "вычислить омегу"? Только имея такое определение, как я понимаю, имеет смысл обоснованно говорить, можно это сделать или нельзя.

Nxx писал(а):

По идее, падающий наблюдатель увидит ускорение работы всего вокруг.

Нет.

[Someone]

Xaositect в сообщении #184475 писал(а):

Возможно, на идею это не влияет.

Тогда я не понимаю Вашу идею. Внешний наблюдатель может увидеть только конечную часть истории падающего компьютера, который на этом отрезке своей истории не успеет ничего вычислить. О чём тогда разговор? Кстати, если поменять местами наблюдателя и компьютер, то ситуация не улучшится: до падения в сингулярность наблюдатель увидит также лишь конечную часть истории компьютера.

[маткиб]

Nxx в сообщении #184468 писал(а):

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

наглая ложь

[Xaositect]

Someone писал(а):

Xaositect в сообщении #184475 писал(а):

Возможно, на идею это не влияет.

Тогда я не понимаю Вашу идею. Внешний наблюдатель может увидеть только конечную часть истории падающего компьютера, который на этом отрезке своей истории не успеет ничего вычислить. О чём тогда разговор? Кстати, если поменять местами наблюдателя и компьютер, то ситуация не улучшится: до падения в сингулярность наблюдатель увидит также лишь конечную часть истории компьютера.

Да, действительно, я ошибся. Наблюдатель падает в черную дыру, а компьютер находится снаружи. Вот ссылка на статью: http://arxiv.org/abs/gr-qc/0104023 Черная дыра должна быть вращающейся.

[juna]

Someone писал(а):

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

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

[Nxx]

Цитата:

Да, действительно, я ошибся. Наблюдатель падает в черную дыру, а компьютер находится снаружи. Вот ссылка на статью: http://arxiv.org/abs/gr-qc/0104023 Черная дыра должна быть вращающейся.

Как я уже говорил, это все не имеет значения, так как время жизни любой черной дыры конечно. Ускорить/замедлить вычисления так можно, но только в конечное число раз.

Цитата:

А еще можно рассмотреть числа, вычислимые с помощью оракулов степени неразрешимости

$$0''$$

,

$$0'''$$

,

$$\sup \{0^{(n)}\}$$

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

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

Цитата:

наглая ложь

Можете привести контрпример? Пример Кантора не подходит, так как для его вычисления нужен оракул бесконечного порядка.

Цитата:

В смысле классической математики они существуют.

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

[ewert]

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

[маткиб]

Nxx в сообщении #184468 писал(а):

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

Nxx в сообщении #184513 писал(а):

Цитата:наглая ложь

Можете привести контрпример? Пример Кантора не подходит, так как для его вычисления нужен оракул бесконечного порядка.

Вот именно пример Кантора и подходит: применим диагональ Кантора к совокупности чисел, вычислимых с "оракулами останова конечного порядка", получим число, которому мы дали определение, но, по-вашему, ему определение дать нельзя. А что там для этого нужен "оракул бесконечного порядка", это никого не интересует, потому что задача дать определение, а не вычислить.

[juna]

маткиб писал(а):

Вот именно пример Кантора и подходит: применим диагональ Кантора к совокупности чисел, вычислимых с "оракулами останова конечного порядка", получим число, которому мы дали определение, но, по-вашему, ему определение дать нельзя. А что там для этого нужен "оракул бесконечного порядка", это никого не интересует, потому что задача дать определение, а не вычислить.

Введем определение, дьявол - это существо о двух рогах и четырех копытах. Из допущения о его существовании нельзя получить противоречие с законами мироздания, следовательно, он существует.
А теперь становится страшно, ведь теперь действительно существует.

Именно так Вы и рассуждаете.

[Утундрий]

Коровы и быки точно существуют... и что в этом страшного? Оо

[Xaositect]

Nxx в сообщении #184513 писал(а):

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

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