Вычислимые и невычислимые числа

[mihaild]

Попробовал всё же прочитать ваши определения. Ничего не понятно.
Нормальное определение, например, такое (без регулятора сходимости):
Функция $f: \mathbb{N} \to \mathbb{Q}$ задает число $x \in \mathbb{R}$, если $\lim\limits_{n \to \infty} f(n) = x$.
Вещественное число $x$ называется вычислимым, если его задает какая-то вычислимая функция $\mathbb{N} \to \mathbb{Q}$.
Другими словами - можно вычислить последовательность рациональных чисел, сходящуюся к данному вещественному числу.

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

Эти определения эквивалентны (множество вещественных чисел, задаваемых какой-то МТ в первом смысле, совпадает с множеством вещественных чисел, задаваемых какой-то МТ во втором смысле). Первое технически удобнее.

Эти определения вам понятны? Если нет - напишите, что непонятно.
Если да - они вас устраивает? Если нет - напишите, чем, и предложите своё в похожих терминах (какую функцию должна вычислять программа; кодирование на ленте можно не расписывать - как записывать рациональные числа и их конечные последовательности как-нибудь разберемся).
Пока что у вас путаница, обязана ли программа выдавать ваше "]]" или нет.

-- 10.01.2019, 16:53 --

mihaild в сообщении #1367234 писал(а):

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

А вот это кстати очевидное вранье: пусть в $x_n$ единицы стоят на позициях с номерами, не превосходящими $n$, если $n$-я МТ останавливается не более чем за $n$ шагов. Тогда каждое $x_n$ конструктивно, но $x_n$ сходится к константе Хайтина.
Чтобы утверждение стало верным - нужно потребовать, чтобы к последовательности прилагалась оценка на расстояние от текущего числа до предела.

(Оффтоп)

(а чем я думал, когда писал исходное утверждение - не знаю)

[warlock66613]

(Оффтоп)

mihaild в сообщении #1367354 писал(а):

а если уж совсем занудничать - то в математике занимаются манипулированием конечными строками - формулами

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

[Skipper]

mihaild в сообщении #1367439 писал(а):

Попробовал всё же прочитать ваши определения. Ничего не понятно.
Нормальное определение, например, такое (без регулятора сходимости):
Функция $f: \mathbb{N} \to \mathbb{Q}$ задает число $x \in \mathbb{R}$, если $\lim\limits_{n \to \infty} f(n) = x$.
Вещественное число $x$ называется вычислимым, если его задает какая-то вычислимая функция $\mathbb{N} \to \mathbb{Q}$.
Другими словами - можно вычислить последовательность рациональных чисел, сходящуюся к данному вещественному числу.

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

Верно, вот как и я пытался определить.

И вот , эту "дополнительную выходную ленту" - я и рассматриваю, больше ничего не надо. Для простоты.

И "входов" для программы никаких не надо. У неё нет никаких входов. Просто exe файл, написанный для запуска без параметров,
и просмотров в памяти, что эта программа там насчитала.
Бинарный код этого exe файла - и есть наше натуральное число из $N$ - как "номер" нашей машины Тьюринга (моей программы - написана на полным по Тьюрингу языке программирования).

mihaild в сообщении #1367439 писал(а):

путаница, обязана ли программа выдавать ваше "]]" или нет.

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

Если программа работает то она выдаёт последовательно числа, разделяет их символом "]" , а мы посмотрев что находится в памяти,
можем 1) взять перед этим символом - последний нужный нам член последовательности и остановить программу,
2) ждать следующих , более точных членов последовательности, которые будут ещё ближе к искомому вычисляемому числу.

Если программа на каком то этапе работает, никогда не останавливается, и не выводит что либо (какого то следующего очередного члена последовательности) -
больше никогда (т.е. за конечное время), значит её байт-код как целое двоичное число из $N$ она не представляет собой функцию
(самый простой пример такой программы - она начала выполнять пустой бесконечный цикл) -

mihaild в сообщении #1367439 писал(а):

Функция $f: \mathbb{N} \to \mathbb{Q}$ задает число $x \in \mathbb{R}$, если $\lim\limits_{n \to \infty} f(n) = x$.
Вещественное число $x$ называется вычислимым, если его задает какая-то вычислимая функция $\mathbb{N} \to \mathbb{Q}$.
Другими словами - можно вычислить последовательность рациональных чисел, сходящуюся к данному вещественному числу.

Т.е. данное число из $N$ (как двоичный байт-код такой программы) - не имеет отношения ни к одному числу из $ R$ .
Все остальные числа из $N$ - имеют отношение ко всем вычислимым числам из $ R$ ,
а т.к. они образуют подмножество счётного множества $N$ - значит, мы рассматриваем только счётное множество
вычислимых чисел из $ R$ .

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

-- Чт янв 10, 2019 16:44:25 --

(Оффтоп)

warlock66613 в сообщении #1367449 писал(а):

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

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

-- Чт янв 10, 2019 16:45:45 --

(Оффтоп)

Sonic86 в сообщении #1367437 писал(а):

сли рассматривать все $\mathbb{R}$ (включая все невычислимые действительные числа), то получается теория сильно проще и работоспособнее, чем теория, построенная на множестве вычислимых действительных чисел

Хорошо, если так.

[Dmitriy40]

Skipper в сообщении #1367422 писал(а):

Почему и какое утверждение выше, можно так записать?

Вот это:

mihaild в сообщении #1367317 писал(а):

Например множество не останавливающихся МТ - конструктивно несчетно. Хотя множество всех МТ и множество останавливающихся - счетны.

Если существуют лишь два вида МТ (останавливающиеся и не останавливающиеся), то сумма счётного (останавливающихся, $c$) и несчётного (не останавливающихся, $b$) множеств оказывается счётным множеством (все, $a$). Хотя несчётное по идее больше счётного ... Тогда даже второе условие в системе можно заменить на $b>a$.
Впрочем я мог и ошибиться с формализацией.

[mihaild]

Skipper в сообщении #1367451 писал(а):

Т.е. данное число из $N$ (как двоичный байт-код программы) - не имеет отношения ни к одному числу из $ R$ .

Нет, тут аргумент $f$ - это номер члена в последовательности приближения, никакой нумерации программ тут еще нет.

Skipper в сообщении #1367451 писал(а):

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

Можно это убрать без ограничения общности - пусть программа вместо завершения просто будет неограниченно повторять последнее выписанное число.

Skipper в сообщении #1367451 писал(а):

Для простоты

Это как раз сложнее - нужно брать отдельную ленту, следить за пределом и т.д.
Переделывается одно в другое несложно:
-из "выдать $n$-й член последовательности" в "выписать все": у нас есть программа $M$, которая по числу $n$ выписывает рациональное число - просто в цикле ее запускаем и печатаем результат
-из "выписать всё" в "выдать $n$-й член последовательности": запускаем программу, выписывающую последовательность, ждем, пока она напишет $n$ членов, выводим $n$-й

Ну ладно, давайте даже рассмотрим вариант с выписыванием бесконечной последовательности приближений.
Во-первых, надо сказать, что происходит если МТ выписывает бесконечную последовательность чисел, но эта последовательность никуда не сходится (видимо объявить что эта МТ не задает никакое число).
Во-вторых, тут всё та же проблема с проверкой корректности: существует МТ, которая выписывает бесконечную сходящуюся последовательность рациональных чисел, но доказать, что она это делает, нельзя.

Skipper в сообщении #1367451 писал(а):

я вообще думаю, что в моей этой модели - это самое простейшее для понимания - определение аналога машин Тьюринга

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

Dmitriy40, а что, где-то в этих разделах используются $+$ и $-$ вместо $\cup$ и $\setminus$?
Я не знаю, можно ли как-то разумно сравнивать множества в конструктивном смысле. И является ли вообще множество не останавливающихся МТ множеством с точки зрения конструктивистов (хотя если не является, то получим, что разность множеств не обязана быть множеством, что тоже хорощо).

[Skipper]

Dmitriy40 в сообщении #1367463 писал(а):

Если существуют лишь два вида МТ (останавливающиеся и не останавливающиеся), то сумма счётного (останавливающихся, $c$) и несчётного (не останавливающихся, $b$) множеств оказывается счётным множеством (все, $a$). Хотя несчётное по идее больше счётного ... Тогда даже второе условие в системе можно заменить на $b>a$.
Впрочем я мог и ошибиться с формализацией.

Dmitriy40 в сообщении #1367463 писал(а):

Например множество не останавливающихся МТ - конструктивно несчетно. Хотя множество всех МТ и множество останавливающихся - счетны.

В моём случае - я же доказал, что это не так..
Все мои программы как двоичные их коды - занумерованы целыми числами из $N$, их множество счётно.
1-е подмножество из $N$, определяет все вычислимые числа из них в $R$ ,
2-е подмножество - ничего не определяет.

Я не утверждаю ни про какое "множество невычислимых чисел".
Я просто написал что есть числа из $N$ , для которых функция

mihaild в сообщении #1367439 писал(а):

Функция $f: \mathbb{N} \to \mathbb{Q}$ задает число $x \in \mathbb{R}$, если $\lim\limits_{n \to \infty} f(n) = x$.

ничего не задаёт. Не имеет некоторых областей определений .
Где здесь какое то противоречие кто усмотрел?

И подмножество, таких номеров из $N$ - тоже счётно.

[mihaild]

Skipper в сообщении #1367451 писал(а):

Мне как программисту, так понять что такое машина Тьюринга - было проще с 1-го курса универа

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

[Dmitriy40]

mihaild
Ну можно и так переписать систему: $\left\{ \begin{array}{rcl} a&=&b\cup c\\ a&<&b\\ \end{array} \right.$ - лучше стало? По моему смысл практически не изменился в плане иллюстрации чем плохо не замыкание в поле.

Skipper
К тому что Вы там доказали или не доказали это отношения не имеет.

[mihaild]

Skipper в сообщении #1367472 писал(а):

Я просто написал что есть числа из $N$ , для которых функция

mihaild в сообщении #1367439 писал(а):

Функция $f: \mathbb{N} \to \mathbb{Q}$ задает число $x \in \mathbb{R}$, если $\lim\limits_{n \to \infty} f(n) = x$.

ничего не задаёт.

Это бессмысленное утверждение. В процитированном вами фрагменте нет никакой зависимости от числа из $\mathbb{N}$ (кстати, начните, пожалуйста, уже записывать знак натуральных чисел правильно).

И прочитайте, на что вы там отвечаете. Речь шла просто об останавливающихся МТ, никаких действительных чисел там еще не было.
И перестаньте пропускать слово конструктивная в словосочетаниях конструктивная счетность / несчетность. Конструктивная счетность сильно отличается от обычной.

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

-- 10.01.2019, 18:16 --

Dmitriy40 в сообщении #1367476 писал(а):

По моему смысл практически не изменился в плане иллюстрации чем плохо не замыкание в поле

О каком поле речь? Вроде бы мощности множеств не образуют поля (и даже группы) ни в каком смысле.

[Dmitriy40]

mihaild в сообщении #1367477 писал(а):

Dmitriy40 в сообщении #1367476 писал(а):

По моему смысл практически не изменился в плане иллюстрации чем плохо не замыкание в поле

О каком поле речь? Вроде бы мощности множеств не образуют поля (и даже группы) ни в каком смысле.

Речь шла о поле действительных чисел.
Вы привели пример что объединение конструктивно счётного и конструктивно несчётного множеств (разных МТ) может давать в результате конструктивно счётное множество (все МТ). Если первые соответствуют вычислимым вещественным числам, а вторые не вычислимым, то их объединение - всем действительным числам (тут тоже надо было расставить слово "конструктивно"?). Я лишь попытался (видимо не слишком удачно) записать это коротко формулой, из которой видна "абсурдность/противоречивость" в обычном смысле, если принять позицию конструктивизма (для действительных чисел).
Если пример оказался неудачным - приношу извинения и предлагаю далее не развивать и "спустить на тормозах".

[Skipper]

mihaild в сообщении #1367474 писал(а):

и это еще одна причина, почему определение с выдачей члена по номеру лучше: мы на выходе получаем гораздо более простой объект, чем в определении с бесконечным выписыванием

Согласен, но тогда ваш "объект" - будет вообще говоря, зависеть от двух номеров, 1) байт-код программы , и 2) номер последовательности который вы хотите получить.
А мой объект как программа - зависит от одного номера - двоичного кода своей программы - это просто можно рассмотреть как одно натуральное число. Для него и получается функция к одному вычислимому вещественному.

Dmitriy40 в сообщении #1367476 писал(а):

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

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

mihaild в сообщении #1367469 писал(а):

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

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

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

3)

mihaild в сообщении #1367477 писал(а):

В процитированном вами фрагменте нет никакой зависимости от числа из $\mathbb{N}$

Ну и что из того, что нет этой зависимости, понять не могу ? Просто - у данной функции есть области определения ,
и данное натуральное число как аргумент вашей функции - не входит в область определений.

mihaild в сообщении #1367469 писал(а):

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

Что означает "доказать нельзя"? 1) Я допустим, декомпилировал код программы, и понял что она там считает .
Тем самым - я за конечное время докажу, что данная программа считает вычислимое вещественное число и данный её номер из множества натуральных, попадает в область определений функции.

2) Я допустим, декомпилировал код программы, и увидел что там какой то бред, типа бесконечного пустого числа .
Тем самым - я за конечное время докажу, что данная программа ничего осмысленного не считает
(данный её номер из множества натуральных, не попадает в область определений функции).

-> предположим, это трудно доказать. Но "трудно" - не значит "невозможно".
Если данный тип программ в принципе доказуем, это значит, что за конечное время будет когда нибудь доказано - считает программа
что то осмысленное или нет. (число-номер программы попадёт выше в пункт 1)
Если же это в принципе не доказуемо , значит человечество об этом никогда не узнает .
(число-номер программы попадает выше в пункт 2 , но мы об этом не знаем. Из этого факта, счётное множество
вычислимых чисел - не становится несчётным, т.к. всё равно все вычислимые вещественные числа в любом случае
занумерованы как байт-коды программ - а это подмножество из $\mathbb{N}$ . ).

mihaild в сообщении #1367477 писал(а):

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

Обязательно ознакомлюсь с этими учебниками. Но мысль-то договорить можно, а то потом
может и потеряться.

[Dmitriy40]

Skipper
Цитируйте аккуратнее, Вы второй раз приписываете мне чужие слова.

[mihaild]

Skipper в сообщении #1367486 писал(а):

Согласен, но тогда ваш "объект" - будет вообще говоря, зависеть от двух номеров, 1) его байт-код , и 2) номер последовательности который вы хотите получить

Какой "объект"? КДЧ в таком определении задаются программами, которые берут на вход натуральное число и выдают рациональное. Дальше можно пробовать нумеровать сами программы.

Skipper в сообщении #1367486 писал(а):

1) радует, что кто-то хорошо понимает мою модель!

Да нету у вас модели вычислимости. Вы сформулировали что-то по мотивам одного из стандартных определений конструктивных действительных чисел, используя модель вычислений как черный ящик.
Описать что-то близкое по сложности к реальному процессору на том же уровне строгости, на котором определяется МТ или РАМ, у вас не получится.

Skipper в сообщении #1367486 писал(а):

Ну и что из того, что нет этой зависимости, понять не могу ?

То, что ваше утверждение имеет вид "существует натуральное число, для которого $2 + 2 = 4$". Оно конечно формально верно, но означает скорее всего не то, что вы имели в виду.

Skipper в сообщении #1367486 писал(а):

Что означает "доказать нельзя"?

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

Skipper в сообщении #1367486 писал(а):

а это подмножество из $\mathbb{N}$

Не всякое подмножество $\mathbb{N}$ можно эффективно занумеровать. И тут встает вопрос, который я выше уже задавал: почему вас не устраивают вещественные числа, которые нельзя эффективно (алгоритмически) приблизить, но устраивают биекции, которые нельзя эффективно задать?
Можно сделать программу $P$, которая по числу $n$ выдает какую-то программу, так, чтобы любое КДЧ задавалось программой $P(n)$ для какого-то $n$. Но сделать так, чтобы еще и программа $P(n)$ задавало КДЧ для любого $n$ - не получится.

Skipper в сообщении #1367486 писал(а):

Но мысль-то договорить можно, а то потом может и потеряться.

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

[Skipper]

Dmitriy40 в сообщении #1367489 писал(а):

Цитируйте аккуратнее, Вы второй раз приписываете мне чужие слова.

Я не нарочно "приписываю".. Выделил текст, нажал на кнопку "вставка" - получил результат.
Может, какой то дефект сайта?

-- Чт янв 10, 2019 18:09:42 --

mihaild в сообщении #1367491 писал(а):

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

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

Как это связано с вычислимыми числами? Именно поэтому их множество становится конструктивно несчётным, или ещё что-то?
Просто вы именно на этот пункт неоднократно указываете.

-- Чт янв 10, 2019 18:14:51 --

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

А вы говорите мне - путь она поставит в 1-й бит - единицу, если континуум-гипотеза истинна,
и пусть поставит туда 0 - если континуум-гипотеза ложна.

А дальше - пусть считает то, что было изначально запланировано.
Но континуум-гипотеза недоказуема, т.е. зависит от аксиом?

И какой тогда бит тогда мне туда писать ? Получается, что захочу то и запишу - противоречий после этого не получим,
и вычислимые числа останутся как и прежде, представленными счётным множеством?

-- Чт янв 10, 2019 18:20:08 --

mihaild в сообщении #1367491 писал(а):

Можно сделать программу $P$, которая по числу $n$ выдает какую-то программу, так, чтобы любое КДЧ задавалось программой $P(n)$ для какого-то $n$. Но сделать так, чтобы еще и программа $P(n)$ задавало КДЧ для любого $n$ - не получится.

Всё здесь понятно. Непонятно только что из этого следует, конструктивная несчётность вычислимых вещественных чисел?

[Dmitriy40]

(Оффтоп)

Skipper в сообщении #1367492 писал(а):

Я не нарочно "приписываю".. Выделил текст, нажал на кнопку "вставка" - получил результат.
Может, какой то дефект сайта?

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