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

[Someone]

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

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

1) Каким образом мы определяем, какой именно член последовательности нам нужен? Или мы просто говорим: "А возьмём-ка сотый член последовательности. Авось он нам подойдёт."?

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

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

Каким образом мы узнаем, что программа никогда ничего не выведет? Допустим, мы терпели миллиард лет, за это время программа вывела три члена последовательности: первый — через 10 минут после запуска, второй — через тысячу лет, третий — через два миллиона лет. Вдруг подождём ещё триллион лет, и она что-нибудь ещё выдаст?

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

(Оффтоп)

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

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

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

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

[mihaild]

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

Как это связано с вычислимыми числами?

Проблема в том, что вы же всё хотите делать алгоритмически. А алгоритмически проверить, получится противоречие или нет, нельзя.
Иначе, как я уже говорил, получается что-то странное: от вещественных чисел вы требуете вычислимости, а от биекции между $\mathbb{N}$ и вычислимыми числами - не требуете.

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

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

Нет, я так не говорю.

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

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

Именно. Не существует вычислимой сюръекции $\mathbb{N} \to \text{множество КДЧ}$. И тем более не существует биекции.

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

[Someone]

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

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

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

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

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

[Skipper]

Цитата:

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

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

Именно. Не существует вычислимой сюръекции $\mathbb{N} \to \text{множество КДЧ}$. И тем более не существует биекции.

Вы ничего не перепутали?
Я же не про невычислимые спросил, а про вычислимые. А здесь главное, чтобы наоборот,
существовала вычислимая сюръекция $\text{множество всех КДЧ} \to \mathbb{N}$.
Поскольку она в модели существует, то $\text{множество всех КДЧ} $ суть подмножество от $ \mathbb{N} $.
И у вас получается, что множество (счетно) имеет меньшую мощность чем его подмножество (несчетно).
Что противоречит здравому смыслу.

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

Каким образом мы определяем, какой именно член последовательности нам нужен? Или мы просто говорим: "А возьмём-ка сотый член последовательности. Авось он нам подойдёт."?

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

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

Каким образом мы узнаем, что программа никогда ничего не выведет? Допустим, мы терпели миллиард лет, за это время программа вывела три члена последовательности: первый — через 10 минут после запуска, второй — через тысячу лет, третий — через два миллиона лет. Вдруг подождём ещё триллион лет, и она что-нибудь ещё выдаст?

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

[Someone]

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

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

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

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

Достаточно того, что есть некая "абсолютная истина", либо программа выдаст
число последовательности либо нет.

Как только Вы это сказали, от всей вашей "вычислимости" остался шиш с маслом. Вы хоть подумайте, откуда Вы эту "абсолютную истину" узнаете? Так и будете сидеть около МТ до скончания веков, ожидая, выдаст она что-нибудь или нет. Смысл конструктивизма в том, что то, что нам требуется, мы делаем конструктивно, пусть даже эта конструктивность в разных направлениях конструктивизма понимается по-разному.

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

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

чтобы наоборот,
существовала вычислимая сюръекция $\text{множество всех КДЧ} \to \mathbb{N}$.

А что Вы с ней будете делать?

[mihaild]

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

Вы ничего не перепутали?
Я же не про невычислимые спросил, а про вычислимые. А здесь главное, чтобы наоборот,
существовала вычислимая сюръекция $\text{множество всех КДЧ} \to \mathbb{N}$.

Нет, не перепутал. Впрочем, такой сюръекции (и вообще вычислимой функции, область определения которой совпадает с множеством КДЧ), тоже не существует.

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

И у вас получается, что множество (счетно) имеет меньшую мощность чем его подмножество (несчетно).

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

(Оффтоп)

И кстати зачем вы ставите разрывы строк там, где они не нужны?

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

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

+много

[Dmitriy40]

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

И у вас получается, что множество (счетно) имеет меньшую мощность чем его подмножество (несчетно).
Что противоречит здравому смыслу.

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

[Skipper]

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

Как только Вы это сказали, от всей вашей "вычислимости" остался шиш с маслом.

У вас первично - программа, вторично - число которое она выводит или нет .

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

Мой же подход, наоборот.

1) сначала есть множество чисел, которые вам могут понадобиться.
Т.е. вот в принципе - рассмотрим всё множество чисел с которыми вы мне, как программисту, можете запросить,
сделать программу. И они все описываются формальным языком.

2) исходя из этого , и пишется программа.

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

При таком подходе - просто не может быть случая -

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

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

Первично - уже описанное число на формальном языке. Вторично - написанная программа (МТ).
Т.е. если есть программа - значит и есть программист , который её написал, и у него можно спросить доказательство ! (или он оставил к ней комментарии).

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

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

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

Возможно, что придётся и отказаться от "псевдочисел", как вы из называете.
Т.е. пишем программу (МТ), проанализировав также и оценки погрешностей от членов последовательности .
Как параметр к программе это задавать не надо, а просто программа, будет например,
гарантированно пропускаь лишние члены приближающейся последовательности ,
чтобы сотый член последовательности отличался от искомого числа не более чем на $0.01 $

-- Пт янв 11, 2019 14:18:28 --

(Оффтоп)

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

И кстати зачем вы ставите разрывы строк там, где они не нужны?

А как лучше, писать на всю ширину экрана? Кажется это неудобным для чтения, потому и вставлял.

-- Пт янв 11, 2019 14:46:22 --

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

Большая часть математики разрешает невычислимые биекции; но тогда непонятно, почему такая дискриминация - невычислимые биекции можно использовать, а невычислимые числа - нет. И я вам об этом минимум в третий раз пишу, а вы так и не ответили.

Согласен, невычислимую биекцию не надо использовать так же как и невычислимые числа.

Но я писал, что нам эта биекция не нужна. Для доказательства счётности всех вычислимых вещественных чисел -
достаточно 1) существовани сюръекции $\text{множество всех КДЧ} \to \mathbb{N}$.
а она есть и я её описал в своей модели.

2) а также аксиомы о том, что любое подмножество счётного множества никак не может бы с бОльшей мощностью, и следовательно - не может быть несчётным.

[Jnrty]

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

У вас первично - программа, вторично - число которое она выводит или нет .

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

Мой же подход, наоборот.

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

Подобных сюрпризов Вас может ожидать ещё много.

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

1) сначала есть множество чисел, которые вам могут понадобиться.
Т.е. вот в принципе - рассмотрим всё множество чисел с которыми вы мне, как программисту, можете запросить,
сделать программу. И они все описываются формальным языком.

2) исходя из этого , и пишется программа.

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

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

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

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

Это не Someone их так назвал. Это Марков с Шаниным. Давно-давно, лет сто назад.

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

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

У Вас очень примитивные представления о формальных языках. Например, простой формальный язык арифметики Пеано позволяет записывать неразрешимые высказывания. Язык теории множеств ZFC в этом отношении ещё богаче. Боюсь, более бедный язык, чем язык арифметики, Вас не устроит, а вместе с ним пролезут и все проблемы, которых Вы так тщитесь избежать.

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

Для доказательства счётности всех вычислимых вещественных чисел -
достаточно 1) существовани сюръекции $\text{множество всех КДЧ} \to \mathbb{N}$.
а она есть и я её описал в своей модели.

Недостаточно. Для доказательства счётности нужна биекция, а в рассматриваемом варианте конструктивизма — вычислимая биекция. Так вот какая-нибудь (невычислимая) биекция есть, а вычислимой нет.

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

2) а также аксиомы о том, что любое подмножество счётного множества никак не может бы с бОльшей мощностью, и следовательно - не может быть несчётным.

А кто Вам сказал, что в рассматриваемом варианте конструктивизма можно сравнивать мощноcти по величине? Как раз нельзя. Кстати, даже и термин "мощность" не используется.

(Skipper)

Слушайте, Вам не надоело ещё глупости нести? Хотите договориться до блокировки за злокачественное невежество? Это может случиться. Кто-нибудь из модераторов посмотрит-посмотрит и подумает: "А не пора ли это безобразие прекратить?"

[Skipper]

(Оффтоп)

Jnrty в сообщении #1367768 писал(а):

Хотите договориться до блокировки за злокачественное невежество?

Понятие "невежество", очень относительное. Если на форуме считается, все кроме знающих ВМ на уровне хороших преподавателей ВУЗов - "невежественны", то
подобный подход - антиреклама форуму. Ну, будут альтернативные форумы, где могут пообщаться и люди , менее глубоко знающие высшую математику,
а здесь количество участников форума резко снизится.
И вообще , считать человека, окончившего ВУЗ с математической специальностью невежественным - довольно спорно.
Скажем так, я лучше знаю ВМ чем 99,9% людей, наверное. Вот полгода назад обратилась двоюродная племянница с просьбой прорешать ей
задачи (12 штук было) , а там и ряды и интегралы и дифференциальные уравнения. Всё я ей прорешал и она сдала экзамен.
А два человека, к которым она обратилась до меня, тоже имеют математическое ВО - высшее образование, причём в отличии от меня , они отличниками были, но сказали что прорешать не могут, т.к. всё забыли.
(Вот к теме и вопрос - а действительно ли оценка в ВУЗе характеризует знания по жизни? ответ - никак не характеризует. Отличник имеет выше оценку,
может только потому что он 10 дней готовился, а неотличник- только 3 дня, больше - лень или другие интересы. Главное же - если человек темой по жизни интересуется а не только для сдачи экзамена).

PS И ещё, можно заметить, что не так часто я тут на форуме кому то надоедаю со своими вопросами. Бывает и по полгода ничего не пишу.
Так что надеюсь, я никому не помешал.. (и никому не надоел)..

[Jnrty]

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

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

Понятие "невежество", очень относительное. Если на форуме считается, все кроме знающих ВМ на уровне хороших преподавателей ВУЗов - "невежественны"

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

Обращаю ваше внимание на то, что Высшая математика и Вычислительная математика, по сути дела, не имеют отношения к вопросам, обсуждаемым в этой теме. Совершенно не важно, насколько хорошо Вы знаете эти дисциплины. Данная тема относится к основаниям математики. То, что Вы понаписали в этой теме — полная ерунда, поскольку в теории алгоритмов и в конструктивном анализе Вы совершенно не разбираетесь. Надо ещё иметь в виду, что теория алгоритмов может быть основана на классической логике, а может быть — на интуиционистской, и надо хорошо понимать, в чём разница. Что касается конструктивного анализа, то он, разумеется, использует интуиционистскую логику.

Более того, Вы ведёте себя агрессивно: Вам пытаются объяснить, почему Вы не правы, а Вы практически все объяснения игнорируете и продолжаете нести чушь. Посему прошу Вас более на эту тему не писать, пока не разберётесь по соответствующим учебникам.

[Skipper]

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

Jnrty в сообщении #1369286 писал(а):

Посему прошу Вас более на эту тему не писать, пока не разберётесь по соответствующим учебникам.

O.K . Больше ничего не пишу, до тех пор пока, не изучу эти учебники .