представление действительных чисел алгоритмами

[Dandan]

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

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

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

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

[venco]

Dandan в сообщении #342756 писал(а):

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

Главное, что это множество - счётно.

[maxal]

см. http://en.wikipedia.org/wiki/Computable_number

[Dandan]

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

[epros]

Dandan в сообщении #343109 писал(а):

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

Если я правильно понимаю, то потребуется иерархия оракулов:
http://en.wikipedia.org/wiki/Oracle_mac ... g_problems
причём не факт, что множество определяемых ZFC действительных чисел покрывается конечной иерархией оракулов. Почему-то мне кажется, что даже счётно-бесконечная иерархия не поможет. А если множество оракулов несчётно, то такое ("алгоритмическое") определение действительного числа вряд ли окажется проще классического теоретико-множественного.

[Андрей АK]

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

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

[zZoMROT]

Андрей АK в сообщении #344360 писал(а):

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

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

[Black_Evg]

1) Никому не придет в голову представлять алгоритмом натуральное число.

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

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

Prorab:

Ник заблокирован как клон Черный Евгений. Предупреждение за бессодержательное сообщение и оффтопик.

[cognize]

Dandan
Могу Вам посоветовать почитать вот эту книгу:
Б. А. Кушнер "Лекции по конструктивному математическому анализу".
Там все построено на нормальных алгорифмах Маркова (они эквивалентны машине Тьюринга).

-- Вс ноя 28, 2010 03:21:49 --

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

-- Вс ноя 28, 2010 03:28:17 --

Dandan в сообщении #343109 писал(а):

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

Да, это так, но я бы не сказал, что изменения эти в худшую сторону, скорее наоборот.

[Андрей АK]

А вот такое расширение темы.

Если бы можно было представить алгоритмом большое число или даже бесконечно длинное число (например алгоритмом 1/3 представляется бесконечная последовательность нулей и единиц вида 010101... а 1/5 - это 001100110011... ), и при этом был бы механизм сложения и умножения этих алгоритмов но такой чтобы сложение и умножение алгоритмов соответствовало бы сложению и умножению последовательности нулей и единиц, которые они представляют (но например 1/3+1/5 = 8/15 = 01000100010001 не равно 0101010101 + 01100110011...= 0111100111100...).

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

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

Но думаю это невозможно (может быть где-то доказана теорема?).

Т.е. ,например, если у нас в кольце $k^x \cdot k^y = k^{x+y} $ умножение элементов сводится к сложению номеров элементов то уже для сложения этих же элементов у нас нет простого способа получить точный номер z такой что $k^x + k^y = k^z $
И наоборот, если есть простой способ узнать номер элемента при сложении двух элементов кольца, то нет способа получить этот же номер после умножения элементов, кроме как используя обычное кольцо целых чисел, что не подходит, поскольку там длина алгоритма, задающего число равна самому числу.

Как например невозможно просто найти такую дробь , которая бы задавала последовательность:
0101010101 + 01100110011...= 0111100111100... = ?/? = 5/21
зная дроби ,задающие исходные последовательности, 1/3 = 010101... и 1/5 = 0011001...

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

[Tod Leben]

Dandan в сообщении #342756 писал(а):

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

Предположим:мы с Вами,по отдельности,решили алгоритмически описать некое число,пусть это будет единица "1".Начало Вашего алгоритма,примерно:
"assume CS..DS..
main proc..
xor AX,AX
mov AX,..."
...и начало моего:
"Посадил Дед Репку."
...хм...чёт они немного различаются.Вам так не кажется?*почесали свои репы*...Не беда!Они ведь описывают одно и тоже число,и результат у них одинаковый.Всё нормально!*обрадовались мы*...Потом взяли и положили их,алгоритмы эти,в Тьюринговую машинку,и "крутанули" их разок другой.
Вопрос:"Какое количество канонических представлений действительного числа мы получим?".

[Tod Leben]

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

причём не факт, что множество определяемых ZFC действительных чисел покрывается конечной иерархией оракулов.

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

Андрей АK в сообщении #344360 писал(а):

Глупо представлять числа алгоритмами

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

Black_Evg в сообщении #366049 писал(а):

1) Никому не придет в голову представлять алгоритмом натуральное число.

Dandan(у,е) пришло,мне пришло...и я думаю мы здесь не одни.

[Tod Leben]

Андрей АK в сообщении #384633 писал(а):

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

Оригинально,а главное свежо,числа числами представлять!!! Интересно,как же выглядят эти числа?

Андрей АK в сообщении #384633 писал(а):

зная дроби ,задающие исходные последовательности, 1/3 = 010101...

А Вы уверены что это верное представление?

[Андрей АK]

Tod Leben в сообщении #401576 писал(а):

Андрей АK в сообщении #384633 писал(а):

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

Оригинально,а главное свежо,числа числами представлять!!! Интересно,как же выглядят эти числа?

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

Tod Leben в сообщении #401576 писал(а):

Андрей АK в сообщении #384633 писал(а):

зная дроби ,задающие исходные последовательности, 1/3 = 010101...

А Вы уверены что это верное представление?

Если неверное - назовите правильное, если верное - зачем языком зря молоть?
Что за дурацкая манера, задавать бессмысленные риторические вопросы?
Или вы таким образом удовлетворяете свою потребность кого ни будь доставать?
Типа, а спрошу ка я: "А вы уверены что ... <подставить случайным образом выбранный текст из поста>" и пусть ка он поищет черную кошку в темной комнате, а я пока посмеюсь в стороне"?

[venco]

Андрей АK в сообщении #404050 писал(а):

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

Что лучше: $\sqrt 2$ или $1,4142135623730950488016887242097...$?