الترقيم التقابلي

الترقيم التقابلي هو أي نظام عددي يمكن فيه تمثيل كل عدد صحيح غير سالب بطريقة واحدة فقط باستخدام سلسلة محدودة من الأرقام . ويشير الاسم إلى التقابل (أي التناظر الأحادي) الموجود في هذه الحالة بين مجموعة الأعداد الصحيحة غير السالبة ومجموعة السلاسل المحدودة التي تستخدم مجموعة محدودة من الرموز (الأرقام).

معظم أنظمة العد العادية، كالنظام العشري الشائع ، ليست تقابلية، لأن أكثر من سلسلة أرقام يمكن أن تمثل العدد الصحيح الموجب نفسه. فعلى وجه الخصوص، لا تُغير إضافة الأصفار البادئة القيمة المُمثلة، لذا فإن "1" و"01" و"001" جميعها تُمثل العدد واحد . ورغم أن الأولى فقط هي الأكثر شيوعًا، فإن إمكانية وجود سلاسل أخرى تعني أن النظام العشري ليس تقابليًا. أما النظام الأحادي ، الذي يتكون من رقم واحد فقط، فهو تقابلي.

الترقيم التقابلي ذو الأساس k هو ترميز موضعي تقابلي . يستخدم سلسلة من الأرقام من المجموعة {1، 2، ...، k } (حيث k ≥ 1) لترميز كل عدد صحيح موجب؛ يحدد موضع الرقم في السلسلة قيمته كمضاعف لقوة من قوى k . أطلق سموليان (1961) على هذا الترميز اسم k -adic، ولكن يجب عدم الخلط بينه وبين الأعداد p -adic : فالأعداد التقابلية هي نظام لتمثيل الأعداد الصحيحة العادية بسلاسل محدودة من الأرقام غير الصفرية، بينما الأعداد p -adic هي نظام من القيم الرياضية التي تحتوي على الأعداد الصحيحة كمجموعة فرعية وقد تحتاج إلى سلاسل لانهائية من الأرقام في أي تمثيل عددي.

يستخدم نظام الترقيم الثنائي ذو الأساس k مجموعة الأرقام {1، 2، ...، k } ( k ≥ 1) لتمثيل كل عدد صحيح غير سالب بشكل فريد، كما يلي:

• يتم تمثيل العدد الصحيح صفر بسلسلة فارغة .
• العدد الصحيح الذي يمثله سلسلة الأرقام غير الفارغة

a _n a _{n −1} ... a ₁ a ₀

يكون

a _n k ⁿ + a _{n −1} k ^{n −1} + ... + a ₁ k ¹ + a ₀ k ⁰ .

• سلسلة الأرقام التي تمثل العدد الصحيح m > 0 هي

a _n a _{n −1} ... a ₁ a ₀

أين

${\displaystyle {\begin{aligned}a_{0}&=m-q_{0}k,&q_{0}&=f\left({\frac {m}{k}}\right)&\\a_{1}&=q_{0}-q_{1}k,&q_{1}&=f\left({\frac {q_{0}}{k}}\right)&\\a_{2}&=q_{1}-q_{2}k,&q_{2}&=f\left({\frac {q_{1}}{k}}\right)&\\&\,\,\,\vdots &&\,\,\,\vdots \\a_{n}&=q_{n-1}-0k,&q_{n}&=f\left({\frac {q_{n-1}}{k}}\right)=0\end{aligned}}}$

و

${\displaystyle f(x)=\lceil x\rceil -1,}$

${\displaystyle \lceil x\rceil }$كونه أصغر عدد صحيح لا يقل عن x ( دالة السقف ).

في المقابل، يمكن تعريف الترميز الموضعي القياسي باستخدام خوارزمية تكرارية مماثلة حيث

${\displaystyle f(x)=\lfloor x\rfloor ,}$

بالنسبة لقاعدة معينة${\displaystyle k\geq 2}$،

• عدد الأرقام في العدد الثنائي ذي الأساس k الذي يمثل عددًا صحيحًا غير سالب n هو

  ${\displaystyle \lfloor \log _{k}((n+1)(k-1))\rfloor }$[ ^{1 ]} على النقيض ^من${\displaystyle \lceil \log _{k}(n+1)\rceil }$بالنسبة للأرقام العادية ذات الأساس k ؛ إذا كان k = 1 (أي أحادي)، فإن عدد الأرقام هو n فقط ؛

• أصغر عدد صحيح غير سالب، يمكن تمثيله في عدد ثنائي الأساس k بطول${\displaystyle \ell \geq 0}$، يكون

  ${\displaystyle \mathrm {min} (\ell )={\frac {k^{\ell }-1}{k-1}}}$؛

• أكبر عدد صحيح غير سالب، يمكن تمثيله في عدد ثنائي تقابلي أساسه k بطول${\displaystyle \ell \geq 0}$، يكون

  ${\displaystyle \mathrm {max} (\ell )={\frac {k^{\ell +1}-k}{k-1}}}$، أي ما يعادل${\displaystyle \mathrm {max} (\ell )=k\times \mathrm {min} (\ell )}$، أو${\displaystyle \mathrm {max} (\ell )=\mathrm {min} (\ell +1)-1}$؛

• تكون الأرقام الثنائية ذات الأساس k والأرقام العادية ذات الأساس k لعدد صحيح غير سالب n متطابقة إذا وفقط إذا لم يحتوي الرقم العادي على الرقم 0 (أو، بشكل مكافئ، الرقم الثنائي ليس سلسلة فارغة ولا يحتوي على الرقم k ).

بالنسبة لقاعدة معينة${\displaystyle k\geq 1}$،

• يوجد بالضبط${\displaystyle k^{\ell }}$الأعداد التقابلية ذات الأساس k بطول${\displaystyle \ell \geq 0}$; ^{[ 2 ]}
• تكون قائمة الأعداد الثنائية التقابلية ذات الأساس k ، مرتبةً ترتيبًا طبيعيًا للأعداد الصحيحة المُمثلة، تلقائيًا بترتيب قصير معجمي (الأقصر أولًا، معجميًا ضمن كل طول). وبالتالي، باستخدام λ للدلالة على السلسلة الفارغة ، تكون الأعداد ذات الأساس 1، 2، 3، 8، 10، 12، و16 كما يلي (حيث تم سرد التمثيلات العادية للمقارنة):

34152 (في النظام التقابلي ذي الأساس 5) = 3×5 ⁴ + 4×5 ³ + 1×5 ² + 5×5 ¹ + 2×1 = 2427 (بالنظام العشري).

119A (في النظام العشري التقابلي، حيث يمثل "A" قيمة الرقم عشرة) = 1×10 ³ + 1×10 ² + 9×10 ¹ + 10×1 = 1200 (بالنظام العشري).

تكون القائمة الأبجدية النموذجية التي تحتوي على أكثر من 26 عنصرًا تقابلية، باستخدام الترتيب A، B، C...X، Y، Z، AA، AB، AC...ZX، ZY، ZZ، AAA، AAB، AAC...

النظام العشري التقابلي هو نظام عددي موضعي أساسه عشرة لا يستخدم رقمًا لتمثيل الصفر . بدلاً من ذلك، يحتوي على رقم لتمثيل العشرة، مثل A.

كما هو الحال في النظام العشري التقليدي ، يُمثل كل رقم قوة من قوى العشرة، فمثلاً 123 يُكتب "مئة زائد عشرات زائد ثلاثة آحاد". جميع الأعداد الصحيحة الموجبة التي تُمثل بأرقام غير صفرية فقط في النظام العشري التقليدي (مثل 123) لها نفس التمثيل في النظام العشري التقابلي. أما الأعداد التي تستخدم الصفر، فيجب إعادة كتابتها، فمثلاً 10 يُصبح A، و20 يُصبح 1A ("عشرة زائد عشرة آحاد")، و100 يُصبح 9A، و101 يُصبح A1، و302 يُصبح 2A2، و1000 يُصبح 99A، و1110 يُصبح AAA، و2010 يُصبح 19AA، وهكذا.

تُجرى عمليتا الجمع والضرب في هذا النظام بنفس طريقة النظام العشري التقليدي، باستثناء أن الترحيل يحدث عندما يتجاوز الرقم عشرة، بدلاً من أن يتجاوز تسعة. لذا، لحساب 643 + 759، نحتاج إلى اثنتي عشرة وحدة (نكتب 2 في خانة الآحاد ونرحّل 1 إلى خانة العشرات)، وعشر عشرات (نكتب A دون الحاجة إلى الترحيل إلى خانة المئات)، وثلاث عشرة مئة (نكتب 3 ونرحّل 1 إلى خانة الآلاف)، وألف واحد (نكتب 1)، لنحصل على النتيجة 13A2 بدلاً من 1402 كما هو متعارف عليه.

في نظام العد الثنائي ذي الأساس 26، يمكن استخدام حروف الأبجدية اللاتينية من "A" إلى "Z" لتمثيل القيم الرقمية من 1 إلى 26. (A=1، B=2، C=3، ...، Z=26)

بهذا الاختيار للترميز، تبدأ متتالية الأرقام (بدءًا من 1) كالتالي: A، B، C، ...، X، Y، Z، AA، AB، AC، ...، AX، AY، AZ، ​​BA، BB، BC، ...

يمثل كل موضع رقم قوة من قوى العدد ستة وعشرين، فعلى سبيل المثال، يمثل الرقم WI القيمة 23 × 26 ¹ + 9 × 26 ⁰ = 607 في النظام العشري.

تستخدم العديد من برامج الجداول الإلكترونية ، بما فيها مايكروسوفت إكسل، هذا النظام لتسمية أعمدة الجدول، بدءًا من A، B، C، ...، Z، AA، AB، ...، AZ، ​​BA، ...، ZZ، AAA، وهكذا. على سبيل المثال، في إكسل 2013، يمكن أن يصل عدد الأعمدة إلى 16384 عمودًا (2^ ¹⁴ بالرمز الثنائي)، مُسمّاة من A إلى XFD. ^{[ 3 ]} كما تُسمى أنواع البرامج الضارة باستخدام هذا النظام: على سبيل المثال، أول فيروس ماكرو واسع الانتشار في مايكروسوفت وورد، وهو Concept، يُسمى رسميًا WM/Concept.A، ونوعه السادس والعشرون WM/Concept.Z، ونوعه السابع والعشرون WM/Concept.AA، وهكذا. ويُستخدم نوع مُعدّل من هذا النظام لتسمية النجوم المتغيرة . ^{[ 4 ]} ويمكن تطبيقه على أي مشكلة تتطلب تسمية منهجية باستخدام الأحرف، مع استخدام أقصر السلاسل النصية الممكنة.

إن حقيقة أن لكل عدد صحيح غير سالب تمثيلاً فريداً في نظام العد الثنائي ذي الأساس k ( حيث k ≥ 1) هي " نظرية شعبية " أعيد اكتشافها مرات عديدة. من الأمثلة المبكرة على ذلك ما ذكره فوستر (1947) في حالة k = 10، وما ذكره سموليان (1961) وبوم (1964) في حالة k ≥ 1. يستخدم سموليان هذا النظام لتوفير ترقيم غودل لسلاسل الرموز في نظام منطقي؛ بينما يستخدم بوم هذه التمثيلات لإجراء عمليات حسابية في لغة البرمجة P'' . يذكر كنوت (1969) الحالة الخاصة k = 10، ويناقش سالوما (1973) الحالات k ≥ 2. ويبدو أن فورسلوند (1995) هو إعادة اكتشاف أخرى، ويفترض أنه إذا كانت أنظمة الترقيم القديمة تستخدم أساسًا تقابليًا k ، فقد لا يتم التعرف عليها على هذا النحو في الوثائق الأثرية، بسبب عدم الإلمام العام بهذا النظام.

• بوم، سي. (يوليو 1964)، "حول عائلة من آلات تورينج ولغة البرمجة ذات الصلة"، نشرة ICC ، 3 : 191.
• فورسلوند، روبرت ر. (1995)، "بديل منطقي لنظام الأعداد الموضعي الحالي"، مجلة الجنوب الغربي للرياضيات البحتة والتطبيقية ، 1 : 27-29 ، MR 1386376 ، S2CID 19010664  .
• فوستر، جيه إي (1947)، "نظام عددي بدون رمز الصفر"، مجلة الرياضيات ، 21 (1): 39-41 ، doi : 10.2307/3029479 ، JSTOR 3029479 .
• كنوت، دي إي (1969)، فن برمجة الحاسوب، المجلد 2: الخوارزميات شبه العددية (  الطبعة الأولى)، أديسون-ويسلي، حل التمرين 4.1-24، ص 195(يناقش التقابل في النظام ذي الأساس 10.)
• سالوما، أ. (1973)، اللغات الرسمية ، دار النشر الأكاديمية، ملاحظة 9.1، ص 90-91(يناقش الأساس التقابلي k لجميع قيم k ≥ 2.)
• سموليان، ر. (1961)، " 9. الترتيب المعجمي؛ التمثيل النوني للأعداد الصحيحة" ، نظرية الأنظمة الرسمية ، دراسات حوليات الرياضيات، المجلد  47، مطبعة جامعة برينستون، الصفحات 34-36 .