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

[Xaositect]

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

Ну так Омега тоже константа - значит, вычислима?

Омега - действительная константа. 0 и 1 - константы натуральные.

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

...Итак, 1000-й вычислим, 1001-й вычислим, 1002-й вычислим, я правильно понял? Любой разряд Омеги вычислим, так?

Да, только неизвестен алгоритм вычисления.

[маткиб]

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

Ну так Омега тоже константа - значит, вычислима?

Определение вычислимости вводится для функций $\mathbb{N}^n\rightarrow\mathbb{N}$, в крайнем случае для функций над другими счётными множествами. Для действительных чисел - своё определение, согласно которому омега не вычислима. Можно сказать, что любая константа-натуральное число вычислима (как функция $\mathbb{N}\rightarrow\mathbb{N}$, например).

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

...Итак, 1000-й вычислим, 1001-й вычислим, 1002-й вычислим, я правильно понял? Любой разряд Омеги вычислим, так?

ДА.

[Nxx]

Ну хорошо, если любой разряд омеги в классическом смысле "вычислим", то и функция

$$\text{sgn }\,x$$

, о которой шла речь выше "вычислима". Надо только понимать, что "вычислима" в данном случае не эквивалентно "выводима из аксиом арифметики".

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

[маткиб]

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

Надо только понимать, что "вычислима" в данном случае не эквивалентно "выводима из аксиом арифметики".

Что означает выводимость из арифметики для функций?

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

Nxx писал(а):

Ну хорошо, если любой разряд омеги в классическом смысле "вычислим", то и функция

$$\text{sgn }\,x$$

, о которой шла речь выше "вычислима"

Если её рассматривать как функцию над вычислимыми действительными числами, то в обычном понимании она невычислима.
Если над натуральными, то вычислима.

Nxx писал(а):

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

Никто и не спорит, что вычислить все разряды сразу невозможно (где столько бумаги найдёте, чтобы ответ выписать?)

[Nxx]

Цитата:

Если её рассматривать как функцию над вычислимыми действительными числами, то в обычном понимании она невычислима.

Также вычислима, как и разряды омеги. Ни больше, ни меньше.

Цитата:

Никто и не спорит, что вычислить все разряды сразу невозможно (где столько бумаги найдёте, чтобы ответ выписать?)

Я не про все, а про конкретные, начиная с достаточно большого (например, 1000-й).

[маткиб]

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

Также вычислима, как и разряды омеги. Ни больше, ни меньше.

Доказательство?

[Someone]

маткиб в сообщении #185321 писал(а):

Очень надеюсь, что Вы не тролль и реально не понимаете, а не провоцируете.

Он не тролль. Он просто фанатик. Как и все фанатики, он глух и слеп, и не воспринимает ничего, что не согласуется с его убеждениями.

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

Ну так Омега тоже константа - значит, вычислима?

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

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

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

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

[Nxx]

Цитата:

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

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

Цитата:

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

Если алгоритм не остановится, но ты об этом не знаешь, хрен ты определишь, остановится ли он когда-либо.

[epros]

Кстати, маткиб, относительно Вашего всезнающего "решателя":

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

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

я хотел Вас спросить: Раз Вы полагаете, что на все корректно поставленные вопросы (не в рамках даже конкретной теории, а "вообще") у кого-то (или где-то) есть правильные и однозначные ответы, подразумевает ли это, что Вы таким образом положительно отвечаете на "вечный" вопрос о существовании т.н. "первопричины"?

Под "первопричиной" (causa prima) обычно имеется в виду некоторая истинная формула (или устройство, или личность, или способ - не суть важно) из которой следуют все истинные утверждения. Причём речь, как Вы понимаете, идёт не обязательно о конечной формуле и не обязательно в конкретном синтаксисе, а, опять же, "вообще", т.е. в самом широком смысле.

К чему я это спрашиваю? А к тому, что понятие "первопричины" легко формализуемо в классической логике:
Высказывание $CP$ есть "первопричина", если $CP \wedge \forall P (P \to (CP \to P))$
(т.е. оно истинно и из него следует любое истинное высказывание).

И в той же классической логике элементарно показывается, что это понятие противоречиво, ибо $P \to (CP \to P) \leftrightarrow \neg CP$

[Nxx]

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

[epros]

Nxx писал(а):

epros, понятие такого оракула, о котором говорит маткиб само по себе не противоречиво.

Смотря как формализовать. Если так, как я сказал (а это, как я понимаю, вполне стандартная формализация), то противоречиво.

[juna]

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

Он не тролль. Он просто фанатик. Как и все фанатики, он глух и слеп, и не воспринимает ничего, что не согласуется с его убеждениями.

Второй раз от Вас вижу подобный реверанс.
Отсюда можно сделать индуктивный вывод: фанатик - это тот человек, чье мнение не согласуется с мнением Someone
Тогда вот Вам еще определение: догматик - это тот, кто "глух и слеп, и не воспринимает ничего, что не согласуется с его убеждениями."
Человек хочет выбрать - во что верить - глазам и ушам или "нормальным математикам".
А Вы говорите, что если не вступите в нашу партию баптистов, будем считать Вас фанатиком.

[маткиб]

epros писал(а):

Кстати, маткиб, относительно Вашего всезнающего "решателя":

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

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

я хотел Вас спросить: Раз Вы полагаете, что на все корректно поставленные вопросы (не в рамках даже конкретной теории, а "вообще") у кого-то (или где-то) есть правильные и однозначные ответы,

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

Тут ещё теорема Тарского о невыразимости истинности вспоминается (как аргумент в пользу того, что такое понятие, как "корректно поставленный математический вопрос вообще", бессмысленно).

epros писал(а):

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

Я так не отвечаю. Существование вымышленного "универсального решателя любых задач" у меня нигде не подразумевается (потому что я не понимаю, что такое "любая задача").

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

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

epros, понятие такого оракула, о котором говорит маткиб само по себе не противоречиво. Проблема в том, что таких оракулов нет и быть не может в реальном мире. Более того, не может быть и устройств, приближающихся к ним по свойствам.

Доказательство?

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

А вот если интерпретация задана, то мне кажется вполне осмысленным представлять устройство (не важно, можно ли его построить в реальном мире), которое для любой замкнутой формулы первого порядка нужной сигнатуры выдаёт её истинность в этой интерпретации.

[Nxx]

Цитата:

Доказательство?

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

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

Кстати, хотел спросить товарища маткиб, допускает ли он существование чисел, для которых не существует свойств, которые однозначно их определяют?

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

[маткиб]

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

физическим законам такие вещи противоречат, и это очевидно

А Вы эти законы знаете?
Я, например, про физические законы знаю три вещи:

1) Они противоречат сами себе (это означает, что их ещё уточнять и уточнять).
2) Есть туева хуча явлений, которые не имеют объяснений в рамках существующих теорий.
3) Даже, если единая теория и будет построена, то очень вероятно, что она является всего лишь грубым приближением более точной и более общей теории (которая может и допускать то, что недопустимо в известной теории).

Поэтому я бы не торопился тут про "очевидность" писать. Кстати, главным препятствием для тех, кому "всё очевидно", является третий пункт.

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

Известны, например, физические пределы на объем информации, который можно записать в некоторую область пространства

предположительные

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

на максимальную частоту

предположительные

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

Ожидать, что можно за конечное время проделать бесконечное количество вычислений или использовать бесконечные объемы памяти, неразумно

Так же, как и неразумно говорить, что это принципиально невозможно

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

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

Кстати, хотел спросить товарища маткиб, допускает ли он существование чисел, для которых не существует свойств, которые однозначно их определяют?

Если определите понятие свойства, то можно будет говорить.

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