حساب بوشي

حساب بوشي ذو الأساس k هو نظرية الرتبة الأولى للأعداد الطبيعية مع الجمع والدالة${\displaystyle V_{k}(x)}$وهو يُعرَّف بأنه أكبر قوة للعدد k تقسم x ، وقد سُمِّيَ تكريمًا لعالم الرياضيات السويسري يوليوس ريتشارد بوشي . ولا تحتوي إشارة حساب بوشي إلا على عملية الجمع.${\displaystyle V_{k}}$والمساواة، مع حذف عملية الضرب بالكامل.

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

مجموعة فرعية${\displaystyle X\subseteq \mathbb {N} ^{n}}$يمكن تعريفها في حساب بوشي ذي الأساس k إذا وفقط إذا كانت قابلة للتمييز k .

لو${\displaystyle n=1}$هذا يعني أن مجموعة الأعداد الصحيحة X في الأساس k مقبولة بواسطة آلة أوتوماتيكية . وبالمثل إذا${\displaystyle n>1}$يوجد جهاز آلي يقرأ الأرقام الأولى، ثم الأرقام الثانية، وهكذا، من n عدد صحيح في الأساس k ، ويقبل الكلمات إذا كانت الأعداد الصحيحة n في العلاقة X. 

إذا كان k و l مرتبطين ضربيًا ، فإن حسابات بوشي للأساسين k و l لها نفس القدرة التعبيرية. في الواقع${\displaystyle V_{l}}$يمكن تعريفها في${\displaystyle {\text{FO}}(V_{k},+)}$، نظرية الدرجة الأولى لـ${\displaystyle V_{k}}$و${\displaystyle +}$.

وإلا، فإن نظرية حسابية تتضمن كليهما${\displaystyle V_{k}}$و${\displaystyle V_{l}}$الدوال مكافئة لحسابات بيانو ، التي تتضمن الجمع والضرب، لأن الضرب قابل للتعريف في${\displaystyle {\text{FO}}(V_{k},V_{l},+)}$.

علاوة على ذلك، وبحسب نظرية كوبام-سيمينوف ، إذا كانت العلاقة قابلة للتعريف في كل من حساب بوشي k و l ، فإنها قابلة للتعريف في حساب بريسبورغر . ^{[ 1 ] [ 2 ]}

• بيس، ألكسيس. "دراسة استقصائية حول قابلية التعريف الحسابي" . تم الاطلاع عليه بتاريخ 27 يونيو 2012 .{{cite web}}: CS1 maint: deprecated archiveal service ( link )

• بيس، ألكسيس (1997). " امتدادات غير قابلة للتقرير لحساب بوشي ونظرية كوبهام-سيمينوف". مجلة المنطق الرمزي 62 (4): 1280-1296 . CiteSeerX 10.1.1.2.1007 . doi : 10.2307/2275643 . JSTOR 2275643. S2CID 31780865. Zbl 0896.03011 .