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

"Все равно его не брошу

потому что он хороший!"

SMT: "при чем тут математика? она только решает задачу, как она описана моделью. если в модели машина не состоит из "твердых детерминированных частиц", она работает надежно, еслb состоит - то эта не та машина, о которой говорил Тьюринг. к ней можете создать свою теорию остановки ;)"

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

SMT, давайте еще раз попробуем расставить точки над i. Что есть математика? Математика это воображаемый нами мир. Но в отличии от других воображаемых миров, это мир имеет свойство быть независимым от нашего воображения. Например мир Гарри Поттера существует в голове автора книги (а так же читателей) и постоянно нуждается в "подкачке" со стороны фантазии автора (мои дети сейчас с восторгом читают эту книгу). Этот мир существует только там, куда "смотрит" воображения автора. Некоторые детали прорисованы тщательно, некоторые вообще в темноте.

Реальность, в этом смысле, как мы полагаем, не такова.

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

Но математическая реальность в этом смысле занимает некую промежуточную позицию.

Она не существует реально. Это наша выдумка. Как мир Гарри Поттера. Но она, математическая реальность и независима от нашей фантазии. Она как бы сама по себе. Это как бы третий мир. Между реальностью и вообржаемостью.

Как материализовать математику?

Очень просто.

Мы должны построить формальную теорию матемаики.

{A, R, O}

A – определить набор симвовов данной теории.

R – определить набор формальных правил манипуляций с символами.

O – определить набор цепочек в алфавите А, которые будут считаться истинными сами по себе. Набор аксиом.

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

Педоположим что мы в алфавите A построили некое математическое высказывание V.

Если наша теория непротиворечива, то это гарантирует нам следующее

Если на выходе алгоритма появилось высказывание V то на выходе никогда не появится высказывание не-V. Или то или то.

Полнота теории предполагает что на выходе алгоритма рано или поздно появится либо высказывание V либо его отрицание не-V.

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

Значит в алфавите А существует масса математических высказываний, которые недоказуемы в данной теории. Ни это высказывание ни его отрицание никогда не появится на выходе алгоритма P.

Но что это за высказывания?

Истинны они НА САМОМ ДЕЛЕ или ложны?

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

1 комментарий:

Кука Тверской комментирует...

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

Каждая из них будет внутренне непротиворечива но они будут противоречить друг другу.

А какая из них истинная? Обе. Проверить экспериментально мы не можем. Расширить теорию можно в той области математики, которую нельзя проверить. Так утверждение "2384043093423932311231 –простое число" можно проверить. Но это твердая часть математики и естественно доказуемое утверждение (есть примитивно-рекурсивный алгоритм который решает этот вопрос то есть гарантированно остановится). Утверждение "множество простых чисел бесконечно" уже экспериментально проверить уже нельзя. Здесь задействована бесконечность. Но мы знаем, что это утверждение рано или поздно будет напечатано на выходе алгоритма Р. Однако как быть с утверждениями, которые касаются непроверяемой бесконечности и могут оказаться не выводимыми в нашей теории?

Они либо истины либо ложны? Или оно никакое?

Если мы не исповедуем платонизм, то мы говорим что оно никакое. Именно этого касается фраза Подниекса. Задав А, R и O мы выдумали новый мир. Но задав А, R и O мы не можем выдумать его во всех деталях. В некоторых местах там "черные провалы". Он не обладает свойством быть сплошным даже там где нас нет как в нашей реальности. Математика это выдумка (Роджерс Пенроуз будет несоглашасен! :) как мир Гарри Потера. Разница в механизме их порождения. Мир Гарри Потера клеится из возможно противоречивых образов-цепочке и только в нужных местах, а математика строится как мозаика по раз и навсегда заданным правилам аксиоматически. И все. Но и такая мозаика покрывает не всю "плоскость рисунка" как ожидали математики.

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

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

Все нормально и логично.

Но давайте попробуем вообразить.

И здесь воображение начинает сдавать.

Возвращаясь к атомам воздуха, которые соберутся в одном конце комнаты. Это совершенно иная ситуация. Я говорю о реальности. Как она должна себя вести на бесконечность? Там где нас нет и никогда не будет. Но она там должна быть! Как реальность поступит с той частью математики где у нас дырки?

Вот я и пришел к крамольной мысли. Наблюдаемая нами реальность неадекватна той реальности которая есть на самом деле. Мы видим одну машину в нашей видимой одной реальности (классической реальности) потому что так устроено наше восприятие. В квантовой реальности существует бесконечное число машин (в мультиверсной интерпретации Эверетта) и для них вопрос остановится ли они все вместе или нет – не все варианты. На некоторых задачах они все вместе останвятся. На некоторых все вместе не остановяться. Но на некоторых, которые уходят на бесконечность, одни остановятся - один нет.

В общем я не вполне все это понимаю сам.

Как говориться, все это тема для медитации.

Кто-нибудь хочет помедитировать со мной?

:)
Информация о пользователе dzver
dzver
Скрыть | 31 августа 2004 г., 07:14
Alexandr_Semenov

Давайте помедитируем:)

Хотя мне по прежнему неясно где проблема...

Вы задаете вопрос, несколько строчек внизу отвечаете /с ваш ответ я вполне согласен:)/, и после етого опять же задаете тот самый вопрос:)

Если на выходе алгоритма появилось высказывание V то на выходе никогда не появится высказывание не-V. Или то или то.

Полнота теории предполагает что на выходе алгоритма рано или поздно появится либо высказывание V либо его отрицание не-V.

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

Значит в алфавите А существует масса математических высказываний, которые недоказуемы в данной теории. Ни это высказывание ни его отрицание никогда не появится на выходе алгоритма P.

Ну да, так оно и есть.

Но что это за высказывания?

Истинны они НА САМОМ ДЕЛЕ или ложны?

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

Слово "истина" лучше не использовать если мы его не формализовали, ибо тогда неясно что оно означает.

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

Каждая из них будет внутренне непротиворечива но они будут противоречить друг другу. А какая из них истинная? Обе.

Именно так и никак иначе!

Утверждение "множество простых чисел бесконечно" уже экспериментально проверить уже нельзя. Здесь задействована бесконечность.

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

Но мы знаем, что это утверждение рано или поздно будет напечатано на выходе алгоритма Р.

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

Так что надо четко определить что мы понимаем под словесной аббревиатурой "проверимо експериментально".

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

А никак.. Или скорее как мы решим, так и сделаем.

Они либо истины либо ложны? Или оно никакое?

Никакие /т.е. невыводимы ни они, ни их отрицания/, в контексте принятых аксиом и правил вывода.

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

Если мы не исповедуем платонизм, то мы говорим что оно никакое.

Очевидно я не платонист...

Но задав А, R и O мы не можем выдумать его во всех деталях. В некоторых местах там "черные провалы". Он не обладает свойством быть сплошным даже там где нас нет как в нашей реальности. Математика это выдумка (Роджерс Пенроуз будет несоглашасен! :) как мир Гарри Потера. Разница в механизме их порождения. Мир Гарри Потера клеится из возможно противоречивых образов-цепочке и только в нужных местах, а математика строится как мозаика по раз и навсегда заданным правилам аксиоматически. И все. Но и такая мозаика покрывает не всю "плоскость рисунка" как ожидали математики.

Чудесно сказано.

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

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

....

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

Все нормально и логично.

Но давайте попробуем вообразить.

И здесь воображение начинает сдавать.

....

Я говорю о реальности. Как она должна себя вести на бесконечность? Там где нас нет и никогда не будет. Но она там должна быть!

Вот здесь я уже не согласен.

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

Например, что после бесконечного времени 2+2=5. Или что на бесконечности ничего нет. Или что на бесконечности бывает все. И т.д. Воображение разных людей дает разные картины - но ето ведь воображение - как мир Гарри Потера - а не что-то реальное или логически смысленное.

Как реальность поступит с той частью математики где у нас дырки?

Как "ей захочется". Например реальность выбрала чтобы пространство-время было неевклидово... А Евклид ету "дырку" /т.е. дополнительную аксиому о параллельных/ залатал уже "неправильно". Разумеется неправильно относно того что "реальность" думает; в математики "правильно" и "неправильно" бессмысленны - не выводится 5-й постулат Евклида из других - так можно выбрать как 5-ого постулата чтобы расширить теорию, так и его алтернативы...

Еще то представление, что реальность должна быть "сплошная" под большим вопросом...

Даже с учетом КМ ничего не дает оснований утверждать что реальность богаче простой машиной Тьюринга /тезис не-знаю-кого-то/.

Однако мне кажется - здесь вопрос принципиальный... Поскольку научное описание реальности по своей сути обязано быть "исчислимым" /если не привлекать херомантии/, то и модель реальности с которой оперируем тоже всегда будет исчислимой.

А сама реальность - хер ее знает..

Если найдут Теории Всего - так она точно будет вычислима.
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 31 августа 2004 г., 18:29
Завтра я в отпуске. Но на последок.

"Чудесно сказано.

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

Именно так. Так называемая программа Гильберта как раз предполагала найти доказательство непротиворечивости математики средствами самой математики дабы устранить кризис оснований математики вызванный парадоксами теории множеств. Именно в русле этой программы появился многотомник "Принципы математики" Рассела и Уайтхида.

Над этим работал фон-Нейман, когда узнал о теореме Геделя в 31 гду. Против этого была направлена кстати и сама работа Геделя. Цель его работы – доказать невыполнимость программы Гильберта.

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

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

Кстати буквально вчера перечитывал последние главы из книги Роджера Пенроуза "Новый ум короля". Так вот Пенроуз не скрывает своих именно платонистических взглядов! Он не сдается!

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

"Вот здесь я уже не согласен.

Если употребление термина "бесконечность" не четко формализовано, про бесконечности можно утверждать все что захочется. Например, что после бесконечного времени 2+2=5. Или что на бесконечности ничего нет. Или что на бесконечности бывает все. И т.д. Воображение разных людей дает разные картины - но ето ведь воображение - как мир Гарри Потера - а не что-то реальное или логически смысленное."

Ага... Отлично!

Хотя это скользкая идея... но она мне нравится. :)

"Еще то представление, что реальность должна быть "сплошная" под большим вопросом...

Даже с учетом КМ ничего не дает оснований утверждать что реальность богаче простой машиной Тьюринга /тезис не-знаю-кого-то/.

Тезис Черча-Тьюринга.

Эти идеи есть у Дойча. Они восхитительны но... но к сожалению... у меня есть весомы контраргумент. Реальность действительно богаче. Помните что такое невычислимые числа? Это числа, которые не может вычалит никакая машина Тьюринга.

Так я могу "вычислить" такое число. Неалгоритмически.

Я сам себе не верю но это так!

Смотрите.

Запишем все вычислимые числа в канторов стобец в двоичном коде.

010101010101010....

000000000000000...

111111111111111...

101010101000101...

. . . .

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

Но давайте начнем подбрасывать чистую монету некий квантово-механический луидор.

Выпал "орел"? Записываем 0 Выпала решка? Записываем 1

Так мы будем бесконца "вычислять" некоторое совершенно случайное число:

100101000101110101011101010100101 . . . .

Какова вероятность того, что это число находится в вышеприведенной бесконечной таблице?

Возьмем произвольную строку этой таблицы. Вероятность что первые символы обеих строчек совпадают - 1/2. Вероятность что совпадает И вторые символы (1/2)^2= 1/4. Вероятность что совпадет все разряды строк с первого по n-тый (1/2)^n и при n -inf вероятность стремится к 0.

Lim (1/2) ^n = Pr = 0

n-inf

Но в таблице бесконечное число строк!

Давайте рассмотрим событие "квантово-луидорная цепочка не совпадает ни с

одной строчкой-цепочкой"

Это значит что ОДНОВРЕМЕННО НЕ происходит сопадения (1-Pr)...

нИ с цепочкой 1

нИ с цепочкой 2

нИ с цепочкой 3

нИ с...

. . .до бесконечности . То ест вероятность этого события

Lim (1-Pr)^n

n-inf

Но Pr мы уже определили и тогда полная вероятность несовпадения строчек такова:

Lim [1- (1/2)^n]^n

n-inf

Далее мы решаем этот предел учитывая что n стремиться к плюс бесконечности.

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

И так вероятность того что наше число не находится в таблице вычислимых чисел = 1.

То есть мы построили НЕВЫЧИСЛИМОЕ ЧИСЛО.

Невычислимое ни на одной машине Тьюринга.

Используя случайность.

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

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

"Однако мне кажется - здесь вопрос принципиальный... Поскольку научное описание реальности по своей сути обязано быть "исчислимым" /если не привлекать херомантии/, то и модель реальности с которой оперируем тоже всегда будет исчислимой."

Согласен. И тем не мене как вы можете выше видеть в квантовой механике есть невычислимая процедура R которая выходит за рамки вычислимого. Наша реальность несколько мощнее и не поддается моделированию в полном объеме на машине Тьюринга.
Информация о пользователе dzver
dzver
Скрыть | 31 августа 2004 г., 19:20
Alexandr_Semenov

То есть мы построили НЕВЫЧИСЛИМОЕ ЧИСЛО.

Невычислимое ни на одной машине Тьюринга.

Используя случайность.

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

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

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

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

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

Ваше число невычислимо только "на бесконечности".

В реальности, вы ету бесконечность никогда не "потрогаете" и ваше невычислимое число никогда "не увидите".

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

Но таких "построений" нельзя приводить в доказательстве что чего-либо в реальности существует:)

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

Eто бесконечная процедура... Докажите, что в квантовой механики ее есть.

Даже если и используем какую-то хитрую комбинацию КМ и ТО /типа компресирование бесконечного собственного интервала времени в конечного для внешнего наблюдателя/ опять не получается потому что такие вещи "за горизонтом" и недоступны и "ненаблюдаемы" для внешнего наблюдателя. Ето с гравитации.

А если пофантазировать про скорости... можно спросить у фотонов /надеясь что нормальное время вселенной бесконечно - для фотонов оно сжато в мгновение/ - заодно и получим ответ сколько равно 0/0:)

Наша реальность несколько мощнее и не поддается моделированию в полном объеме на машине Тьюринга.

Не согласен... Какова реальность в етом отношении - не известно /может быть и так, и так/.
Информация о пользователе S
S
Скрыть | 31 августа 2004 г., 20:06
===Alexandr_Semenov Участник Клуба

---То есть мы построили НЕВЫЧИСЛИМОЕ ЧИСЛО.

Хочу добавить к предыдущему посту то, что описанный Вами алгоритм имеет ту же проблему остановки. Т.е. никак не обходит ее. Каким образом Вы узнаете что УЖЕ построили невычислимое число? Таблица для проверки ведь бесконечна и узнать, что Вы прошли ее всю Вам тоже не дано.

А практически нулевая вероятность НИКОГДА не доказывала невозможность события. Вот какова вероятность того, что Вас зачали родители (именно эти папа и мама, именно в данное время и именно конкретный сперматозоид добрался до яйцеклетки)? Практически ноль...

А Вы ведь существуете... ;)
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 1 сентября 2004 г., 02:49
Ну вот. Я выдал чуть ли не самый интересный результат в соей жизни, а его не поняли! Похлопали по плечу и сказали: "тебе мерещится" :)(

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

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

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

И так. Что такое вычислимое число?

Нет, начнем еще раньше.

Начнем с несчетных множеств. С Кантора. Святая святых. Диагональная процедура. Как Кантор доказывает что множество действительных чисел действительно несчетно?

Он говорит. Допустим мы упорядочим все действительные числа на интервале

]0, 1[ и выпишем их в столбик в некотором порядке. Допустим так...

0.102933838222333. . .

0.129328233439494. . .

0.348432238229348. . .

0.409538234201234. . .

. . .

Каждая такая БЕСКОНЕЧНАЯ строчка – это дейстительне число.

И таких чисел – бесконечность. То есть таблица вниз тоже бесконечна. В результате мы имеем бесконечную вправо и вниз таблицу ЦИФР.

Нам надо доказать что не все натуральные числа находятся в этой бесконечной таблице. Мы берем диагональ справа вниз и слева направо и выписываем ее цифры. Получаем еще одно диагональное число:

0.1285 . . .91. . .

Тоже бесконечная цепочка цифр. Возможно это число тоже находится где-то "посередине" таблицы. Наверняка там находится! Но теперь мы его "инвертируем" каким-либо образом. Например прибавляем к каждой цифре единицу, а если эта цифра 9 то заменяем ее на 0.

Получаем другое число

0.2396. . .02 . . .

Это число отличается от любого числа в бесконечном списке хотя бы на одну цифру. От первого в первой цифре. От второго во второй. От третьего в третей.

То есть это число выпадает из списка. А значит, как бы этот список не был упорядочен он не содержит всех действительных чисел из интервала ]0, 1[

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

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

Как он так лихо берет и упорядочивает бесконечные цепочки? Как это он строит бесконечную диагональ? И как это он так легко выводит, актуализирует свойства некоторого бесконечного объекта?

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

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

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

Я вспоминаю это, потому что меня обвинили в том же. Что я перескакиваю через бесконечность. Это смешно. Потому что между мной и Кантором стоит еще одно имя. Тьюринг. Он тоже "скачет". И его тоже внесли в учебники за это. :)

Что мы имеем перед Тьюрингом? Перед его работой о невычислимых числах 1936года? Мы имеем числовую ось состоящую из множества действительных чисел. Их не то что много их ОЧЕНЬ много. Их несчетное количество. Множество натуральных чисел 1, 2, 3 . . . . есть подмножество этого множества.

Поэтому их можно было бы выписать в стандартном виде как мы выписываем действительные числа в виде бесконечных цепочке.

1.00000000 . . . .

2.00000000 . . . .

3.00000000 . . . .

. . .

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

Кроме того есть множество рациональных числе. Это числа заданные дробью вида a/b, где a и b – натуральные числа (здесь следовало бы упомянуть отрицательные числа, целые, но это - детали). При кажущемся бОльшем множестве действительных числе их тоже счетное число. Столько, сколько натуральных. Их тоже можно расположить в бесконечный столбик ни потеряв ни одного. Легко понять что, с одной стороны, они подмножество множества действительных чисел (они расположены где-то на числовой оси), но с другой стороны натуральные числа – их под множество.

Сморите:

1/1, 2/1, 3/1, . . . и т.д.

Это дроби, но то же и наши натуральные числа!
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 1 сентября 2004 г., 02:50
Желательно все это рисовать в виде кружочков друг в друге. Мы уже получили некую матрешку множеств. И будем ее достраивать дальше и дальше.

Следующий шаг.

Вы знаете что число корень из 2 не принадлежит множеству рациональных чисел. Но оно тоже расположено где-то на числовой оси. Это горе Пифагора. Крах его системы. Тайна пифогарийев, предательски открытая миру. . . Корень из два не рациональное число его называют алгебраическим числом.

Всякое число которое можно записать как некоте алгебраическое высказывание с использованием операций и знаков радикала называется алгебраическим например: [2+sqrt(5)- sqrt(3)]^3 / sqrt(7).

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

1/1, 2/1, 3/1, . . . и т.д.

Счетное ли множество алгебраических чисел? Ведь таких чисел еще больше чем дести тельных чисел! Но подумайте, любая такая формула – это конечная цепочка символов. А множество таких конечных цепочек счетное. То есть это еще одна матрешка. Еще большая. Но она все рано внутри суперматрешки несчетного множества дейстительных чисел. То есть на числовой прямой все равно остаются числа, для вычисления которых не хватает всех алгебраических выражений!

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

Очевидно трансцендентные числа тоже являются некой матрешкой и наверное не последний. Далее можно выделить множество определимых числе. Чисел свойство которых описывается конечной цепочкой слов. Например нет ни конечной не бесконечной алгебраической формулы для вычисления простых чисел. Но мы можем сказать "первое простое число", "второе простое число", "третье простое число" или "первое член в 1234333 простой паре близнецов". Можно так определять число? Можно. И наверное множество всех ранее нами определенных числе являются всего лишь подмножеством этого множества. Но и это множество счетное. Ведь любое описание – конечная цепочка символов. Со всеми вытекающими отсюда последствиями –счетностью множесва. Поэтому на числовой оси все равно остается бездна каких-то темных числе, которыми почти полностью заполнена числовая ось, а все эти наши множества фактически ничего там не весят!

Как долго мы будем продолжать эту игру с матрешкам?

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

Вычислимые числа это числа, которые вычисляются на его машине. Машине Тьюринга. Сейчас мы легко можем сказать, что вычислимые числа это те числа, для вычисления которых найдется некоторая компьютерная программа печатающая их ПРАЗРЯДНО на своем выходе.

(я думаю все понимают что абстрактная программа не ограничена как реальные программы верхним пределом значений того или иного типа данных? У машины Тюбинга один тип данных infininteger :)

Например, программа, печатающая как-нибудь натуральное число очевидна. Например печатающая число 3.

. . .

begin

Write("3");

end.

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

А как с действительными числами? Вычислимо ли 1/3?

Ну почему бы и нет? Вот фактически универсальный алгоритм приспособленный для вычисления 1/3:

. . .

begin

a:=1; b:= 3;

While l0 do begin

If ab then begin

c:=a mod b;

Write(c);

l:=a div b end

else begin

a:=a*10;

Write("0");

end;

end.

Правда здесь не печатается десятичная запятая, но это для нас не существенно.

Важно, что этот алгоритм будет печатать:

033333333333333333....

Стоп. Но он никогда же не остановится!

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

Хорошо, а программа вычисляющая любое алгебраическое число возможна?

Конечно возможна (детали могут озадачить, но это вопрос для школьников физ.мат.школ. перепрыгнем его). А для трансцендентного числа?

Например, числа "пи" или "е"? Есть программа? Есть! И не одна!

А для определимых чисел? Скажем программа, которая бы печатала тот самый первый член 1234333 простой паре близнецов? Есть и такая программа!

Конечно не для всех определимых, но есть и для них.

В общем множество вычислимых чисел это наиболее общее множество чисел включающее почти все ранее определенные нами подмножества. Это все числа которые можно как то ВЫЧИСЛЯТЬ. И не важно остановится процесс их вычисления или нет. Остановится – ну и ладно. Нет – тоже нормально.

Можно даже сделать так. Пускай все программы зациклятся. Если программа вычисляет натуральное число 3 то пускай она напечатав цифру 3 напечатает десятичную точку и дальше без конца печатает нули:

3. 0 0 0 0 0. . . .
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 1 сентября 2004 г., 02:51
Дурное дело не хитрое. Зациклим все программы для армейского единообразия!

Ибо скоро нам их придется выстраивать их в шеренгу Кантора.

И так. Уловили смысл ВЫЧИСЛИМОГО ЧИСЛА?

Является множество вычислимых чисел счетным? Конечно. Ведь всякая программа есть всего лишь конечная цепочка символов. Поэтому даже множество вычислимых чисел на числовой оси не покрывает всех чисел. А значит существуют НЕВЫЧИСЛИМЫЕ ЧИСЛА. Не вычислимые ни на какой машине Тьюринга!

Уловили и это?

Тьюринг задался такой проблемой. А нельзя ли воспользоваться диагональной процедурой Кантора как ВЫЧИСЛИТЕЛЬНЙ ПРОЦЕДУРОЙ и сделать невозможное: вычислить какое-нибудь невычислимое число?!

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

Смотрите. Программа работает циклически.

Первая итерация

Программа печатает первый разряд первого вычислимого числа.

Вторая итерация.

Программа печатает второй разряд первого числа

Программа печатает первый разряд второго числа.

Третья итерация.

Программа печатает третий разряд первого числа

Программа печатает второй разряд второго числа.

Программа печатает первый разряд третьего числа.

. . .

N-тая итерация.

Программа печатает N-тый разряд первого числа

Программа печатает N-1 разряд второго числа.

Программа печатает N-2 разряд третьего числа.

. . .

Программа печатает первый разряд N-того числа.

. . .

Идея ясна? Очень необычная но богатая идея.

И так подобная суперпрограмма возможна. Она как Змейка Кантора будет непрерывно обползать и выпечатывать верхний правый фрагмент таблицы всех вычислимых чисел. Все что нам осталось – брать диагональ и инвертируя в ней цифры печатать рядом НЕВЫЧИСЛИМОЕ число. Число, которого наверняка нет в бесконечной таблице вычислимых чисел.

Но разве это невычислимое число?

Как такое может быть?

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

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

Это оригинальная идея доказательств Тьюринга Проблемы Остановки в его работе о невычислимых числах. Что бы выгородить все это он фактически изобрел УНИВЕРСАЛЬНЫЙ КОМПЬЮТЕР. Странно, не правда ли?

Ради такой абстрактной глупости создать такую ВЕЩЬ!

Мы тоже здесь ищем ответы на "дурацкие" вопросы.

Каким боком может это выйти?

Конечно может ничего не выйти. Мало ли дураков мучают себя глупыми вопросами. Не всем быть Тьюрингами!

:))(

Я знаю еще два доказательства Проблемы Остановки. Самое простои и изящное не столь громоздко.

Допустим существует разрешающая процедура T(p, x) такая что выдает "1" если программа Р(x) c геделевым номером p останавливается, если ей на вход подается число x. Если же Р(x) не останавливается, значит программа T(p, x) печатает "0". Это записывается так:

..................1, если Р(x) останавливается

T(p,x) ={

..................0, если Р(x) НЕ останавливается

Тогда напишем следующую программу B ("брадобрей")

. . .

begin

Read(x)

While T(x,x)=1 do

begin end;

end.

И скормим на вход программе B ее геделев номер. Что получаем? Если процедура T приходит к выводу что программа В получив на вход свой геделев номер не зациклится, то она, выдаст 1 и . . . программа В ЗАЦИКЛИТСЯ. Если же программа T выдаст 0 – зациклится, программа В благополучно остановится.

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

Теорема Тьюринга об Остановке доказана.

Зачем я все это здесь так долго рассказываю? Я хотел показать что я стою на плечах гигантов. И напомнит как все там красиво взаимосвязано и надезно закрыто и как квантово-механический НЕВЫЧИЛСИМЫЙ луидор во все это вписывается.
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 1 сентября 2004 г., 02:52
Можно уверено гнать отсебятину пологая что ты один видишь нечто великое а все вокруг - дураки. Особенно это хорошо делать на "философии". И там я тоже могу смеяться, ругаться злиться что меня не понимают. Но здесь у меня в руках оказался неразменный пятак! Я его сдаю, а он возвращается! И так и сяк. Но чудо на лицо! Как не крути! :)(

Вот стоит бесконечный ряд абстрактных машин Тьюринга которые деловито печатают и печатаю разряд за разрядом ВЫЧИСЛИМЫЕ числа. Секунда разряд, вторая –еще разряд. Третья – еще разряд. Бесконечный ряд бесконечных лент. Я становлюсь рядом и в такт и работе начинаю подсасывать свой пятак.

Орел

1

Решка

10

Решка

100

Орел

1001

. . .

Чем мой процесс отличается от того что происходит внутри БЕСКОНЕЧНОГО ряда машин? Внешне - ничем. Это еще один черный ящик который без остановки печатает разряды некоторого числа. И у них и у меня процесс никогда не остановится. некоторые из тех машин зацикливаются. Ну и бог с ними. Но моя гарантированно не зациклится. Гипотетическая диагональная машина Кантроа должна была так же печатать невычислимое число бесконца. Но Тьюринг показал что она обязательно где-то "повиснет" как толко повиснет одна из тех в бесконечном ряду. А мой пятак не зависает. Он вообще ни от чего не зависит. Дзинь, и происходит редукция волновой функци. Дынь! Еще раз. Всякий раз происходит не вычислительная не редуцируемая ни к каким вычислениям процедура. Процедура математически чисто случайный выбор.

Решка

10011

Решка

100111

Орел

1001110

. . .

Никаких проблем остановки!!!!

Так все-таки что у меня в руках?

:)))

ЗЫ:

Цитата:

*************

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

Вероятность достоверного события равна 1

. . .

Событие V называется невозможным в данном эксперементе, если оно не может произойти в нем никогда. . . Вероятность невозможного события равна 0

***********

"Вероятность вокруг нас". А.В. Скороходов.

О бросании точки на плоскость и вероятности попасть точкой в заданную точку равное 0. Здесь нет противоречия. Фактически описанная процедура с луидором и есть вариант такого бросания. Мощность невычислимых на плоскости точек – континуум, а точек, которые мы можем назначить вычислением к попаданию – счетное множество. Это значит что какую бы точку мы не назначили, случайно бросив на плоскость пробную точку мы достоверно в нее не попадем в силу бесконечной малости площади вычислимых точек по отношению к невычислимым. Но о чем это говорит? Это говорит, что с помощи процедуры случайного бросания мы "вычисляем" ЛЮБОЕ действительное число. Но вероятность попасть на такое действительное число, чтобы оно еще было и вычислимым равна нулю. Этого никогда не происходит. Поэтому все получаемые так числа - невычислимые. Гарантированно невычислимые.

Как не крути, но мы все же превзошли машину Тьюринга в решении задачи о невычислимых числах!
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 1 сентября 2004 г., 03:18
Перечитал отправленный текст и ужаснулся. Я очен часто путаю название рациональных чисел с дейтвительными и даже натуральными. Это очень плохо! Людям непосвященным все запутает. :(((

Корректируйте меня пожалуйста по контексту.
Информация о пользователе dzver
dzver
Скрыть | 1 сентября 2004 г., 06:04
Alexandr_Semenov

Вы очень интересно пишете. Вам бы преподом быть.

Как обычно, я с почти всем согласен.

Однако, поясните пожалуйста, следние моменты.

1.

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

Да, но..

Это говорит, что с помощи процедуры случайного бросания мы "вычисляем" ЛЮБОЕ действительное число.

А вот с етим не совсем согласен. Мы ничего не вычислили, потому что никакое число не назначили предварительно. И именно поетому как вероятность, так и "вычисление" здесь несколько непричем.

Ваш метод "вычисления вычислимых чисел" - вычисли то - не знаю что.

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

2. С другой стороны, все надо рассматривать в контексте принятых аксиом и правил вывода. Дополним базисных функций /правил вывода/ с еще одну безаргументную: "Rand()". Она выдает 0 или 1 в 50% случаев АБСОЛЮТНО СЛУЧАЙНО. /Несложно физически построить ее и дооборудовать обычную машину Тьюринга с ней/.

Тогда программа печатающая невычислимые числа записывается конечно и просто:

begin

While True do

Print Rand();

end.

Но подумайте, любая такая формула – это конечная цепочка символов. А множество таких конечных цепочек счетное.

Программа выше - тоже конечная цепочка символов, как и наша 4-символьная функция "Rand()".

3. Мое третье возражение дублирует 2 но ето скорее вопрос.

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

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

Про бесконечности и зацикленные машины Тьюринга, вычисляющие бесконечные вычислимые числа.

Все, что я хотел сказать, что выражение:

"данная конечная машина Тьюринга No.3293293 вычисляет число pi",

в физической реальности надо понимать как:

"МТ No.3293293 вычисляет число pi с любой ЗАПЕРЕД заданной точности"

а НЕ как

"МТ No.3293293 на самом деле вычисляет число pi".

Потому что МТ No.3293293 число pi никогда не вычислИТ.

(если хотите можете сказать что она исчислит pi на бесконечности но ето то же самое что и никогда).

Определение выше /"МТ No.3293293 вычисляет число pi с любой ЗАПЕРЕД заданной точности"/ вполне в согласии с обычной дефиниции вычислимых чисел, но его ясно как понимать в реальности и мозги не пудрит.

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

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

Т.е вот такой сценарий.

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

Вы утверждаете что нет.

Что наблюдается?

Вы бросили 101.

Ждем известное время и моя МТ выдает где-то 101.

Вы бросаете ноль, сейчас ваше число получается итого 1010.

Мы опять ждем и после некоторого большего времени моя МТ выдает и 1010.

И так на каждом етапе /моя машинка МТ будет медлит конечно, експоненциально, но все-равно "догонит" каждую вашу конечную последовательность/.

А ето все, что важно по отношении к реальности.

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

Кстати "любая заданая точность" - ето тот же самый прием с который по-моему Коши определил коректно /и физически смысленно!/ бесконечно-малые в дифф. счисления.

И наконец, про Реальности /откуда все и началось/.

Я согласен, что реальность похоже НЕ является полностью детерминирована - как "механические часы" /в смысле Лапласа/.

Но, она спокойно может быть "Rand-вычислимой" - т.и. вычислимой машиной Тьюринга с присобаченной функции Rand().

И, я думаю что именно ето имел ввиду Дойч /а не механическая вычислимость типа Лапласа - т.е. обычной машине Тьюринга/.
Информация о пользователе dzver
dzver
Скрыть | 1 сентября 2004 г., 06:57
тьфу, ЗАПЕРЕД=НАПЕРЕД
Информация о пользователе dzver
dzver
Скрыть | 1 сентября 2004 г., 10:15
Да, может быть и про етого надо сказать.

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

Как он так лихо берет и упорядочивает бесконечные цепочки? Как это он строит бесконечную диагональ? И как это он так легко выводит, актуализирует свойства некоторого бесконечного объекта?

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

И почему вы назвали их "актуальными бесконечностями"?

Таким же образом - доказательство что множество натуральных чисел равномощно множеству четных чисел (своего собственного подмножества)- сводится до соответствием x=2*y - и "актуальная бесконечность числового ряда целиком" на самом деле нигде не изпользуется.

Хотя мы можем написать их для иллюстрации:

y: 1, 2, 3, 4, 5, 6, 7, 8 ......

x: 2, 4, 6, 8 .......

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

Етот рисунок - просто же иллюстрация к доказательству.

Тем же образом, Канторова матрица - тоже иллюстрация - а не "построение актуальных бесконечных множеств".

Другими словами, метод Кантора вполне формулируется старым добрым "допустим что... тогда для каждого конкретного... найдется... такое что...противоречие с допущением" - т.е. бесконечности не должны быть "актуальными".

С другой стороны, математические бесконечности нельзя автоматически перебрасывать на Реальность - поскольку реальность всегда "актуальна".

Математический натуральный ряд бесконечен -но у вас есть весомые аргументы что произвольно большие числа могут быть физически осмысленны /типа брой нуклонов во вселенной более чем любого наперед заданного числа... общая енергия вселенной больше чем любого наперед заданного числа...и т.д/?

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

Я вспоминаю это, потому что меня обвинили в том же. Что я перескакиваю через бесконечность. Это смешно.

Нет.. Вас никто не обвинил что перескакиваете через бесконечность.

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

Ну скажите ради бога откуда вы знаете что в реальности невычислимые числа существуют?

Чтобы утверждать етого, мне кажется необходимо привести примера - типа доказать что физически осмысленное отношение не зависящее от с-ме измерение единиц /напр. отношение массы покоя електрона к массы покоя протона/ - суть величина невычислимая. Или что-то вроде. Такое доказательство ясно, нельзя привести пока физика не полностью аксиоматизирована:) А если она и никогда не будет полностью аксиоматизирована /Теория Всего/ то и никогда не станет ясно как вещи обстоят на самом деле..
Информация о пользователе dzver
dzver
Скрыть | 1 сентября 2004 г., 10:34
Чем мой процесс отличается от того что происходит внутри БЕСКОНЕЧНОГО ряда машин? Внешне - ничем. Это еще один черный ящик который без остановки печатает разряды некоторого числа.

Верно..

И у них и у меня процесс никогда не остановится. некоторые из тех машин зацикливаются. Ну и бог с ними. Но моя гарантированно не зациклится.

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

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

1 шаг: 0,1

2 шаг: 00,01,11,10

3 шаг: 000,001,010,011,110,111,100,101

.........

Назовем ее МТ01.

Гипотетическая диагональная машина Кантроа должна была так же печатать невычислимое число бесконца. Но Тьюринг показал что она обязательно где-то "повиснет" как толко повиснет одна из тех в бесконечном ряду. А мой пятак не зависает.

МТ01 тоже не повиснет.

Он вообще ни от чего не зависит.

МТ01 зависит от своего алгоритма - но зато какой он мощный:)

Дзинь, и происходит редукция волновой функци.

Дзинь, и МТ01 выплюнула 2^n чисел - ваша текущая последовательность среди них.

Дынь! Еще раз.

Дзинь, и МТ01 выплюнула уже 2^(n+1) чисел -ваша текущая последовательность опять среди них.

Всякий раз происходит не вычислительная не редуцируемая ни к каким вычислениям процедура. Процедура математически чисто случайный выбор.

Зато каждый раз МТ01 догоняет, "охватывая" ваше текущее число...

Хотя и процедура МТ01 вполне вычислительная /и, надо признать, более трудоемка чем ваша/...

Никаких проблем остановки!!!!

МТ01 тоже никогда не остановится, гарантировано:)

Так все-таки что у меня в руках?

:)))

В етом и вопрос? Что-же так необычного здесь...?
Информация о пользователе Pier_V_Tin
Pier_V_Tin
PROFESSION DE FOI
E-mail: pier_v_tin@front.ru
Скрыть | 2 сентября 2004 г., 03:52
Alexandr_Semenov:

Как может существовать бесконечное число Z-машин Тьюринга, которые одновременно могут, и остановиться, и не остановиться?![имеется ввиду что существует неперечислимое множество предложений в языке Арифметики таких что присоединение их или их отрицаний к аксиоматической Арифматике Пеано (в дальнейшем PA) не ведет к противоречию]

___________________

Alexandr_Semenov предложил кодировать _каким-либо образом найденные_ недоказуемые в PA утверждения "Ф" в форме

1)(Ex)(Ez)Т(x,y,z) и

2)(Ex)(Az)~T(x,y,z)

где x - номер машины Тьюринга, y - номер утверждения "Ф", z=(t,u) - номер пары, где t - число шагов вычислений, u - принадлежит множеству {True,False}, (E) - существует, (A) - для любого.

В случае (1), в общем, из u=True не следует что (Ex)(Et) Т(x,"~Ф",(t,False)),так что такое присоединение утверждений вида (1) или (2) ни к чему не обязывает кроме следствий непротиворечивости. Возмем "0=0", доказуемое в PA. Но (Ex)(Et)Т(x,"~0=0",(t,False)) ложно так как мы исходим из того что PA непротиворечива (и неполна). Следовательно (Ax)(At)~Т(x,"~0=0",(t,False))(утверждение о недоказуемости непротиворечивости PA). Но возможно ли что для всякого утверждения "Ф" истинно (Ex)(Et)T(x,"Ф",(t,True)) & (Ex)(Et)Т(x,"~Ф",(t,False))? Если же "Ф" полуразрешимо то у нас не найдется номера машины для одной из формул. Такие новые номера соответствуют именам машин Ораклов отвечающих на определенные трудные вопросы. Все разрешимые задачи решаются в PA, так что мы имеем здесь вложение в аппарат доказательств PA разрешающее применимость закона исключенного третьего к рекурсивно перечислимым множествам.

В случае (2) мы присоединяем отрицание предложения с номером y - "~Ф" так что будем считать что (Ex)(Et)T(x,"~Ф",(t,True)) для некоторой машины с Ораклом.

Теперь заметим что любому номеру x машины Тьюринга соответствует р.п. множество X на котором она выдает значение True за конечное число шагов, но y у нас из дополнения к р.п. множеству - Y (множеству недоказуемых в PA предложений). Объединение всех таких пересечений множеств X с Y есть р. п. множество, так что как бы мы ни кодировали нерешаемые задачи машинами Тьюринга мы несможем закодировать их всех(для этого придется использовать тренсфинитную рекурсию).

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

Гедель установил что для всякого рекурсивно перечислимого отношения R(x) существует полиномиальное отношение (Ey)(P(x,y)=0) с некоторым кванторным префиксом (Ю.В.Мятисевич доказал достаточно кванторов существования) истинное тогда и только тогда когда истинно R(x) (у нас (Ex)(Ez)Т(x,y,z) = (Ew)(P(w,y)=0), (Ex)(Az)~T(x,y,z) = (Ew)(P(w,y)=0)). Как только мы нашли машину Тьюринга удоволетворяющую (1) или (2) и некоторое недоказуемое в PA утверждение "Ф", этой находке будет соответствовать полуразрешимое утверждение (Ew)(P(w,"Ф")=0). Таким образом каждое недоказуемое в PA утверждение соответствует утверждению о существовании корня w (неразрешимого в PA) уравнения P(w,"Ф")=0.

Теперь мне хочется проделать следующее:

Пусть доказуемо, или же принято на веру утверждение что для некоторого "Ф" (Aw)~(P(w,"Ф")=0). Т.е. "Ф" неприсоединимо. Мы расширяем область определения теории такими w что P(w,"Ф")=0 выходя за пределы натуральных чисел, как это делалось ноднократно с вещественными числами и с мнимой единицей. Таким образом предложение ложное в PA, оказывается истинным в новой теории. Конечно такое расширение затрагивает все прежние предложения содержащие квантор всеобщности. Может оказатся что (Ex)x=x+1 например или можно получить кольцо целых чисел исходя из того что (Ex)x+1=0,... Здесь вопрос смещается со свойств множеств которые определяются этими формулами на свойства формул _истинных_ при некоторой интерпретации, которые могут сильно отличатся.

Alexandr_Semenov:

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

_________________

Есть такие объекты обладающие этим свойством, очень простые, это лямбда-термы. См.:

http://www.andrew.cmu.edu/user/cebrown/notes/baren dregt.html

Там важно лишь что если останавливаются то с одинаковым выходом.
Информация о пользователе NO
NO Участник Клуба
WWW: 4spam2no@mail.ru
Скрыть | 2 сентября 2004 г., 22:20
Alexandr_Semenov

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

Слово "аксиома" как раз и происходит от слова "ценность" :)

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

Мойте руки после программирования, вот и вся метаматематика.
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:46
"Хотя этот топик и умер, зато он наиболее интересный из всего что здесь обсуждают..."

давно я тут не был и тоже думал, что топик умер. а он, оказывается, цветет и пахнет ;)

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

я думаю, что лет через 100-200 ответы на вопросы из этого форума будут изучать в школе в базовом курсе математики ;)
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:47
Александр Семенов:

30 августа, 17:12 Вы пишете: "Я не уверен. Это очень смутная догадка ни к чему не обязывающая"

ничего не понял. какая догадка? та, что МТ состоит из твердых детерминированных частиц? или что МТ может дать сбой? так это неверно по определению МТ. или то, что МТ в тезисе Тьюринга - не та, которая им же формально описана, а имеющая какое-то физическое воплощение? или что-то другое? говорите яснее.
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:48
"Мы должны построить формальную теорию матемаики. {A, R, O}"

вот они, скользкие моменты! давайте строить по аналогии с исчислением предикатов. "A - набор символов теории" - для формальной теории на этом месте стоит не алфавит, в котором записываются высказывания теории (алфавит - это забота исчисления), а множество констант предметной области. если мы хотим, чтобы построенная математика могла работать дальше с целыми и действительными числами, то мы должны включить во множество A множества R и Z. то есть, чтобы я мог написать (Ex)x=\pi (здесь под \pi я буду подразумевать одну греческую букву, а не три знака), то множество всех предложений теории уже не будет счетным (т.к. A - континуум). если все-таки мы захотим сделать A конечным/счетным и принудительно добавим \pi к выбранному алфавиту, то как быть с целым континуумом других констант? если A - не континуум, то некоторые предложения (в частности, с использованием констант) не могут быть записаны в нашей новой математике. а если континуум – то рассуждения насчет счетности всех предложений теории рассыпаются. R - набор манипуляций. тут все понятно, можно взять правила вывода из какой-то логики. O – аксиомы. как заранее так определить набор аксиом, чтобы он подошел и для теории чисел, и для анализа, и для всех остальных приложений. в каждой теории по отдельности набор аксиом более-менее устоялся, а для математики вообще все аксиомы свалить в кучу нельзя – кто будет доказывать непротиворечивость такой системы? теперь подходим к центру проблемы.
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:49
как узнать, невыводимые высказывания истинны или ложны? прежде чем браться за такую задачу, определим истинность высказывания P(t1) для константы t1. в формальной теории, построенной на базе исчисления предикатов, так: значения термов на константах тоже заданы (входят в конструкцию теории) то есть если s – функциональный символ, s(x,y,z) – функция, s(a,b,c) – терм, a,b,c – из множества A, тогда мы всегда знаем, что s(a,b,c)=d, d – тоже из A. значения предикатов на константах (значит, и на всех термах) задаются интерпретациями (то есть в конструкцию теории нужно внести еще одно множество). то есть истинность конкретного предложения зависит от интерпретации. предложения с кванторами проверяются с привлечением множества констант A, с которым мы пока не определились. краткое резюме сказанному: выводимость (в формальной теории) никак не связана с истинностью. если мы вывели (Ax)P(x), то истинность определяется интерпретацией P, и конечно, множеством констант, которые будет пробегать квантор.
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:52
по поводу 31 августа, 18:29.

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

ещё одна мысль на тему – если Вы проводить опыт с бросанием монетки (предположим даже, если на бесконечности вы его закончите), у Вас всего будет всего одно невычислимое число, но таких чисел намного больше, как получить другие? континуум Александров Семеновых, бесконечное число раз бросающих монетку, поражает больше, чем не останавливающаяся и останавливающаяся одновременно машина Тьюринга ;)
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:52
уважаемый участник клуба, призываю к математической строгости!

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

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

3. как Вы можете говорить о результате вычисления МТ, которая никогда не остановится. где гарантия, что машина, предположительно печатающая 1/3, после 3000 шагов (или 8000, кто знает…) не вернется назад и не сотрет напечатанные тройки, напечатав вместо них пятерки. в этом смысле она никак не может быть эквивалентна программе, которая печатает тройки и для которой точно известно, что от напечатанных троек она уже не откажется. таким образом, говорить об эквивалентности программы и МТ можно лишь в случае, когда МТ останавливается и с оговоркой, что в определенном месте ленты мы обнаруживаем тот же результат, что и вывод программы. в этом смысле все не останавливающиеся машины эквивалентны, и мы не можем различить машину, печатающую невычислимое число от другой такой же зациклившейся.

4. «Вероятность достоверного события равна 1. Вероятность невозможного события равна 0». по определению, да. но из этого не становится верным обратное утверждение, на которое Вы ссылаетесь: «вероятность попасть на такое число […] равна нулю. Этого никогда не происходит. Поэтому все получаемые так числа - невычислимые»

p.s. не сочтите за наезд, но на этом форуме строгость не повредит.
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:54
Pier_V_Tin:

простите, но у меня небольшой пробел в терминологии: что такое неперечислимое множество: бесконечное, счетное, мощнее, чем счетное, или какое-то другое?

ещё вопрос: есть ли смысл вводить в T(x,y,z) переменную x? как я понял, T – отношение, связывает множество машин с номерами x, которые, получив на вход y, выдают z=(t,u). У Александра машина уже задана x=m (и точно известно, что её можно построить, т.е. что константа m есть в предметной области), почему бы для удобства не переобозначить T(x,y,z)=T(m,y,z)=T1(y,z). для краткости, T(y,z). или принципиально важно, что рассматриваются все МТ, даже те, которые не предназначены для проверки утверждений?
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 3 сентября 2004 г., 19:09
Я в отпуске. Дома подключиться к сети пока не могу раньше чем завтра. Сейчас оказался на работе. Заглянул сюда. Да, тема жива! :))) Попробую ответить за выходные. Замечание о строгости принимаю. Посыпаю голову пеплом. :)(
Информация о пользователе Pier_V_Tin
Pier_V_Tin
PROFESSION DE FOI
E-mail: pier_v_tin@front.ru
Скрыть | 3 сентября 2004 г., 22:22
I.Множество рекурсивно перечислимо (полуразрешимо) если оно есть либо область определения либо область значений какой либо частично-рекурсивной функции (машины Тьюринга).

II. Множество рекурсивно (разрешимо) если и оно и его дополнение рекурсивно перечислимо.

Для р.п. множеств функция-индикатор выдает предположим 1 на его элементах и все остальное включая случай неопределенности на прочих элементах. Для рекурсивного множества функцию-индикатор можно задать всюду определенной чтобы она выдавала 1 на элементах множества и 0 (или любое число кроме 1) на его дополнении.

Все конечные множества рекурсивны.

T(x,y,(t,z)) - "Машина с номером x получив на входе y через t шагов заканчивает работу и выдает z" - предикат Клини.
Информация о пользователе dzver
dzver
Скрыть | 3 сентября 2004 г., 22:31
SMT

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

квантовая механика, вроде, дает гарантию; его монетка не классическая а квантовомеханическая
Информация о пользователе 7-40
7-40 Участник Клуба Золотое перо
WWW: Tuline eesti poiss - Горячий эстонский парень
Скрыть | 4 сентября 2004 г., 00:09
222AVIA:

С: Так что думаю, что думающий чел (типа

С: аналитик) всегда может найти ошибки,

С: даже не обладая всеохватывающими

С: знаниями.

Сергей, вспоминаю несколько диалогов с Вами. Вы (если не ошибаюсь) называли себя аналитиком и уже не раз приписывали себе способность "найти ошибки, даже не обладая всеохватывающими знаниями". Простите, если обижу Вас напоминаниями - но как раз в тех самых случаях Вы как раз и ДОПУСКАЛИ ОШИБКИ, причём элементарные. Т. е. речь об обнаружении не шла вообще - дай бог самому не ошибаться.

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

По поводу цитаты из Ландау: он имел в виду, очевидно, не знание устройства автомобиля, а именно умение управлять им. Если человек не умеет управлять автомобилем - попытки сесть за руль чреваты. Если человек не разбирается в предмете - попытки выносить суждения по нему тоже чреваты. Даже если этот человек называет себя аналитиком.

С искренним уважением к Вам... ;-)
Информация о пользователе 7-40
7-40 Участник Клуба Золотое перо
WWW: Tuline eesti poiss - Горячий эстонский парень
Скрыть | 4 сентября 2004 г., 00:10
Ой! Не туда полетело! Сорри!
Информация о пользователе SMT
SMT
Скрыть | 4 сентября 2004 г., 02:41
Александр Семенов

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

Pier_V_Tin

конечно, если обозначение T(x,y,z) общепринято, давайте пользоваться им

dzver

я еще не дошел до функции R в теории квантовых вычислений. но у меня уже сомнения - почему именно случайность, а не очень большой количество невидимых внутренних состояний (или случайность в КМ - по определению?)
Информация о пользователе SMT
SMT
Скрыть | 4 сентября 2004 г., 02:44
вот что мне не нравится в диагональной процедуре: требуется, чтобы каждое число однозначно кодировалось последовательностью цифр. с учетом того, что 0.49999999…=0.5000000… специально оговаривается, что 0.499999… - это не число. то есть кодировка уже не взаимно-однозначная. при построении диагонального числа Кантора нужно убедится, что получается число (то есть нет девяток в периоде). для десятичного представления проблем нет, договариваемся никогда не выбирать девятку, а для двоичных последовательностей, которые использовались в примерах выше, все сложнее.

дальше пойдет ненаучная фантастика, просьба не комментировать:

непонятно, является ли числом последовательность

0.4 (999 бесконечно много девяток 9999) 0 (000 бесконечно много нулей 000)

если это число, рациональное оно или нет?

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

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

сопоставив ящики (программы конечной длины внутри них) с последовательностями, думаю, нужно рассмотреть более компактную запись бесконечной последовательности, а именно, как функцию f: N-{0,1}

потом нужно определить операции над такими функциями (в общем-то, операции над программами не новость) и построить пространство функций. если оно конечномерно (что вряд ли по аналогии с анализом, где даже непрерывные функции уже образуют бесконечномерное пространство, а может и конечномерно для программ некоторой длины, не превышающую наперед заданную), то раскладывая по базису, получим интересный способ анализа и синтеза алгоритмов. бред, короче.
Информация о пользователе dzver
dzver
Скрыть | 4 сентября 2004 г., 08:44
SMT

dzver

я еще не дошел до функции R в теории квантовых вычислений. но у меня уже сомнения - почему именно случайность, а не очень большой количество невидимых внутренних состояний (или случайность в КМ - по определению?)

Да, eто постулат /принцип/.

На тот принцип однако есть [физически веские] основания.

Почему не очень большое количество внутренних состояний:

- скрытые параметры /какие бы то они не были/ дают для запутанных пар предсказания отличающиеся от предсказаний КМ /нер. Белла/. Ето експериментально проверено в лоб и результаты однозначно потверждают предсказаний КМ и не стыкуются со скрытыми параметрами /не конкретные скрытые параметры, а вообще с возможностью скрытых параметров независимо от их сорта и как они именно влияют/.

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

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

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

Например, нельзя доказать что кв.мех случайность не является результатом мгновенного нелокального "взаимодействия" всех объектов вселенной с измеряемой частицы /слово "взаимодействие" в кавычках потому что оно не передает информацию, а только налаживает нелокальную корреляцию - иначе СТО летит на хер а она хорошо потверждена/.

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

И здесь слово "постулат" скорее надо интерпретировать в смысле что ето а) в корне расходится с настоящих теорий которые отлично потверждены б) експериментальная проверка в лоб дала результаты которые несовместимы /никак не могут быть объяснены - ето доказывается математически/ с помощью локальных скрытых параметров.

Итого - скрытые параметры - возможны, но они должны быть раз нелокальные, два не переносить информации а только налаживать корреляции - что само по себе уже вроде делает их неиспользоваемыми для физике.
Информация о пользователе SMT
SMT
Скрыть | 4 сентября 2004 г., 14:28
dzver:

ну что-ж, буду читать Фейнмана...

значит, если с помощью КМ можно получить настоящее случайное число (экспериментально), то тезис Тьюринга под сомнением (как же так, какой-то физик может вычислить СЧ, а машина Тьюринга - не может)

Александр Семенов:

мое сообщение от 3 сентября, 17:48

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

вместо

(Ex)x=\pi

пишем

(Ex)(Ez) x=z & P(z)
Информация о пользователе dzver
dzver
Скрыть | 4 сентября 2004 г., 21:22
SMT

значит, если с помощью КМ можно получить настоящее случайное число (экспериментально), то тезис Тьюринга под сомнением (как же так, какой-то физик может вычислить СЧ, а машина Тьюринга - не может)

Именно что я считаю что ето не так.

Что имеете ввиду под "получить настоящее случайное число".

Если вы о бесконечную случайную дробь Семенова "целиком" - т.е. "актуально", то для етого привлекать КМ не необходимо.

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

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

Если вы под "получить настоящее случайное число" имеете ввиду генератор нулей и единиц который их генерит абсолютно случайно /а не псевдослучайно/ - напр. с вероятности 50%-50% - да, КМ дает возможность получить физически такого генератора - которого из классической МТ в принципе нельзя получить.

Ниже под "генератора случайных чисел" я понимаю именно такого генератора символов 0 и 1 с абсолютной 50%-ной случайности - а не генератора бесконечной случайной дроби "целиком" какого не существует.

И мое утверждение состоит в том, что вычислительная мощность МТ с ИГСЧ /идеальном генераторе случайных чисел/ физически такая, как и вычислительная мощность обычной МТ, если рассматривать их не на "актуальной бесконечности", а на конечном, хотя и произвольно большом интервале.

Поскольку вычисления производимые МТ с ИГСЧ /случайных МТ/ могут быть возпроизведены разветвляющимся множеством обычных МТ.

Т.е. на каждом конечном етапе своего вычисления результат МТ с ИГСЧ не содержит ничего такого которого невозможно получить обычным МТ.

Поетому никакой физик или квантовой компьютер таким образом вычислить невычислимое число тоже не может.

Утверждение Семенова что они /МТ с ИГСЧ и МТ без ИГСЧ/ различаются на актуальной бесконечности - хотя и может быть математически верное - но физически ему нельзя придать смысла.

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

Просто нам надо "посмотреть на актуальную бесконечность" и "там" воочию увидим, остановилась ли обычная МТ или нет.

Я тоже думаю, Семенову надо четко определится что он именно утверждает...
Информация о пользователе SMT
SMT
Скрыть | 5 сентября 2004 г., 02:59
нужно ввести характеристику конечной длины для любой последовательности (конечно, о взаимно-однозначном соответствии речи нет), предъявив которую, мы бы доказали, что "вычислили" последовательность. например, остаток от деления суммы цифр на 10. такая величина имела бы смысл, если бы, с одной стороны, она для каждой последовательности сходилась, и, с другой, хорошо бы характеризовала последовательность. циклическая сумма не сходится для иррациональных чисел, давайте попробуем придумать что-то другое.
Информация о пользователе dzver
dzver
Скрыть | 5 сентября 2004 г., 03:47
SMT

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

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

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

Например, цепочка Семенова имеет статистическое свойство что среднее всех разрядов клонит к 1/2 - частота встречания 0 и 1 в любой подцепочки одинакова и клонит к 1/2 с увеличением размера подцепочки.

Но напр. периодическая последовательность 0.101010101.... имеет того же свойства; можно придумать и непериодические последовательности такого рода - напр.

0.011011100101110.... /образовано как конкатенация бинарных представлений натуральной последовательности, аналог в десятичном записи 0.012345678910111213141516..../

Если бы возможно было сжать собственное бесконечное время в конечного временного интервала и понаблюдать за результатом извне...
Информация о пользователе SMT
SMT
Скрыть | 5 сентября 2004 г., 07:26
сам хеш (так я буду называть характеристику) доказательством считать нельзя. но он придуман не для доказательства факта, что машина что-то вычисляет, а чтобы в краткой форме представить результат. то есть Семенов говорит: "я вычислил". мы ему верим, но просим дать хеш, чтобы сверить с нашим результатом (если мы вычисляем одно и то же). неоднозначность будет, но ведь доверяют же CRC, хотя он тоже не дает 100% гарантии
Информация о пользователе dzver
dzver
Скрыть | 5 сентября 2004 г., 07:56
SMT

Назовем для краткости бесконечную цепочку из абсолютно случайных нулей и единиц "цепочку Семенова".

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

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

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

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

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

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

Но.. поскольку все конечные последовательности вычислимы, а цепочка на каждом етапе конечна /хотя и произвольно большая/ то такой хеш для конечных последовательностей всегда даст несовпадение, независимо дали ети конечные последовательности получались вычислением или являются конечное подмножество цепочку Семенова.
Информация о пользователе SMT
SMT
Скрыть | 5 сентября 2004 г., 09:18
вот теперь понятно! вычисление цепочек Семенова не соответствует научному методу :*) так как он не может повторить получение цепочки, то можно считать что он её и не получил
Информация о пользователе SMT
SMT
Скрыть | 5 сентября 2004 г., 09:23
;)))))))))))))
Информация о пользователе dzver
dzver
Скрыть | 5 сентября 2004 г., 10:00
так как он не может повторить получение цепочки, то можно считать что он её и не получил

Если бы он и хоть одну цепочку сгенерил:))

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

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

Может быть, такой тест и на самом деле является "хороший хеш" для цепочек Семенова? Хотя конечно ничего не доказывает.
Информация о пользователе SMT
SMT
Скрыть | 5 сентября 2004 г., 12:00
суть не в наличии цепочки. можно вместо цепочки взять генератор, функцию

f:N-{0,1}

но прежде чем говорить о такой функции, надо описать множества аргументов и значений, а также правила (формальные) для вычисления. если Александр опишет Семенова, бросающего монетку, настолько полно, что на это описание можно будет ввести в формальную теорию, то открытие состоялось
Информация о пользователе dzver
dzver
Скрыть | 5 сентября 2004 г., 12:24
можно вместо цепочки взять генератор, функцию f:N-{0,1} но прежде чем говорить о такой функции, надо описать множества аргументов и значений, а также правила (формальные) для вычисления

Eсли на цепочки Семенова имеется генератор с формальных правил для вычисления, она заведомо не случайна; во всяком случае, не больше чем числа pi или e.

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

/Возможность функцию типа Rand() реализующая ИГСЧ пока в расчет не берем поскольку ето "нечестно"/
Информация о пользователе dzver
dzver
Скрыть | 5 сентября 2004 г., 12:33
другой аргумент - если цепочка Семенова описывалась бы формальным алгоритмом f, то ето значит что f "компрессирует инфу репрезентируемой цепочки" до конечной фиксированной длиной описания самого f; но как известно, случайные цепочки не поддаются компрессии и длина генерящих программ соизмерима с длину самого результата, грубо говоря.
Информация о пользователе NO
NO Участник Клуба
WWW: 4spam2no@mail.ru
Скрыть | 5 сентября 2004 г., 15:21
Истинно случайными являются только числа Семенова-Чубайса - полученные на обесточенном компьютере.

И числа Семенова-Пифагора. Впервые эти числа упоминаются в трактате Декарта "К вопросу о эмуляции машины Тьюринга на конечном автомате", Декарт сообщает, что Пифагор детерминировал Семенову амфору с выломанным донышком, полную компакт-дисков с такими числами. По словам Семенова он это сообщение уже получил, но оно пока не дошло. Хотя по нашему общему мнению не может такого быть чтобы получил, но не дошло :)
Информация о пользователе Pier_V_Tin
Pier_V_Tin
PROFESSION DE FOI
E-mail: pier_v_tin@front.ru
Скрыть | 6 сентября 2004 г., 04:15
Вы знаете, есть такой раздел теории сложности вычислений где рассматриваются вероятностные машины Тьюринга.

Вероятностная машина Тьюринга это машина с дополнительной лентой на которой записана случайная последовательность 0 и 1. Такая машина на выходе выдает 0 или 1. Такая машина f вычисляет принадлежность входа x некоторому множеству L (которое в теории сложности принято называть языком) с некоторой ошибкой a(|x|) где |x| длинна входного слова.

x принадлежит L = Вероятность(f(x)=1)1-a(|x|)

x не принадлежит L = Вероятность(f(x)=1)= a(|x|).

В этой теории много результатов, например задача распознавания простых чисел решается на вероятностной машине Тьюринга за полиномиальное время, т.е. существует такая случайная величина \ksi и машина Тьюринга решающая эту задачу (при обращении к \ksi )...
Информация о пользователе SMT
SMT
Скрыть | 6 сентября 2004 г., 19:22
за полиномиальное время (от величины n входного числа) можно проверить простоту числа, просто поделив его на числа от 1 до sqrt(n).

только я не понимаю, почему в книжке написано, что лучший современный алгоритм Адлемана-Померанса-Румели дает результат за O((log n)^(c*log log log n))?

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

мои догадки правильны?
Информация о пользователе Pier_V_Tin
Pier_V_Tin
PROFESSION DE FOI
E-mail: pier_v_tin@front.ru
Скрыть | 8 сентября 2004 г., 06:20
Ну да. В этой науке почему то принято считать что машина правильно работает (распознает язык) если вероятность ошибки меньше 1/3. Я этого не понимаю.Но мы знаем что если нам удалось доказать недоказуемость V то мы можем прибавить к исходному набору аксиом старой теории как V и получить новую теорию, так и не-V и получить совсем другую новую теорию. То есть мы теперь можем иметь две разных математики и обе они будут истины!!!

Каждая из них будет внутренне непротиворечива но они будут противоречить друг другу.

А какая из них истинная? Обе. Проверить экспериментально мы не можем. Расширить теорию можно в той области математики, которую нельзя проверить. Так утверждение "2384043093423932311231 –простое число" можно проверить. Но это твердая часть математики и естественно доказуемое утверждение (есть примитивно-рекурсивный алгоритм который решает этот вопрос то есть гарантированно остановится). Утверждение "множество простых чисел бесконечно" уже экспериментально проверить уже нельзя. Здесь задействована бесконечность. Но мы знаем, что это утверждение рано или поздно будет напечатано на выходе алгоритма Р. Однако как быть с утверждениями, которые касаются непроверяемой бесконечности и могут оказаться не выводимыми в нашей теории?

Они либо истины либо ложны? Или оно никакое?

Если мы не исповедуем платонизм, то мы говорим что оно никакое. Именно этого касается фраза Подниекса. Задав А, R и O мы выдумали новый мир. Но задав А, R и O мы не можем выдумать его во всех деталях. В некоторых местах там "черные провалы". Он не обладает свойством быть сплошным даже там где нас нет как в нашей реальности. Математика это выдумка (Роджерс Пенроуз будет несоглашасен! :) как мир Гарри Потера. Разница в механизме их порождения. Мир Гарри Потера клеится из возможно противоречивых образов-цепочке и только в нужных местах, а математика строится как мозаика по раз и навсегда заданным правилам аксиоматически. И все. Но и такая мозаика покрывает не всю "плоскость рисунка" как ожидали математики.

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

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

Все нормально и логично.

Но давайте попробуем вообразить.

И здесь воображение начинает сдавать.

Возвращаясь к атомам воздуха, которые соберутся в одном конце комнаты. Это совершенно иная ситуация. Я говорю о реальности. Как она должна себя вести на бесконечность? Там где нас нет и никогда не будет. Но она там должна быть! Как реальность поступит с той частью математики где у нас дырки?

Вот я и пришел к крамольной мысли. Наблюдаемая нами реальность неадекватна той реальности которая есть на самом деле. Мы видим одну машину в нашей видимой одной реальности (классической реальности) потому что так устроено наше восприятие. В квантовой реальности существует бесконечное число машин (в мультиверсной интерпретации Эверетта) и для них вопрос остановится ли они все вместе или нет – не все варианты. На некоторых задачах они все вместе останвятся. На некоторых все вместе не остановяться. Но на некоторых, которые уходят на бесконечность, одни остановятся - один нет.

В общем я не вполне все это понимаю сам.

Как говориться, все это тема для медитации.

Кто-нибудь хочет помедитировать со мной?

:)
Информация о пользователе dzver
dzver
Скрыть | 31 августа 2004 г., 07:14
Alexandr_Semenov

Давайте помедитируем:)

Хотя мне по прежнему неясно где проблема...

Вы задаете вопрос, несколько строчек внизу отвечаете /с ваш ответ я вполне согласен:)/, и после етого опять же задаете тот самый вопрос:)

Если на выходе алгоритма появилось высказывание V то на выходе никогда не появится высказывание не-V. Или то или то.

Полнота теории предполагает что на выходе алгоритма рано или поздно появится либо высказывание V либо его отрицание не-V.

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

Значит в алфавите А существует масса математических высказываний, которые недоказуемы в данной теории. Ни это высказывание ни его отрицание никогда не появится на выходе алгоритма P.

Ну да, так оно и есть.

Но что это за высказывания?

Истинны они НА САМОМ ДЕЛЕ или ложны?

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

Слово "истина" лучше не использовать если мы его не формализовали, ибо тогда неясно что оно означает.

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

Каждая из них будет внутренне непротиворечива но они будут противоречить друг другу. А какая из них истинная? Обе.

Именно так и никак иначе!

Утверждение "множество простых чисел бесконечно" уже экспериментально проверить уже нельзя. Здесь задействована бесконечность.

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

Но мы знаем, что это утверждение рано или поздно будет напечатано на выходе алгоритма Р.

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

Так что надо четко определить что мы понимаем под словесной аббревиатурой "проверимо експериментально".

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

А никак.. Или скорее как мы решим, так и сделаем.

Они либо истины либо ложны? Или оно никакое?

Никакие /т.е. невыводимы ни они, ни их отрицания/, в контексте принятых аксиом и правил вывода.

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

Если мы не исповедуем платонизм, то мы говорим что оно никакое.

Очевидно я не платонист...

Но задав А, R и O мы не можем выдумать его во всех деталях. В некоторых местах там "черные провалы". Он не обладает свойством быть сплошным даже там где нас нет как в нашей реальности. Математика это выдумка (Роджерс Пенроуз будет несоглашасен! :) как мир Гарри Потера. Разница в механизме их порождения. Мир Гарри Потера клеится из возможно противоречивых образов-цепочке и только в нужных местах, а математика строится как мозаика по раз и навсегда заданным правилам аксиоматически. И все. Но и такая мозаика покрывает не всю "плоскость рисунка" как ожидали математики.

Чудесно сказано.

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

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

....

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

Все нормально и логично.

Но давайте попробуем вообразить.

И здесь воображение начинает сдавать.

....

Я говорю о реальности. Как она должна себя вести на бесконечность? Там где нас нет и никогда не будет. Но она там должна быть!

Вот здесь я уже не согласен.

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

Например, что после бесконечного времени 2+2=5. Или что на бесконечности ничего нет. Или что на бесконечности бывает все. И т.д. Воображение разных людей дает разные картины - но ето ведь воображение - как мир Гарри Потера - а не что-то реальное или логически смысленное.

Как реальность поступит с той частью математики где у нас дырки?

Как "ей захочется". Например реальность выбрала чтобы пространство-время было неевклидово... А Евклид ету "дырку" /т.е. дополнительную аксиому о параллельных/ залатал уже "неправильно". Разумеется неправильно относно того что "реальность" думает; в математики "правильно" и "неправильно" бессмысленны - не выводится 5-й постулат Евклида из других - так можно выбрать как 5-ого постулата чтобы расширить теорию, так и его алтернативы...

Еще то представление, что реальность должна быть "сплошная" под большим вопросом...

Даже с учетом КМ ничего не дает оснований утверждать что реальность богаче простой машиной Тьюринга /тезис не-знаю-кого-то/.

Однако мне кажется - здесь вопрос принципиальный... Поскольку научное описание реальности по своей сути обязано быть "исчислимым" /если не привлекать херомантии/, то и модель реальности с которой оперируем тоже всегда будет исчислимой.

А сама реальность - хер ее знает..

Если найдут Теории Всего - так она точно будет вычислима.
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 31 августа 2004 г., 18:29
Завтра я в отпуске. Но на последок.

"Чудесно сказано.

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

Именно так. Так называемая программа Гильберта как раз предполагала найти доказательство непротиворечивости математики средствами самой математики дабы устранить кризис оснований математики вызванный парадоксами теории множеств. Именно в русле этой программы появился многотомник "Принципы математики" Рассела и Уайтхида.

Над этим работал фон-Нейман, когда узнал о теореме Геделя в 31 гду. Против этого была направлена кстати и сама работа Геделя. Цель его работы – доказать невыполнимость программы Гильберта.

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

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

Кстати буквально вчера перечитывал последние главы из книги Роджера Пенроуза "Новый ум короля". Так вот Пенроуз не скрывает своих именно платонистических взглядов! Он не сдается!

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

"Вот здесь я уже не согласен.

Если употребление термина "бесконечность" не четко формализовано, про бесконечности можно утверждать все что захочется. Например, что после бесконечного времени 2+2=5. Или что на бесконечности ничего нет. Или что на бесконечности бывает все. И т.д. Воображение разных людей дает разные картины - но ето ведь воображение - как мир Гарри Потера - а не что-то реальное или логически смысленное."

Ага... Отлично!

Хотя это скользкая идея... но она мне нравится. :)

"Еще то представление, что реальность должна быть "сплошная" под большим вопросом...

Даже с учетом КМ ничего не дает оснований утверждать что реальность богаче простой машиной Тьюринга /тезис не-знаю-кого-то/.

Тезис Черча-Тьюринга.

Эти идеи есть у Дойча. Они восхитительны но... но к сожалению... у меня есть весомы контраргумент. Реальность действительно богаче. Помните что такое невычислимые числа? Это числа, которые не может вычалит никакая машина Тьюринга.

Так я могу "вычислить" такое число. Неалгоритмически.

Я сам себе не верю но это так!

Смотрите.

Запишем все вычислимые числа в канторов стобец в двоичном коде.

010101010101010....

000000000000000...

111111111111111...

101010101000101...

. . . .

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

Но давайте начнем подбрасывать чистую монету некий квантово-механический луидор.

Выпал "орел"? Записываем 0 Выпала решка? Записываем 1

Так мы будем бесконца "вычислять" некоторое совершенно случайное число:

100101000101110101011101010100101 . . . .

Какова вероятность того, что это число находится в вышеприведенной бесконечной таблице?

Возьмем произвольную строку этой таблицы. Вероятность что первые символы обеих строчек совпадают - 1/2. Вероятность что совпадает И вторые символы (1/2)^2= 1/4. Вероятность что совпадет все разряды строк с первого по n-тый (1/2)^n и при n -inf вероятность стремится к 0.

Lim (1/2) ^n = Pr = 0

n-inf

Но в таблице бесконечное число строк!

Давайте рассмотрим событие "квантово-луидорная цепочка не совпадает ни с

одной строчкой-цепочкой"

Это значит что ОДНОВРЕМЕННО НЕ происходит сопадения (1-Pr)...

нИ с цепочкой 1

нИ с цепочкой 2

нИ с цепочкой 3

нИ с...

. . .до бесконечности . То ест вероятность этого события

Lim (1-Pr)^n

n-inf

Но Pr мы уже определили и тогда полная вероятность несовпадения строчек такова:

Lim [1- (1/2)^n]^n

n-inf

Далее мы решаем этот предел учитывая что n стремиться к плюс бесконечности.

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

И так вероятность того что наше число не находится в таблице вычислимых чисел = 1.

То есть мы построили НЕВЫЧИСЛИМОЕ ЧИСЛО.

Невычислимое ни на одной машине Тьюринга.

Используя случайность.

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

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

"Однако мне кажется - здесь вопрос принципиальный... Поскольку научное описание реальности по своей сути обязано быть "исчислимым" /если не привлекать херомантии/, то и модель реальности с которой оперируем тоже всегда будет исчислимой."

Согласен. И тем не мене как вы можете выше видеть в квантовой механике есть невычислимая процедура R которая выходит за рамки вычислимого. Наша реальность несколько мощнее и не поддается моделированию в полном объеме на машине Тьюринга.
Информация о пользователе dzver
dzver
Скрыть | 31 августа 2004 г., 19:20
Alexandr_Semenov

То есть мы построили НЕВЫЧИСЛИМОЕ ЧИСЛО.

Невычислимое ни на одной машине Тьюринга.

Используя случайность.

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

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

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

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

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

Ваше число невычислимо только "на бесконечности".

В реальности, вы ету бесконечность никогда не "потрогаете" и ваше невычислимое число никогда "не увидите".

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

Но таких "построений" нельзя приводить в доказательстве что чего-либо в реальности существует:)

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

Eто бесконечная процедура... Докажите, что в квантовой механики ее есть.

Даже если и используем какую-то хитрую комбинацию КМ и ТО /типа компресирование бесконечного собственного интервала времени в конечного для внешнего наблюдателя/ опять не получается потому что такие вещи "за горизонтом" и недоступны и "ненаблюдаемы" для внешнего наблюдателя. Ето с гравитации.

А если пофантазировать про скорости... можно спросить у фотонов /надеясь что нормальное время вселенной бесконечно - для фотонов оно сжато в мгновение/ - заодно и получим ответ сколько равно 0/0:)

Наша реальность несколько мощнее и не поддается моделированию в полном объеме на машине Тьюринга.

Не согласен... Какова реальность в етом отношении - не известно /может быть и так, и так/.
Информация о пользователе S
S
Скрыть | 31 августа 2004 г., 20:06
===Alexandr_Semenov Участник Клуба

---То есть мы построили НЕВЫЧИСЛИМОЕ ЧИСЛО.

Хочу добавить к предыдущему посту то, что описанный Вами алгоритм имеет ту же проблему остановки. Т.е. никак не обходит ее. Каким образом Вы узнаете что УЖЕ построили невычислимое число? Таблица для проверки ведь бесконечна и узнать, что Вы прошли ее всю Вам тоже не дано.

А практически нулевая вероятность НИКОГДА не доказывала невозможность события. Вот какова вероятность того, что Вас зачали родители (именно эти папа и мама, именно в данное время и именно конкретный сперматозоид добрался до яйцеклетки)? Практически ноль...

А Вы ведь существуете... ;)
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 1 сентября 2004 г., 02:49
Ну вот. Я выдал чуть ли не самый интересный результат в соей жизни, а его не поняли! Похлопали по плечу и сказали: "тебе мерещится" :)(

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

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

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

И так. Что такое вычислимое число?

Нет, начнем еще раньше.

Начнем с несчетных множеств. С Кантора. Святая святых. Диагональная процедура. Как Кантор доказывает что множество действительных чисел действительно несчетно?

Он говорит. Допустим мы упорядочим все действительные числа на интервале

]0, 1[ и выпишем их в столбик в некотором порядке. Допустим так...

0.102933838222333. . .

0.129328233439494. . .

0.348432238229348. . .

0.409538234201234. . .

. . .

Каждая такая БЕСКОНЕЧНАЯ строчка – это дейстительне число.

И таких чисел – бесконечность. То есть таблица вниз тоже бесконечна. В результате мы имеем бесконечную вправо и вниз таблицу ЦИФР.

Нам надо доказать что не все натуральные числа находятся в этой бесконечной таблице. Мы берем диагональ справа вниз и слева направо и выписываем ее цифры. Получаем еще одно диагональное число:

0.1285 . . .91. . .

Тоже бесконечная цепочка цифр. Возможно это число тоже находится где-то "посередине" таблицы. Наверняка там находится! Но теперь мы его "инвертируем" каким-либо образом. Например прибавляем к каждой цифре единицу, а если эта цифра 9 то заменяем ее на 0.

Получаем другое число

0.2396. . .02 . . .

Это число отличается от любого числа в бесконечном списке хотя бы на одну цифру. От первого в первой цифре. От второго во второй. От третьего в третей.

То есть это число выпадает из списка. А значит, как бы этот список не был упорядочен он не содержит всех действительных чисел из интервала ]0, 1[

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

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

Как он так лихо берет и упорядочивает бесконечные цепочки? Как это он строит бесконечную диагональ? И как это он так легко выводит, актуализирует свойства некоторого бесконечного объекта?

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

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

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

Я вспоминаю это, потому что меня обвинили в том же. Что я перескакиваю через бесконечность. Это смешно. Потому что между мной и Кантором стоит еще одно имя. Тьюринг. Он тоже "скачет". И его тоже внесли в учебники за это. :)

Что мы имеем перед Тьюрингом? Перед его работой о невычислимых числах 1936года? Мы имеем числовую ось состоящую из множества действительных чисел. Их не то что много их ОЧЕНЬ много. Их несчетное количество. Множество натуральных чисел 1, 2, 3 . . . . есть подмножество этого множества.

Поэтому их можно было бы выписать в стандартном виде как мы выписываем действительные числа в виде бесконечных цепочке.

1.00000000 . . . .

2.00000000 . . . .

3.00000000 . . . .

. . .

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

Кроме того есть множество рациональных числе. Это числа заданные дробью вида a/b, где a и b – натуральные числа (здесь следовало бы упомянуть отрицательные числа, целые, но это - детали). При кажущемся бОльшем множестве действительных числе их тоже счетное число. Столько, сколько натуральных. Их тоже можно расположить в бесконечный столбик ни потеряв ни одного. Легко понять что, с одной стороны, они подмножество множества действительных чисел (они расположены где-то на числовой оси), но с другой стороны натуральные числа – их под множество.

Сморите:

1/1, 2/1, 3/1, . . . и т.д.

Это дроби, но то же и наши натуральные числа!
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 1 сентября 2004 г., 02:50
Желательно все это рисовать в виде кружочков друг в друге. Мы уже получили некую матрешку множеств. И будем ее достраивать дальше и дальше.

Следующий шаг.

Вы знаете что число корень из 2 не принадлежит множеству рациональных чисел. Но оно тоже расположено где-то на числовой оси. Это горе Пифагора. Крах его системы. Тайна пифогарийев, предательски открытая миру. . . Корень из два не рациональное число его называют алгебраическим числом.

Всякое число которое можно записать как некоте алгебраическое высказывание с использованием операций и знаков радикала называется алгебраическим например: [2+sqrt(5)- sqrt(3)]^3 / sqrt(7).

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

1/1, 2/1, 3/1, . . . и т.д.

Счетное ли множество алгебраических чисел? Ведь таких чисел еще больше чем дести тельных чисел! Но подумайте, любая такая формула – это конечная цепочка символов. А множество таких конечных цепочек счетное. То есть это еще одна матрешка. Еще большая. Но она все рано внутри суперматрешки несчетного множества дейстительных чисел. То есть на числовой прямой все равно остаются числа, для вычисления которых не хватает всех алгебраических выражений!

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

Очевидно трансцендентные числа тоже являются некой матрешкой и наверное не последний. Далее можно выделить множество определимых числе. Чисел свойство которых описывается конечной цепочкой слов. Например нет ни конечной не бесконечной алгебраической формулы для вычисления простых чисел. Но мы можем сказать "первое простое число", "второе простое число", "третье простое число" или "первое член в 1234333 простой паре близнецов". Можно так определять число? Можно. И наверное множество всех ранее нами определенных числе являются всего лишь подмножеством этого множества. Но и это множество счетное. Ведь любое описание – конечная цепочка символов. Со всеми вытекающими отсюда последствиями –счетностью множесва. Поэтому на числовой оси все равно остается бездна каких-то темных числе, которыми почти полностью заполнена числовая ось, а все эти наши множества фактически ничего там не весят!

Как долго мы будем продолжать эту игру с матрешкам?

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

Вычислимые числа это числа, которые вычисляются на его машине. Машине Тьюринга. Сейчас мы легко можем сказать, что вычислимые числа это те числа, для вычисления которых найдется некоторая компьютерная программа печатающая их ПРАЗРЯДНО на своем выходе.

(я думаю все понимают что абстрактная программа не ограничена как реальные программы верхним пределом значений того или иного типа данных? У машины Тюбинга один тип данных infininteger :)

Например, программа, печатающая как-нибудь натуральное число очевидна. Например печатающая число 3.

. . .

begin

Write("3");

end.

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

А как с действительными числами? Вычислимо ли 1/3?

Ну почему бы и нет? Вот фактически универсальный алгоритм приспособленный для вычисления 1/3:

. . .

begin

a:=1; b:= 3;

While l0 do begin

If ab then begin

c:=a mod b;

Write(c);

l:=a div b end

else begin

a:=a*10;

Write("0");

end;

end.

Правда здесь не печатается десятичная запятая, но это для нас не существенно.

Важно, что этот алгоритм будет печатать:

033333333333333333....

Стоп. Но он никогда же не остановится!

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

Хорошо, а программа вычисляющая любое алгебраическое число возможна?

Конечно возможна (детали могут озадачить, но это вопрос для школьников физ.мат.школ. перепрыгнем его). А для трансцендентного числа?

Например, числа "пи" или "е"? Есть программа? Есть! И не одна!

А для определимых чисел? Скажем программа, которая бы печатала тот самый первый член 1234333 простой паре близнецов? Есть и такая программа!

Конечно не для всех определимых, но есть и для них.

В общем множество вычислимых чисел это наиболее общее множество чисел включающее почти все ранее определенные нами подмножества. Это все числа которые можно как то ВЫЧИСЛЯТЬ. И не важно остановится процесс их вычисления или нет. Остановится – ну и ладно. Нет – тоже нормально.

Можно даже сделать так. Пускай все программы зациклятся. Если программа вычисляет натуральное число 3 то пускай она напечатав цифру 3 напечатает десятичную точку и дальше без конца печатает нули:

3. 0 0 0 0 0. . . .
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 1 сентября 2004 г., 02:51
Дурное дело не хитрое. Зациклим все программы для армейского единообразия!

Ибо скоро нам их придется выстраивать их в шеренгу Кантора.

И так. Уловили смысл ВЫЧИСЛИМОГО ЧИСЛА?

Является множество вычислимых чисел счетным? Конечно. Ведь всякая программа есть всего лишь конечная цепочка символов. Поэтому даже множество вычислимых чисел на числовой оси не покрывает всех чисел. А значит существуют НЕВЫЧИСЛИМЫЕ ЧИСЛА. Не вычислимые ни на какой машине Тьюринга!

Уловили и это?

Тьюринг задался такой проблемой. А нельзя ли воспользоваться диагональной процедурой Кантора как ВЫЧИСЛИТЕЛЬНЙ ПРОЦЕДУРОЙ и сделать невозможное: вычислить какое-нибудь невычислимое число?!

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

Смотрите. Программа работает циклически.

Первая итерация

Программа печатает первый разряд первого вычислимого числа.

Вторая итерация.

Программа печатает второй разряд первого числа

Программа печатает первый разряд второго числа.

Третья итерация.

Программа печатает третий разряд первого числа

Программа печатает второй разряд второго числа.

Программа печатает первый разряд третьего числа.

. . .

N-тая итерация.

Программа печатает N-тый разряд первого числа

Программа печатает N-1 разряд второго числа.

Программа печатает N-2 разряд третьего числа.

. . .

Программа печатает первый разряд N-того числа.

. . .

Идея ясна? Очень необычная но богатая идея.

И так подобная суперпрограмма возможна. Она как Змейка Кантора будет непрерывно обползать и выпечатывать верхний правый фрагмент таблицы всех вычислимых чисел. Все что нам осталось – брать диагональ и инвертируя в ней цифры печатать рядом НЕВЫЧИСЛИМОЕ число. Число, которого наверняка нет в бесконечной таблице вычислимых чисел.

Но разве это невычислимое число?

Как такое может быть?

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

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

Это оригинальная идея доказательств Тьюринга Проблемы Остановки в его работе о невычислимых числах. Что бы выгородить все это он фактически изобрел УНИВЕРСАЛЬНЫЙ КОМПЬЮТЕР. Странно, не правда ли?

Ради такой абстрактной глупости создать такую ВЕЩЬ!

Мы тоже здесь ищем ответы на "дурацкие" вопросы.

Каким боком может это выйти?

Конечно может ничего не выйти. Мало ли дураков мучают себя глупыми вопросами. Не всем быть Тьюрингами!

:))(

Я знаю еще два доказательства Проблемы Остановки. Самое простои и изящное не столь громоздко.

Допустим существует разрешающая процедура T(p, x) такая что выдает "1" если программа Р(x) c геделевым номером p останавливается, если ей на вход подается число x. Если же Р(x) не останавливается, значит программа T(p, x) печатает "0". Это записывается так:

..................1, если Р(x) останавливается

T(p,x) ={

..................0, если Р(x) НЕ останавливается

Тогда напишем следующую программу B ("брадобрей")

. . .

begin

Read(x)

While T(x,x)=1 do

begin end;

end.

И скормим на вход программе B ее геделев номер. Что получаем? Если процедура T приходит к выводу что программа В получив на вход свой геделев номер не зациклится, то она, выдаст 1 и . . . программа В ЗАЦИКЛИТСЯ. Если же программа T выдаст 0 – зациклится, программа В благополучно остановится.

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

Теорема Тьюринга об Остановке доказана.

Зачем я все это здесь так долго рассказываю? Я хотел показать что я стою на плечах гигантов. И напомнит как все там красиво взаимосвязано и надезно закрыто и как квантово-механический НЕВЫЧИЛСИМЫЙ луидор во все это вписывается.
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 1 сентября 2004 г., 02:52
Можно уверено гнать отсебятину пологая что ты один видишь нечто великое а все вокруг - дураки. Особенно это хорошо делать на "философии". И там я тоже могу смеяться, ругаться злиться что меня не понимают. Но здесь у меня в руках оказался неразменный пятак! Я его сдаю, а он возвращается! И так и сяк. Но чудо на лицо! Как не крути! :)(

Вот стоит бесконечный ряд абстрактных машин Тьюринга которые деловито печатают и печатаю разряд за разрядом ВЫЧИСЛИМЫЕ числа. Секунда разряд, вторая –еще разряд. Третья – еще разряд. Бесконечный ряд бесконечных лент. Я становлюсь рядом и в такт и работе начинаю подсасывать свой пятак.

Орел

1

Решка

10

Решка

100

Орел

1001

. . .

Чем мой процесс отличается от того что происходит внутри БЕСКОНЕЧНОГО ряда машин? Внешне - ничем. Это еще один черный ящик который без остановки печатает разряды некоторого числа. И у них и у меня процесс никогда не остановится. некоторые из тех машин зацикливаются. Ну и бог с ними. Но моя гарантированно не зациклится. Гипотетическая диагональная машина Кантроа должна была так же печатать невычислимое число бесконца. Но Тьюринг показал что она обязательно где-то "повиснет" как толко повиснет одна из тех в бесконечном ряду. А мой пятак не зависает. Он вообще ни от чего не зависит. Дзинь, и происходит редукция волновой функци. Дынь! Еще раз. Всякий раз происходит не вычислительная не редуцируемая ни к каким вычислениям процедура. Процедура математически чисто случайный выбор.

Решка

10011

Решка

100111

Орел

1001110

. . .

Никаких проблем остановки!!!!

Так все-таки что у меня в руках?

:)))

ЗЫ:

Цитата:

*************

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

Вероятность достоверного события равна 1

. . .

Событие V называется невозможным в данном эксперементе, если оно не может произойти в нем никогда. . . Вероятность невозможного события равна 0

***********

"Вероятность вокруг нас". А.В. Скороходов.

О бросании точки на плоскость и вероятности попасть точкой в заданную точку равное 0. Здесь нет противоречия. Фактически описанная процедура с луидором и есть вариант такого бросания. Мощность невычислимых на плоскости точек – континуум, а точек, которые мы можем назначить вычислением к попаданию – счетное множество. Это значит что какую бы точку мы не назначили, случайно бросив на плоскость пробную точку мы достоверно в нее не попадем в силу бесконечной малости площади вычислимых точек по отношению к невычислимым. Но о чем это говорит? Это говорит, что с помощи процедуры случайного бросания мы "вычисляем" ЛЮБОЕ действительное число. Но вероятность попасть на такое действительное число, чтобы оно еще было и вычислимым равна нулю. Этого никогда не происходит. Поэтому все получаемые так числа - невычислимые. Гарантированно невычислимые.

Как не крути, но мы все же превзошли машину Тьюринга в решении задачи о невычислимых числах!
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 1 сентября 2004 г., 03:18
Перечитал отправленный текст и ужаснулся. Я очен часто путаю название рациональных чисел с дейтвительными и даже натуральными. Это очень плохо! Людям непосвященным все запутает. :(((

Корректируйте меня пожалуйста по контексту.
Информация о пользователе dzver
dzver
Скрыть | 1 сентября 2004 г., 06:04
Alexandr_Semenov

Вы очень интересно пишете. Вам бы преподом быть.

Как обычно, я с почти всем согласен.

Однако, поясните пожалуйста, следние моменты.

1.

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

Да, но..

Это говорит, что с помощи процедуры случайного бросания мы "вычисляем" ЛЮБОЕ действительное число.

А вот с етим не совсем согласен. Мы ничего не вычислили, потому что никакое число не назначили предварительно. И именно поетому как вероятность, так и "вычисление" здесь несколько непричем.

Ваш метод "вычисления вычислимых чисел" - вычисли то - не знаю что.

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

2. С другой стороны, все надо рассматривать в контексте принятых аксиом и правил вывода. Дополним базисных функций /правил вывода/ с еще одну безаргументную: "Rand()". Она выдает 0 или 1 в 50% случаев АБСОЛЮТНО СЛУЧАЙНО. /Несложно физически построить ее и дооборудовать обычную машину Тьюринга с ней/.

Тогда программа печатающая невычислимые числа записывается конечно и просто:

begin

While True do

Print Rand();

end.

Но подумайте, любая такая формула – это конечная цепочка символов. А множество таких конечных цепочек счетное.

Программа выше - тоже конечная цепочка символов, как и наша 4-символьная функция "Rand()".

3. Мое третье возражение дублирует 2 но ето скорее вопрос.

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

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

Про бесконечности и зацикленные машины Тьюринга, вычисляющие бесконечные вычислимые числа.

Все, что я хотел сказать, что выражение:

"данная конечная машина Тьюринга No.3293293 вычисляет число pi",

в физической реальности надо понимать как:

"МТ No.3293293 вычисляет число pi с любой ЗАПЕРЕД заданной точности"

а НЕ как

"МТ No.3293293 на самом деле вычисляет число pi".

Потому что МТ No.3293293 число pi никогда не вычислИТ.

(если хотите можете сказать что она исчислит pi на бесконечности но ето то же самое что и никогда).

Определение выше /"МТ No.3293293 вычисляет число pi с любой ЗАПЕРЕД заданной точности"/ вполне в согласии с обычной дефиниции вычислимых чисел, но его ясно как понимать в реальности и мозги не пудрит.

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

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

Т.е вот такой сценарий.

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

Вы утверждаете что нет.

Что наблюдается?

Вы бросили 101.

Ждем известное время и моя МТ выдает где-то 101.

Вы бросаете ноль, сейчас ваше число получается итого 1010.

Мы опять ждем и после некоторого большего времени моя МТ выдает и 1010.

И так на каждом етапе /моя машинка МТ будет медлит конечно, експоненциально, но все-равно "догонит" каждую вашу конечную последовательность/.

А ето все, что важно по отношении к реальности.

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

Кстати "любая заданая точность" - ето тот же самый прием с который по-моему Коши определил коректно /и физически смысленно!/ бесконечно-малые в дифф. счисления.

И наконец, про Реальности /откуда все и началось/.

Я согласен, что реальность похоже НЕ является полностью детерминирована - как "механические часы" /в смысле Лапласа/.

Но, она спокойно может быть "Rand-вычислимой" - т.и. вычислимой машиной Тьюринга с присобаченной функции Rand().

И, я думаю что именно ето имел ввиду Дойч /а не механическая вычислимость типа Лапласа - т.е. обычной машине Тьюринга/.
Информация о пользователе dzver
dzver
Скрыть | 1 сентября 2004 г., 06:57
тьфу, ЗАПЕРЕД=НАПЕРЕД
Информация о пользователе dzver
dzver
Скрыть | 1 сентября 2004 г., 10:15
Да, может быть и про етого надо сказать.

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

Как он так лихо берет и упорядочивает бесконечные цепочки? Как это он строит бесконечную диагональ? И как это он так легко выводит, актуализирует свойства некоторого бесконечного объекта?

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

И почему вы назвали их "актуальными бесконечностями"?

Таким же образом - доказательство что множество натуральных чисел равномощно множеству четных чисел (своего собственного подмножества)- сводится до соответствием x=2*y - и "актуальная бесконечность числового ряда целиком" на самом деле нигде не изпользуется.

Хотя мы можем написать их для иллюстрации:

y: 1, 2, 3, 4, 5, 6, 7, 8 ......

x: 2, 4, 6, 8 .......

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

Етот рисунок - просто же иллюстрация к доказательству.

Тем же образом, Канторова матрица - тоже иллюстрация - а не "построение актуальных бесконечных множеств".

Другими словами, метод Кантора вполне формулируется старым добрым "допустим что... тогда для каждого конкретного... найдется... такое что...противоречие с допущением" - т.е. бесконечности не должны быть "актуальными".

С другой стороны, математические бесконечности нельзя автоматически перебрасывать на Реальность - поскольку реальность всегда "актуальна".

Математический натуральный ряд бесконечен -но у вас есть весомые аргументы что произвольно большие числа могут быть физически осмысленны /типа брой нуклонов во вселенной более чем любого наперед заданного числа... общая енергия вселенной больше чем любого наперед заданного числа...и т.д/?

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

Я вспоминаю это, потому что меня обвинили в том же. Что я перескакиваю через бесконечность. Это смешно.

Нет.. Вас никто не обвинил что перескакиваете через бесконечность.

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

Ну скажите ради бога откуда вы знаете что в реальности невычислимые числа существуют?

Чтобы утверждать етого, мне кажется необходимо привести примера - типа доказать что физически осмысленное отношение не зависящее от с-ме измерение единиц /напр. отношение массы покоя електрона к массы покоя протона/ - суть величина невычислимая. Или что-то вроде. Такое доказательство ясно, нельзя привести пока физика не полностью аксиоматизирована:) А если она и никогда не будет полностью аксиоматизирована /Теория Всего/ то и никогда не станет ясно как вещи обстоят на самом деле..
Информация о пользователе dzver
dzver
Скрыть | 1 сентября 2004 г., 10:34
Чем мой процесс отличается от того что происходит внутри БЕСКОНЕЧНОГО ряда машин? Внешне - ничем. Это еще один черный ящик который без остановки печатает разряды некоторого числа.

Верно..

И у них и у меня процесс никогда не остановится. некоторые из тех машин зацикливаются. Ну и бог с ними. Но моя гарантированно не зациклится.

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

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

1 шаг: 0,1

2 шаг: 00,01,11,10

3 шаг: 000,001,010,011,110,111,100,101

.........

Назовем ее МТ01.

Гипотетическая диагональная машина Кантроа должна была так же печатать невычислимое число бесконца. Но Тьюринг показал что она обязательно где-то "повиснет" как толко повиснет одна из тех в бесконечном ряду. А мой пятак не зависает.

МТ01 тоже не повиснет.

Он вообще ни от чего не зависит.

МТ01 зависит от своего алгоритма - но зато какой он мощный:)

Дзинь, и происходит редукция волновой функци.

Дзинь, и МТ01 выплюнула 2^n чисел - ваша текущая последовательность среди них.

Дынь! Еще раз.

Дзинь, и МТ01 выплюнула уже 2^(n+1) чисел -ваша текущая последовательность опять среди них.

Всякий раз происходит не вычислительная не редуцируемая ни к каким вычислениям процедура. Процедура математически чисто случайный выбор.

Зато каждый раз МТ01 догоняет, "охватывая" ваше текущее число...

Хотя и процедура МТ01 вполне вычислительная /и, надо признать, более трудоемка чем ваша/...

Никаких проблем остановки!!!!

МТ01 тоже никогда не остановится, гарантировано:)

Так все-таки что у меня в руках?

:)))

В етом и вопрос? Что-же так необычного здесь...?
Информация о пользователе Pier_V_Tin
Pier_V_Tin
PROFESSION DE FOI
E-mail: pier_v_tin@front.ru
Скрыть | 2 сентября 2004 г., 03:52
Alexandr_Semenov:

Как может существовать бесконечное число Z-машин Тьюринга, которые одновременно могут, и остановиться, и не остановиться?![имеется ввиду что существует неперечислимое множество предложений в языке Арифметики таких что присоединение их или их отрицаний к аксиоматической Арифматике Пеано (в дальнейшем PA) не ведет к противоречию]

___________________

Alexandr_Semenov предложил кодировать _каким-либо образом найденные_ недоказуемые в PA утверждения "Ф" в форме

1)(Ex)(Ez)Т(x,y,z) и

2)(Ex)(Az)~T(x,y,z)

где x - номер машины Тьюринга, y - номер утверждения "Ф", z=(t,u) - номер пары, где t - число шагов вычислений, u - принадлежит множеству {True,False}, (E) - существует, (A) - для любого.

В случае (1), в общем, из u=True не следует что (Ex)(Et) Т(x,"~Ф",(t,False)),так что такое присоединение утверждений вида (1) или (2) ни к чему не обязывает кроме следствий непротиворечивости. Возмем "0=0", доказуемое в PA. Но (Ex)(Et)Т(x,"~0=0",(t,False)) ложно так как мы исходим из того что PA непротиворечива (и неполна). Следовательно (Ax)(At)~Т(x,"~0=0",(t,False))(утверждение о недоказуемости непротиворечивости PA). Но возможно ли что для всякого утверждения "Ф" истинно (Ex)(Et)T(x,"Ф",(t,True)) & (Ex)(Et)Т(x,"~Ф",(t,False))? Если же "Ф" полуразрешимо то у нас не найдется номера машины для одной из формул. Такие новые номера соответствуют именам машин Ораклов отвечающих на определенные трудные вопросы. Все разрешимые задачи решаются в PA, так что мы имеем здесь вложение в аппарат доказательств PA разрешающее применимость закона исключенного третьего к рекурсивно перечислимым множествам.

В случае (2) мы присоединяем отрицание предложения с номером y - "~Ф" так что будем считать что (Ex)(Et)T(x,"~Ф",(t,True)) для некоторой машины с Ораклом.

Теперь заметим что любому номеру x машины Тьюринга соответствует р.п. множество X на котором она выдает значение True за конечное число шагов, но y у нас из дополнения к р.п. множеству - Y (множеству недоказуемых в PA предложений). Объединение всех таких пересечений множеств X с Y есть р. п. множество, так что как бы мы ни кодировали нерешаемые задачи машинами Тьюринга мы несможем закодировать их всех(для этого придется использовать тренсфинитную рекурсию).

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

Гедель установил что для всякого рекурсивно перечислимого отношения R(x) существует полиномиальное отношение (Ey)(P(x,y)=0) с некоторым кванторным префиксом (Ю.В.Мятисевич доказал достаточно кванторов существования) истинное тогда и только тогда когда истинно R(x) (у нас (Ex)(Ez)Т(x,y,z) = (Ew)(P(w,y)=0), (Ex)(Az)~T(x,y,z) = (Ew)(P(w,y)=0)). Как только мы нашли машину Тьюринга удоволетворяющую (1) или (2) и некоторое недоказуемое в PA утверждение "Ф", этой находке будет соответствовать полуразрешимое утверждение (Ew)(P(w,"Ф")=0). Таким образом каждое недоказуемое в PA утверждение соответствует утверждению о существовании корня w (неразрешимого в PA) уравнения P(w,"Ф")=0.

Теперь мне хочется проделать следующее:

Пусть доказуемо, или же принято на веру утверждение что для некоторого "Ф" (Aw)~(P(w,"Ф")=0). Т.е. "Ф" неприсоединимо. Мы расширяем область определения теории такими w что P(w,"Ф")=0 выходя за пределы натуральных чисел, как это делалось ноднократно с вещественными числами и с мнимой единицей. Таким образом предложение ложное в PA, оказывается истинным в новой теории. Конечно такое расширение затрагивает все прежние предложения содержащие квантор всеобщности. Может оказатся что (Ex)x=x+1 например или можно получить кольцо целых чисел исходя из того что (Ex)x+1=0,... Здесь вопрос смещается со свойств множеств которые определяются этими формулами на свойства формул _истинных_ при некоторой интерпретации, которые могут сильно отличатся.

Alexandr_Semenov:

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

_________________

Есть такие объекты обладающие этим свойством, очень простые, это лямбда-термы. См.:

http://www.andrew.cmu.edu/user/cebrown/notes/baren dregt.html

Там важно лишь что если останавливаются то с одинаковым выходом.
Информация о пользователе NO
NO Участник Клуба
WWW: 4spam2no@mail.ru
Скрыть | 2 сентября 2004 г., 22:20
Alexandr_Semenov

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

Слово "аксиома" как раз и происходит от слова "ценность" :)

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

Мойте руки после программирования, вот и вся метаматематика.
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:46
"Хотя этот топик и умер, зато он наиболее интересный из всего что здесь обсуждают..."

давно я тут не был и тоже думал, что топик умер. а он, оказывается, цветет и пахнет ;)

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

я думаю, что лет через 100-200 ответы на вопросы из этого форума будут изучать в школе в базовом курсе математики ;)
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:47
Александр Семенов:

30 августа, 17:12 Вы пишете: "Я не уверен. Это очень смутная догадка ни к чему не обязывающая"

ничего не понял. какая догадка? та, что МТ состоит из твердых детерминированных частиц? или что МТ может дать сбой? так это неверно по определению МТ. или то, что МТ в тезисе Тьюринга - не та, которая им же формально описана, а имеющая какое-то физическое воплощение? или что-то другое? говорите яснее.
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:48
"Мы должны построить формальную теорию матемаики. {A, R, O}"

вот они, скользкие моменты! давайте строить по аналогии с исчислением предикатов. "A - набор символов теории" - для формальной теории на этом месте стоит не алфавит, в котором записываются высказывания теории (алфавит - это забота исчисления), а множество констант предметной области. если мы хотим, чтобы построенная математика могла работать дальше с целыми и действительными числами, то мы должны включить во множество A множества R и Z. то есть, чтобы я мог написать (Ex)x=\pi (здесь под \pi я буду подразумевать одну греческую букву, а не три знака), то множество всех предложений теории уже не будет счетным (т.к. A - континуум). если все-таки мы захотим сделать A конечным/счетным и принудительно добавим \pi к выбранному алфавиту, то как быть с целым континуумом других констант? если A - не континуум, то некоторые предложения (в частности, с использованием констант) не могут быть записаны в нашей новой математике. а если континуум – то рассуждения насчет счетности всех предложений теории рассыпаются. R - набор манипуляций. тут все понятно, можно взять правила вывода из какой-то логики. O – аксиомы. как заранее так определить набор аксиом, чтобы он подошел и для теории чисел, и для анализа, и для всех остальных приложений. в каждой теории по отдельности набор аксиом более-менее устоялся, а для математики вообще все аксиомы свалить в кучу нельзя – кто будет доказывать непротиворечивость такой системы? теперь подходим к центру проблемы.
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:49
как узнать, невыводимые высказывания истинны или ложны? прежде чем браться за такую задачу, определим истинность высказывания P(t1) для константы t1. в формальной теории, построенной на базе исчисления предикатов, так: значения термов на константах тоже заданы (входят в конструкцию теории) то есть если s – функциональный символ, s(x,y,z) – функция, s(a,b,c) – терм, a,b,c – из множества A, тогда мы всегда знаем, что s(a,b,c)=d, d – тоже из A. значения предикатов на константах (значит, и на всех термах) задаются интерпретациями (то есть в конструкцию теории нужно внести еще одно множество). то есть истинность конкретного предложения зависит от интерпретации. предложения с кванторами проверяются с привлечением множества констант A, с которым мы пока не определились. краткое резюме сказанному: выводимость (в формальной теории) никак не связана с истинностью. если мы вывели (Ax)P(x), то истинность определяется интерпретацией P, и конечно, множеством констант, которые будет пробегать квантор.
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:52
по поводу 31 августа, 18:29.

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

ещё одна мысль на тему – если Вы проводить опыт с бросанием монетки (предположим даже, если на бесконечности вы его закончите), у Вас всего будет всего одно невычислимое число, но таких чисел намного больше, как получить другие? континуум Александров Семеновых, бесконечное число раз бросающих монетку, поражает больше, чем не останавливающаяся и останавливающаяся одновременно машина Тьюринга ;)
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:52
уважаемый участник клуба, призываю к математической строгости!

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

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

3. как Вы можете говорить о результате вычисления МТ, которая никогда не остановится. где гарантия, что машина, предположительно печатающая 1/3, после 3000 шагов (или 8000, кто знает…) не вернется назад и не сотрет напечатанные тройки, напечатав вместо них пятерки. в этом смысле она никак не может быть эквивалентна программе, которая печатает тройки и для которой точно известно, что от напечатанных троек она уже не откажется. таким образом, говорить об эквивалентности программы и МТ можно лишь в случае, когда МТ останавливается и с оговоркой, что в определенном месте ленты мы обнаруживаем тот же результат, что и вывод программы. в этом смысле все не останавливающиеся машины эквивалентны, и мы не можем различить машину, печатающую невычислимое число от другой такой же зациклившейся.

4. «Вероятность достоверного события равна 1. Вероятность невозможного события равна 0». по определению, да. но из этого не становится верным обратное утверждение, на которое Вы ссылаетесь: «вероятность попасть на такое число […] равна нулю. Этого никогда не происходит. Поэтому все получаемые так числа - невычислимые»

p.s. не сочтите за наезд, но на этом форуме строгость не повредит.
Информация о пользователе SMT
SMT
Скрыть | 3 сентября 2004 г., 17:54
Pier_V_Tin:

простите, но у меня небольшой пробел в терминологии: что такое неперечислимое множество: бесконечное, счетное, мощнее, чем счетное, или какое-то другое?

ещё вопрос: есть ли смысл вводить в T(x,y,z) переменную x? как я понял, T – отношение, связывает множество машин с номерами x, которые, получив на вход y, выдают z=(t,u). У Александра машина уже задана x=m (и точно известно, что её можно построить, т.е. что константа m есть в предметной области), почему бы для удобства не переобозначить T(x,y,z)=T(m,y,z)=T1(y,z). для краткости, T(y,z). или принципиально важно, что рассматриваются все МТ, даже те, которые не предназначены для проверки утверждений?
Информация о пользователе Alexandr_Semenov
Alexandr_Semenov Участник Клуба
Александр Семенов
E-mail: sem123@list.ru
Скрыть | 3 сентября 2004 г., 19:09
Я в отпуске. Дома подключиться к сети пока не могу раньше чем завтра. Сейчас оказался на работе. Заглянул сюда. Да, тема жива! :))) Попробую ответить за выходные. Замечание о строгости принимаю. Посыпаю голову пеплом. :)(
Информация о пользователе Pier_V_Tin
Pier_V_Tin
PROFESSION DE FOI
E-mail: pier_v_tin@front.ru
Скрыть | 3 сентября 2004 г., 22:22
I.Множество рекурсивно перечислимо (полуразрешимо) если оно есть либо область определения либо область значений какой либо частично-рекурсивной функции (машины Тьюринга).

II. Множество рекурсивно (разрешимо) если и оно и его дополнение рекурсивно перечислимо.

Для р.п. множеств функция-индикатор выдает предположим 1 на его элементах и все остальное включая случай неопределенности на прочих элементах. Для рекурсивного множества функцию-индикатор можно задать всюду определенной чтобы она выдавала 1 на элементах множества и 0 (или любое число кроме 1) на его дополнении.

Все конечные множества рекурсивны.

T(x,y,(t,z)) - "Машина с номером x получив на входе y через t шагов заканчивает работу и выдает z" - предикат Клини.
Информация о пользователе dzver
dzver
Скрыть | 3 сентября 2004 г., 22:31
SMT

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

квантовая механика, вроде, дает гарантию; его монетка не классическая а квантовомеханическая
Информация о пользователе 7-40
7-40 Участник Клуба Золотое перо
WWW: Tuline eesti poiss - Горячий эстонский парень
Скрыть | 4 сентября 2004 г., 00:09
222AVIA:

С: Так что думаю, что думающий чел (типа

С: аналитик) всегда может найти ошибки,

С: даже не обладая всеохватывающими

С: знаниями.

Сергей, вспоминаю несколько диалогов с Вами. Вы (если не ошибаюсь) называли себя аналитиком и уже не раз приписывали себе способность "найти ошибки, даже не обладая всеохватывающими знаниями". Простите, если обижу Вас напоминаниями - но как раз в тех самых случаях Вы как раз и ДОПУСКАЛИ ОШИБКИ, причём элементарные. Т. е. речь об обнаружении не шла вообще - дай бог самому не ошибаться.

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

По поводу цитаты из Ландау: он имел в виду, очевидно, не знание устройства автомобиля, а именно умение управлять им. Если человек не умеет управлять автомобилем - попытки сесть за руль чреваты. Если человек не разбирается в предмете - попытки выносить суждения по нему тоже чреваты. Даже если этот человек называет себя аналитиком.

С искренним уважением к Вам... ;-)
Информация о пользователе 7-40
7-40 Участник Клуба Золотое перо
WWW: Tuline eesti poiss - Горячий эстонский парень
Скрыть | 4 сентября 2004 г., 00:10
Ой! Не туда полетело! Сорри!
Информация о пользователе SMT
SMT
Скрыть | 4 сентября 2004 г., 02:41
Александр Семенов

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

Pier_V_Tin

конечно, если обозначение T(x,y,z) общепринято, давайте пользоваться им

dzver

я еще не дошел до функции R в теории квантовых вычислений. но у меня уже сомнения - почему именно случайность, а не очень большой количество невидимых внутренних состояний (или случайность в КМ - по определению?)
Информация о пользователе SMT
SMT
Скрыть | 4 сентября 2004 г., 02:44
вот что мне не нравится в диагональной процедуре: требуется, чтобы каждое число однозначно кодировалось последовательностью цифр. с учетом того, что 0.49999999…=0.5000000… специально оговаривается, что 0.499999… - это не число. то есть кодировка уже не взаимно-однозначная. при построении диагонального числа Кантора нужно убедится, что получается число (то есть нет девяток в периоде). для десятичного представления проблем нет, договариваемся никогда не выбирать девятку, а для двоичных последовательностей, которые использовались в примерах выше, все сложнее.

дальше пойдет ненаучная фантастика, просьба не комментировать:

непонятно, является ли числом последовательность

0.4 (999 бесконечно много девяток 9999) 0 (000 бесконечно много нулей 000)

если это число, рациональное оно или нет?

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

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

сопоставив ящики (программы конечной длины внутри них) с последовательностями, думаю, нужно рассмотреть более компактную запись бесконечной последовательности, а именно, как функцию f: N-{0,1}

потом нужно определить операции над такими функциями (в общем-то, операции над программами не новость) и построить пространство функций. если оно конечномерно (что вряд ли по аналогии с анализом, где даже непрерывные функции уже образуют бесконечномерное пространство, а может и конечномерно для программ некоторой длины, не превышающую наперед заданную), то раскладывая по базису, получим интересный способ анализа и синтеза алгоритмов. бред, короче.
Информация о пользователе dzver
dzver
Скрыть | 4 сентября 2004 г., 08:44
SMT

dzver

я еще не дошел до функции R в теории квантовых вычислений. но у меня уже сомнения - почему именно случайность, а не очень большой количество невидимых внутренних состояний (или случайность в КМ - по определению?)

Да, eто постулат /принцип/.

На тот принцип однако есть [физически веские] основания.

Почему не очень большое количество внутренних состояний:

- скрытые параметры /какие бы то они не были/ дают для запутанных пар предсказания отличающиеся от предсказаний КМ /нер. Белла/. Ето експериментально проверено в лоб и результаты однозначно потверждают предсказаний КМ и не стыкуются со скрытыми параметрами /не конкретные скрытые параметры, а вообще с возможностью скрытых параметров независимо от их сорта и как они именно влияют/.

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

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

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

Например, нельзя доказать что кв.мех случайность не является результатом мгновенного нелокального "взаимодействия" всех объектов вселенной с измеряемой частицы /слово "взаимодействие" в кавычках потому что оно не передает информацию, а только налаживает нелокальную корреляцию - иначе СТО летит на хер а она хорошо потверждена/.

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

И здесь слово "постулат" скорее надо интерпретировать в смысле что ето а) в корне расходится с настоящих теорий которые отлично потверждены б) експериментальная проверка в лоб дала результаты которые несовместимы /никак не могут быть объяснены - ето доказывается математически/ с помощью локальных скрытых параметров.

Итого - скрытые параметры - возможны, но они должны быть раз нелокальные, два не переносить информации а только налаживать корреляции - что само по себе уже вроде делает их неиспользоваемыми для физике.
Информация о пользователе SMT
SMT
Скрыть | 4 сентября 2004 г., 14:28
dzver:

ну что-ж, буду читать Фейнмана...

значит, если с помощью КМ можно получить настоящее случайное число (экспериментально), то тезис Тьюринга под сомнением (как же так, какой-то физик может вычислить СЧ, а машина Тьюринга - не может)

Александр Семенов:

мое сообщение от 3 сентября, 17:48

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

вместо

(Ex)x=\pi

пишем

(Ex)(Ez) x=z & P(z)
Информация о пользователе dzver
dzver
Скрыть | 4 сентября 2004 г., 21:22
SMT

значит, если с помощью КМ можно получить настоящее случайное число (экспериментально), то тезис Тьюринга под сомнением (как же так, какой-то физик может вычислить СЧ, а машина Тьюринга - не может)

Именно что я считаю что ето не так.

Что имеете ввиду под "получить настоящее случайное число".

Если вы о бесконечную случайную дробь Семенова "целиком" - т.е. "актуально", то для етого привлекать КМ не необходимо.

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

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

Если вы под "получить настоящее случайное число" имеете ввиду генератор нулей и единиц который их генерит абсолютно случайно /а не псевдослучайно/ - напр. с вероятности 50%-50% - да, КМ дает возможность получить физически такого генератора - которого из классической МТ в принципе нельзя получить.

Ниже под "генератора случайных чисел" я понимаю именно такого генератора символов 0 и 1 с абсолютной 50%-ной случайности - а не генератора бесконечной случайной дроби "целиком" какого не существует.

И мое утверждение состоит в том, что вычислительная мощность МТ с ИГСЧ /идеальном генераторе случайных чисел/ физически такая, как и вычислительная мощность обычной МТ, если рассматривать их не на "актуальной бесконечности", а на конечном, хотя и произвольно большом интервале.

Поскольку вычисления производимые МТ с ИГСЧ /случайных МТ/ могут быть возпроизведены разветвляющимся множеством обычных МТ.

Т.е. на каждом конечном етапе своего вычисления результат МТ с ИГСЧ не содержит ничего такого которого невозможно получить обычным МТ.

Поетому никакой физик или квантовой компьютер таким образом вычислить невычислимое число тоже не может.

Утверждение Семенова что они /МТ с ИГСЧ и МТ без ИГСЧ/ различаются на актуальной бесконечности - хотя и может быть математически верное - но физически ему нельзя придать смысла.

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

Просто нам надо "посмотреть на актуальную бесконечность" и "там" воочию увидим, остановилась ли обычная МТ или нет.

Я тоже думаю, Семенову надо четко определится что он именно утверждает...
Информация о пользователе SMT
SMT
Скрыть | 5 сентября 2004 г., 02:59
нужно ввести характеристику конечной длины для любой последовательности (конечно, о взаимно-однозначном соответствии речи нет), предъявив которую, мы бы доказали, что "вычислили" последовательность. например, остаток от деления суммы цифр на 10. такая величина имела бы смысл, если бы, с одной стороны, она для каждой последовательности сходилась, и, с другой, хорошо бы характеризовала последовательность. циклическая сумма не сходится для иррациональных чисел, давайте попробуем придумать что-то другое.
Информация о пользователе dzver
dzver
Скрыть | 5 сентября 2004 г., 03:47
SMT

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

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

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

Например, цепочка Семенова имеет статистическое свойство что среднее всех разрядов клонит к 1/2 - частота встречания 0 и 1 в любой подцепочки одинакова и клонит к 1/2 с увеличением размера подцепочки.

Но напр. периодическая последовательность 0.101010101.... имеет того же свойства; можно придумать и непериодические последовательности такого рода - напр.

0.011011100101110.... /образовано как конкатенация бинарных представлений натуральной последовательности, аналог в десятичном записи 0.012345678910111213141516..../

Если бы возможно было сжать собственное бесконечное время в конечного временного интервала и понаблюдать за результатом извне...
Информация о пользователе SMT
SMT
Скрыть | 5 сентября 2004 г., 07:26
сам хеш (так я буду называть характеристику) доказательством считать нельзя. но он придуман не для доказательства факта, что машина что-то вычисляет, а чтобы в краткой форме представить результат. то есть Семенов говорит: "я вычислил". мы ему верим, но просим дать хеш, чтобы сверить с нашим результатом (если мы вычисляем одно и то же). неоднозначность будет, но ведь доверяют же CRC, хотя он тоже не дает 100% гарантии
Информация о пользователе dzver
dzver
Скрыть | 5 сентября 2004 г., 07:56
SMT

Назовем для краткости бесконечную цепочку из абсолютно случайных нулей и единиц "цепочку Семенова".

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

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

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

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

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

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

Но.. поскольку все конечные последовательности вычислимы, а цепочка на каждом етапе конечна /хотя и произвольно большая/ то такой хеш для конечных последовательностей всегда даст несовпадение, независимо дали ети конечные последовательности получались вычислением или являются конечное подмножество цепочку Семенова.
Информация о пользователе SMT
SMT
Скрыть | 5 сентября 2004 г., 09:18
вот теперь понятно! вычисление цепочек Семенова не соответствует научному методу :*) так как он не может повторить получение цепочки, то можно считать что он её и не получил
Информация о пользователе SMT
SMT
Скрыть | 5 сентября 2004 г., 09:23
;)))))))))))))
Информация о пользователе dzver
dzver
Скрыть | 5 сентября 2004 г., 10:00
так как он не может повторить получение цепочки, то можно считать что он её и не получил

Если бы он и хоть одну цепочку сгенерил:))

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

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

Может быть, такой тест и на самом деле является "хороший хеш" для цепочек Семенова? Хотя конечно ничего не доказывает.
Информация о пользователе SMT
SMT
Скрыть | 5 сентября 2004 г., 12:00
суть не в наличии цепочки. можно вместо цепочки взять генератор, функцию

f:N-{0,1}

но прежде чем говорить о такой функции, надо описать множества аргументов и значений, а также правила (формальные) для вычисления. если Александр опишет Семенова, бросающего монетку, настолько полно, что на это описание можно будет ввести в формальную теорию, то открытие состоялось
Информация о пользователе dzver
dzver
Скрыть | 5 сентября 2004 г., 12:24
можно вместо цепочки взять генератор, функцию f:N-{0,1} но прежде чем говорить о такой функции, надо описать множества аргументов и значений, а также правила (формальные) для вычисления

Eсли на цепочки Семенова имеется генератор с формальных правил для вычисления, она заведомо не случайна; во всяком случае, не больше чем числа pi или e.

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

/Возможность функцию типа Rand() реализующая ИГСЧ пока в расчет не берем поскольку ето "нечестно"/
Информация о пользователе dzver
dzver
Скрыть | 5 сентября 2004 г., 12:33
другой аргумент - если цепочка Семенова описывалась бы формальным алгоритмом f, то ето значит что f "компрессирует инфу репрезентируемой цепочки" до конечной фиксированной длиной описания самого f; но как известно, случайные цепочки не поддаются компрессии и длина генерящих программ соизмерима с длину самого результата, грубо говоря.
Информация о пользователе NO
NO Участник Клуба
WWW: 4spam2no@mail.ru
Скрыть | 5 сентября 2004 г., 15:21
Истинно случайными являются только числа Семенова-Чубайса - полученные на обесточенном компьютере.

И числа Семенова-Пифагора. Впервые эти числа упоминаются в трактате Декарта "К вопросу о эмуляции машины Тьюринга на конечном автомате", Декарт сообщает, что Пифагор детерминировал Семенову амфору с выломанным донышком, полную компакт-дисков с такими числами. По словам Семенова он это сообщение уже получил, но оно пока не дошло. Хотя по нашему общему мнению не может такого быть чтобы получил, но не дошло :)
Информация о пользователе Pier_V_Tin
Pier_V_Tin
PROFESSION DE FOI
E-mail: pier_v_tin@front.ru
Скрыть | 6 сентября 2004 г., 04:15
Вы знаете, есть такой раздел теории сложности вычислений где рассматриваются вероятностные машины Тьюринга.

Вероятностная машина Тьюринга это машина с дополнительной лентой на которой записана случайная последовательность 0 и 1. Такая машина на выходе выдает 0 или 1. Такая машина f вычисляет принадлежность входа x некоторому множеству L (которое в теории сложности принято называть языком) с некоторой ошибкой a(|x|) где |x| длинна входного слова.

x принадлежит L = Вероятность(f(x)=1)1-a(|x|)

x не принадлежит L = Вероятность(f(x)=1)= a(|x|).

В этой теории много результатов, например задача распознавания простых чисел решается на вероятностной машине Тьюринга за полиномиальное время, т.е. существует такая случайная величина \ksi и машина Тьюринга решающая эту задачу (при обращении к \ksi )...
Информация о пользователе SMT
SMT
Скрыть | 6 сентября 2004 г., 19:22
за полиномиальное время (от величины n входного числа) можно проверить простоту числа, просто поделив его на числа от 1 до sqrt(n).

только я не понимаю, почему в книжке написано, что лучший современный алгоритм Адлемана-Померанса-Румели дает результат за O((log n)^(c*log log log n))?

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

мои догадки правильны?
Информация о пользователе Pier_V_Tin
Pier_V_Tin
PROFESSION DE FOI
E-mail: pier_v_tin@front.ru
Скрыть | 8 сентября 2004 г., 06:20
Ну да. В этой науке почему то принято считать что машина правильно работает (распознает язык) если вероятность ошибки меньше 1/3. Я этого не понимаю.