АТД числа с операцией сложения

[vopl]

Читаю книжку Бениаминов Е.М., Ефимова Е.А. Элементы универсальной алгебры и ее приложений в информатике.

По окончании 1 главы есть задачи и упражнения, номер 1.8. (стр 22)
'Опишите тип данных "Двоичные числа" с операцией сложения двоичных чисел'

Думаю так:
По определению - тип данных это тройка <Имя, Cигнатура, Mножество определяющих соотношений> (стр 17).
Сигнатура - это пара <Множество имен носителей, Множество имен типизированных операций> (стр 14, но множество отношений пусто, поэтому его не пишу).

запишу формально:

<
   Имя: Тип_Двоичные_числа,
   Cигнатура: 
   <
      Множество имен носителей: {Двоичное_число}
      Множество имен типизированных операций:{Сложение: Двоичное_число X Двоичное_число -> Двоичное_число}
   >
   Множество определяющих соотношений: ???
>

Двоичное число можно кодировать как сетку 2-цифр по 2-разрядам, примерно так

... ц ц ц ц ц ц ц, ц  ц  ц  ц ...   цифры
... 6 5 4 3 2 1 0 -1 -2 -3 -4 ...   разряды

и еще надо добавить знак +-

получается, что двоичное число - это знак +- и бесконечная совокупнось пар <2-цифра, 2-разряд>, где 2-разряд - это целое, 2-цифра - это "0" или "1". Вычислить значение числа можно как сумму тех разрядов, которым соответствует цифра "1".

Сложение. Думаю складывать в столбик(по другому не умею). Тогда надо сделать следующее:
1. для двух чисел, уметь сопоставлять их друг с другом так, чтобы можно было для заданного разряда выделять соответствующие ему цифры в одном и другом числе (это просто)
2. уметь складывать 2 одноцифровых числа (тут таблица сложения поможет)
3. уметь учитывать остаток от предыдущего действия на следующий разряд, тоесть, уметь складавать по 3 одноцифровых числа, это несложно по рекурсии
4. уметь для заданного разряда получать следующий разряд (это просто)
5. так как такое сложение - "однопроходное" и цифры результата в бОльших разрядах зависят от цифр операндов в меньших - то надо найти разряд, с которого можно такое сложение начинать. Это должен быть такой разряд, меньше которого нет разрядов с цифрой "1" (они будут влиять). В моем кодировании такого разряда выделить нельзя, разряды вправо уходят в -беск. Значит такое кодирование не совместимо с таким сложением. Хек приплыли. Надо другое кодирование или другой способ сложения

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

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

Bins:
   носитель: множество слов на алфавите {0,1} 
   отображения:
   {
      _0: ->Bins, 
      _1: ->Bins, 
      C:Bins x Bins -> Bins, 
      Add:Bins x Bins -> Bins
   }
   соотношения:
   {
      //выделение цифры 0
      _0=0
      //выделение цифры 1
      _1=1
      
      //конкатенация с нулем
      C(x,_0) = x0
      //конкатенация с единицей
      C(x,_1) = x1
      
      
      //коммутативность явно, чтобы последующие соотношения не дублировать по 2 раза
      Add(x,y) = Add(y,x)

      //для простых операндов
      Add(_0, _0) = _0
      Add(_1, _0) = _1
      Add(_1, _1) = C(_1, _0)

      //один из операндов составной
      Add(C(x,_0), _0) = C(x,_0)
      Add(C(x,_1), _0) = C(x,_1)
      Add(C(x,_0), _1) = C(x,_1)
      Add(C(x,_1), _1) = C(Add(x,_1),_0)
      
      //оба составные
      Add(C(x,_0), C(y,_0)) = C(Add(x,y),_0)
      //Add(C(x,_1), C(y,_0)) = C(Add(x,y),_1)   по комутации эквивалентно следующему, можно не писать
      Add(C(x,_0), C(y,_1)) = C(Add(x,y),_1)
      Add(C(x,_1), C(y,_1)) = C(Add(Add(x,y),_1),_0)
   }   
   

   
   
   проверка
   111 + 1 = 
   Add(C(C(_1,_1),_1), _1) = 
   C(Add(C(_1,_1), _1), _0) = 
   C(C(Add(_1,_1),_0), _0) = 
   C(C(C(_1, _0),_0), _0) = 
   1000
все.
-------------------------

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

[Xaositect]

vopl в сообщении #431462 писал(а):

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

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

[vopl]

Xaositect в сообщении #431475 писал(а):

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

ээ.. чесно не понимаю, причем тут количество чисел? Натуральных - хоть и не континуум, но тоже бесконечно много. Но Bins - вполне справедлив для любого из них, хоть конечного, хоть бесконечного. Он же не работает со множеством этих чисел, он работает как бы "на нем" с парами через Add.
Есть такие натуральные, которые нельзя представить в виде конечного объекта. И более, любое натуральное можно представить в виде бесконечного объекта. Например 38:
"...000...0038" - тут бесконечно много нулей слева.

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

   "...000...0010" + "...000...001"= 
   Add(C(C(... C(0,0),..._1), _0),  C(C(... C(0,0),..._0), _1)) = 
   
   //...тут бесконечно много преобразований по соотношениям из Bins...   причем самих соотношений - конечное число (15 штук)

   C(C(... C(0,0),..._1), _1) = 
   "...000...011"

Просмотрел книжку еще раз, там нигде не говорится что носитель типа данных должен быть конечен. У меня в Bins он бесконечен ("множество слов на алфавите {0,1}").

Продолжая на действительные числа:
Любое действительное число можно представить в виде бесконечного объекта. Например 38.4
"...000...038,40...000...".
Например, 1/3
"...000...000,33...333...".
Ну а у иррационального справа будут какие то разные цифры.

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

Xaositect в сообщении #431475 писал(а):

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

Ну тоесть отказаться от действительных чисел, и взять другие?

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

[Xaositect]

vopl в сообщении #431531 писал(а):

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

Это неверно. Любое натуральное число представляется некоторым конечным количеством цифр. Именно это позволяет Вам получить любое натуральное число в виде конечной формулы, содержащей отображения 0, 1 и C

Цитата:

И более, любое натуральное можно представить в виде бесконечного объекта.

Это, разумеется, правда.

vopl в сообщении #431531 писал(а):

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

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

vopl в сообщении #431531 писал(а):

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

Ну, мы можем получить с помощью сложения в столбик неравенства вида $q\leq a+b<q+10^{-n}$, если запишем $a$ и $b$ с точностью до $n+1$ знака после запятой. После этого, записав рациональные $q$ как десятичные дроби, мы получим последовательность, из которой можно выписать все цифры числа $a+b$.

vopl в сообщении #431531 писал(а):

Ну тоесть отказаться от действительных чисел, и взять другие?

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

[vopl]

По поводу действительных чисел уяснил, спасибо.

Xaositect в сообщении #431567 писал(а):

vopl в сообщении #431531 писал(а):

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

Это неверно. Любое натуральное число представляется некоторым конечным количеством цифр. Именно это позволяет Вам получить любое натуральное число в виде конечной формулы, содержащей отображения 0, 1 и C

а такое число
9...9
тоесть бесконечное количество девяток - это не натуральное? Смотрю аксиомы Пеано и не вижу никаких противоречий.
Могу из него получить следующее
9...9 + 1 = 10...0
получается единица и бесконечное количество нулей - тоже натуральное

А что не так с такими числами? Почему спрашиваю - я их использую в своем Bins, и говорю что алгоритм сложения в столбик справедлив для пары таких бесконечных натуральных. Он, конечно, бесконечно долго работать будет, но справедлив - же?

[Xaositect]

vopl в сообщении #431585 писал(а):

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

Нет, не натуральное. Противоречие: $x = \dots 9\dots 9 \Rightarrow x-9 = \dots 9 \dots 90 = 10x\Rightarrow 9x + 9 = 0\Rightarrow x + 1 = 0$, а значит $x$ должно быть предшественником 0.

-- Вт апр 05, 2011 20:48:24 --

vopl в сообщении #431585 писал(а):

А что не так с такими числами? Почему спрашиваю - я их использую в своем Bins, и говорю что алгоритм сложения в столбик справедлив для пары таких бесконечных натуральных. Он, конечно, бесконечно долго работать будет, но справедлив - же?

Да, сложение в столбик в некотором смысле работать будет.

[vopl]

Xaositect в сообщении #431593 писал(а):

vopl в сообщении #431585 писал(а):

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

Нет, не натуральное. Противоречие: $x = \dots 9\dots 9 \Rightarrow x-9 = \dots 9 \dots 90 = 10x\Rightarrow 9x + 9 = 0\Rightarrow x + 1 = 0$, а значит $x$ должно быть предшественником 0.

Не согласен, на мой взгляд так
$x = \dots 9\dots 9 \Rightarrow x-9 = \dots 9 \dots 90 \not= 10x$

По Вашему получается что "бесконечное количество девяток" равно "другому бесконечному количеству девяток", но эти две бесконечности - ведь разные? Если у числа $x$ обозначить количество девяток $N$ то в $x-9 = \dots 9 \dots 90$ будет количество девяток $N-1$? Тогда нелзя говорить что $x-9=x*10$.

[Xaositect]

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

[vopl]

Xaositect в сообщении #431730 писал(а):

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

Возьмем аксиомы Пеано и начнем выписывать последовательность натуральных чисел через операцию "следующий за" $s$
$1, 2, 3, \dots$
очевидно, выписование никогда не завершится.

Обратимся к Ктулху, который живет всегда. Он продолжает выписывать последовательность натуральных чисел и через вечность выписывает некое число $9 \dots 9$,
запишу его так $[9,k]$. В нем $k$ девяток и $k$ бесконечно.
Через десять вечностей $k$ ктулху выпишет число $[9,k]0$, а еще через 9 шагов $[9,k]9 = [9,k+1]$

Так как мощности $|[9,k]| = |[9,k+1]|$ (из теории множеств) и элементы обоих множеств берутся из единой последовательности (натуральных чисел) то равны сами множества а следовательно и закодированные ими числа.

Тогда $[9,k] = [9,k+1]$. (*)

(Оффтоп)

Ктулху гоняет по кругу одни и те же бесконечные числа тоесть нарушает 4 аксиому Пеано, тогда $[9,k]$ и $[9,k+1]$ не являются натуральными относительно друг друга.

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

Или Ктулху-Синус всетаки повторяет слагаемые, бесконечно удаленные от начала последовательности ряда Тейлора (тоесть тоже гоняет по кругу)? Тогда такие слагаемые не должны вносить вклад в результирующую сумму, тоесть должны быть 0. Но в ряде нет нулевых элементов. И нет элементов, дающих в сумме ноль. Значит этот вариант не подходит. Тоесть Ктулху-Синус действительно не гоняет по кругу. Тогда $[9,k] \ne [9,k+1]$ и это всетаки разные числа.

Из Ктулху-Синуса можно сказать следующее:
если мощности равны $|[9,k]| = |[9,k+1]|$ (из теории множеств) и элементы обоих множеств берутся из единой последовательности (натуральных чисел) то
все равно нельзя говорить о равенстве закодированных ими чисел.

Тоесть $[9,k]-9 \ne [9,k]*10$

На таком неравенстве (в частности) я основывал утверждение что столбик справедлив для бесконечно больших чисел. Ведь если $[9,k]-9 = [9,k]*10$ то найдутся "гоняющие по кругу" и столбик перестанет правильно сопоставлять разряды у двух чисел и следовательно не будет верным.

[vopl]

Без Ктулху и попроще:

Возьмем бесконечное множество $N$, выделим в нем любой элемент $n$ и изымем его из $N$. Получим множество $N\setminus \{n\}$ такое что $N\setminus\{n\} \ne N$, потомучто они отличаются на элемент $n$. Но мощности у обоих одинаковые $|N\setminus\{n\}| = |N|$ и элементы, за исключением $n$, одинаковые.

Таким образом, дописывание девятки к $x=9...9$ не дает тот же самый $x$.

[Xaositect]

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

[vopl]

Xaositect в сообщении #431593 писал(а):

Нет, не натуральное. Противоречие: $x = \dots 9\dots 9 \Rightarrow x-9 = \dots 9 \dots 90 = 10x\Rightarrow 9x + 9 = 0\Rightarrow x + 1 = 0$, а значит $x$ должно быть предшественником 0.

Xaositect в сообщении #431730 писал(а):

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

Возьмем бесконечное множество $N$, выделим в нем любой элемент $n$ и изымем его из $N$. Получим множество $N\setminus \{n\}$ такое что $N\setminus\{n\} \ne N$, потому что они отличаются на элемент $n$. Тоесть, если из бесконечного множества выкинуть хотя бы один элемент - то оно станет другим множеством, не равным исходному.

Тогда
$x = \dots 9\dots 9 \Rightarrow x-9 = \dots 9 \dots 90 \not= 10x$

Тогда представленное Вами противоречие не верно.

[Joker_vD]

Извините, но "число" $\dots9\dots9$ — отнюдь не множество из девяток.

[vopl]

Joker_vD в сообщении #432034 писал(а):

Извините, но "число" $\dots9\dots9$ — отнюдь не множество из девяток.

Ага. Не множество.

Но такие числа можно однозначно отобразить на множества. Тоесть построить биекцию из множества таких чисел в множество "каких то множеств".

Такая биекция - это десятичная система счисления (или двоичная для Bins который раньше по ветке мелькал).


10-цифра - это одно из 0,1,2,3,4,5,6,7,8,9
10-разряд - это один элемент из последовательности 1,10,100,1000,...

Паре <10-цифра, 10-разряд> можно однозначно сопоставить число, равное "10-цифра"*"10-разряд"
Множеству таких пар можно сопоставить число, равное сумме чисел, сопоставленных каждой паре соответственно.

Если в множестве таких пар нет двух пар, у которых значение 10-разряда совпадает - то таким множеством можно кодировать числа вида $\dots9\dots9$. Тут каждая девятка - это пара из <"9", 10-разряд-соответствующий-позиции-этой-девятке>.

Тоесть $\dots9\dots9$ можно рассматривать как множество.
Вот примерно так.


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

[Joker_vD]

Обозначим ваше "число" за $\chi$, $\chi = \dots9\dots9$

vopl в сообщении #432043 писал(а):

10-разряд - это один элемент из последовательности 1,10,100,1000,...

А вас не смущает, что это множество — счетно, и без натурального ряда его не построить? Значит, есть там и разряд десятки, соответствующий $\chi$. Или нету. Ладно, это не важно.

Но даже если и так: хи состоит из пар $(9,n)$, где $n \in \mathbb N \cup \{0\}$. Из чего состоит хи минус девять? Из $(9,n)$, где $n \in \mathbb N$, плюс еще $(0,0)$. А из чего состоит десять хи? Из $(9,n)$, где $n \in \mathbb N$, плюс еще $(0,0)$.