قندس نشيط

في علم الحاسوب النظري ، تهدف لعبة القندس المشغول إلى إيجاد برنامج نهائي بحجم مُحدد، يُنتج (بحسب التعريف) أكبر قدر ممكن من المخرجات، أو يعمل لأطول عدد من الخطوات. ^{[ 2 ]} ولأنّ برنامجًا ذا حلقة لا نهائية يُنتج مخرجات لا نهائية أو يعمل لوقت لا نهائي أمرٌ سهل التصور، تُستبعد هذه البرامج من اللعبة. ^{[ 2 ]} وبدلًا من لغات البرمجة التقليدية، تُستخدم في اللعبة آلات تورينج ذات n حالة ، ^{[ 2 ]} وهي من أوائل النماذج الرياضية للحوسبة . ^{[ 3 ]}

تتكون آلات تورينج من شريط لا نهائي، ومجموعة محدودة من الحالات التي تُشكل "شفرة المصدر" للبرنامج. يُعرَّف إنتاج أكبر قدر من المخرجات بكتابة أكبر عدد من الآحاد على الشريط، ويُشار إليه أيضًا بتحقيق أعلى نتيجة، بينما يُعرَّف التشغيل لأطول مدة زمنية باتخاذ أكبر عدد من الخطوات للتوقف. ^{[ 4 ]} تتلخص لعبة القندس المشغول ذات n حالة في إيجاد آلة تورينج التي تعمل لأطول مدة أو تحقق أعلى نتيجة، والتي تحتوي على n حالة وتتوقف في النهاية. ^{[ 2 ]} يُفترض أن تبدأ هذه الآلات بشريط فارغ، وأن الشريط يحتوي فقط على أصفار وواحدات ( آلة تورينج ثنائية ). ^{[ 2 ]} الهدف من اللعبة هو برمجة مجموعة من الانتقالات بين الحالات بهدف تحقيق أعلى نتيجة أو أطول مدة تشغيل، مع ضمان توقف الآلة في النهاية.

يُعدّ تحديد زمن التشغيل أو النتيجة للقندس المشغول رقم n عمليةً غير قابلة للحساب . ^{[ 4 ]} في الواقع، تصبح كلٌّ من الدالتين Σ(n) و S(n) في نهاية المطاف أكبر من أي دالة قابلة للحساب . ^{[ 4 ]} ولهذا الأمر آثارٌ في نظرية قابلية الحساب ، ومسألة التوقف ، ونظرية التعقيد . ^{[ 5 ]} وقد طُرح مفهوم القندس المشغول لأول مرة من قِبل تيبور رادو في بحثه المنشور عام 1962 بعنوان "حول الدوال غير القابلة للحساب". ^{[ 4 ]}

من نتائج لعبة القندس المشغول أنه إذا أمكن حساب الدالتين Σ(n) و S(n) لجميع قيم n ، فإن ذلك سيحل جميع التخمينات الرياضية التي يمكن اختزالها إلى مسألة توقف، مثلاً، إلى صيغة "هل تتوقف آلة تورينغ هذه ؟ ". ^{[ 6 ]} على سبيل المثال، توجد آلة تورينغ ذات 27 حالة تتحقق من تخمين غولدباخ لكل عدد وتتوقف عند مثال مضاد؛ إذا لم تتوقف هذه الآلة بعد تشغيلها لـ S(27) خطوة، فلا بد أنها ستعمل إلى الأبد، مما يحل التخمين. ^{[ 6 ]}^{[ 7 ]} يمكن التعبير عن العديد من المشكلات الأخرى، بما في ذلك فرضية ريمان (744 حالة) واتساق نظرية مجموعات ZF (745 حالة ^{[ 8 ]}^{[ 9 ]} )، بصيغة مماثلة، حيث يلزم التحقق من عدد لا نهائي قابل للعد من الحالات على الأكثر. ^{[ 6 ]}

التعريف التقني

تتضمن لعبة القندس المشغول ذات الحالة n (أو لعبة BB- n )، التي تم تقديمها في ورقة تيبور رادو عام 1962، فئة من آلات تورينج ، حيث يُطلب من كل عضو فيها تلبية مواصفات التصميم التالية:

تحتوي الآلة على n حالة تشغيلية بالإضافة إلى حالة توقف، حيث n عدد صحيح موجب، وتُحدد إحدى هذه الحالات n كحالة بداية . (عادةً ما تُرقّم الحالات من 1 إلى n، مع اعتبار الحالة 1 حالة البداية، أو من A إلى B ، مع اعتبار الحالة A حالة البداية).
تستخدم الآلة شريطًا واحدًا ثنائي الاتجاه لا نهائي (أو غير محدود).
الأبجدية الشريطية هي {0، 1}، حيث يمثل الرقم 0 رمز الفراغ.
تأخذ دالة الانتقال الخاصة بالآلة مدخلين:
- الوضع الحالي غير المتوقف،
- الرمز الموجود في خلية الشريط الحالية،
وينتج ثلاثة مخرجات:
- رمز للكتابة فوق الرمز الموجود في خلية الشريط الحالية (قد يكون نفس الرمز الذي تمت الكتابة فوقه)،
- اتجاه للتحرك (يسارًا أو يمينًا؛ أي الانتقال إلى خلية الشريط بمقدار موضع واحد إلى يسار أو يمين الخلية الحالية)، و
- حالة للانتقال إليها (والتي قد تكون حالة التوقف).

يتألف تشغيل الآلة من البدء في حالة البداية، حيث تكون خلية الشريط الحالية أي خلية من شريط فارغ (جميعها أصفار)، ثم تكرار دالة الانتقال حتى الوصول إلى حالة التوقف (إن وُجدت). إذا توقفت الآلة في النهاية، يُطلق على عدد الآحاد المتبقية على الشريط اسم " نتيجة الآلة" . آلة " القندس المشغول" من الرتبة n ، أو BB- n أو ببساطة "القندس المشغول"، هي آلة تورينغ تفوز في لعبة "القندس المشغول" ذات n حالة. ^{[ 6 ]} وبحسب التعريف، إما أن تحقق أعلى نتيجة (يرمز لها بـ Σ(n) ^{[ 4 ]} )، أو تعمل لأطول مدة ( S(n) )، من بين جميع آلات تورينغ المنافسة الأخرى ذات n حالة.

مثال

قد تكون قواعد آلة تورينج أحادية الحالة كالتالي:

في الحالة 1، إذا كان الرمز الحالي هو 0، فاكتب 1، وانتقل مسافة واحدة إلى اليمين، ثم انتقل إلى الحالة 1
في الحالة 1، إذا كان الرمز الحالي هو 1، فاكتب 0، وانتقل مسافة واحدة إلى اليمين، ثم انتقل إلى وضع التوقف (HALT).

ستتحرك آلة تورينج هذه إلى اليمين، مُبدِّلةً قيمة جميع البتات التي تمر بها. وبما أن الشريط الابتدائي يحتوي على أصفار فقط، فإنها ستُشكِّل سلسلة لا نهائية من الآحاد. ولن تكون هذه الآلة منافسةً لآلة "القندس المشغول" لأنها تعمل إلى الأبد على شريط فارغ.

الوظائف

في ورقته البحثية الأصلية عام 1962، عرّف رادو دالتين مرتبطتين بلعبة القندس المشغول: دالة النقاط Σ(n) ودالة التحولات S(n). ^{[ 4 ]} تأخذ كلتا الدالتين عددًا من حالات آلة تورينج. $n$ وتُخرج الدالة Σ(n) أعلى درجة يمكن أن تحققها آلة تورينج ذات هذا العدد من الحالات وفقًا لمقياس معين. تعطي دالة الدرجة Σ(n) الحد الأقصى لعدد الآحاد. $n$ يمكن لآلة تورينج ذات n حالة أن تُخرج بيانات قبل التوقف، بينما تُعطي دالة الإزاحات S(n) الحد الأقصى لعدد الإزاحات (أو الخطوات المكافئة، لأن كل خطوة تتضمن إزاحة) التي يمكن لآلة تورينج ذات n حالة أن تُخرجها. $n$ يمكن لآلة تورينج ذات n حالة أن تخضع لعملية ما قبل التوقف. ^{[ 4 ]} أثبت أن كلتا الدالتين غير قابلتين للحساب ، لأنهما تنموان أسرع من أي دالة قابلة للحساب. ^{[ 4 ]} تم تعريف الدالة BB(n) على أنها إحدى هاتين الدالتين، لذلك لن يتم استخدام هذا الترميز في هذه المقالة.

يمكن تعريف عدد من الدوال غير القابلة للحساب الأخرى بناءً على قياس أداء آلات تورينج بطرق أخرى غير الوقت أو الحد الأقصى لعدد الآحاد. ^{[ 10 ]} على سبيل المثال: ^{[ 10 ]}

الوظيفة ${\text{num}}(n)$ يُعرَّف هذا بأنه الحد الأقصى لعدد الآحاد المتتالية التي يمكن لآلة تورينغ ذات التوقف كتابتها على شريط فارغ. بعبارة أخرى، هو أكبر عدد أحادي يمكن لآلة تورينغ ذات n حالة كتابته على شريط.
الوظيفة ${\text{space}}(n)$ يُعرَّف هذا بأنه الحد الأقصى لعدد مربعات الشريط التي يمكن لآلة تورينغ المتوقفة قراءتها (أي زيارتها) قبل التوقف. يشمل هذا مربع البداية، ولكنه لا يشمل المربع الذي تصل إليه الآلة فقط بعد انتقال التوقف (إذا كان انتقال التوقف مُعلَّمًا باتجاه حركة)، لأن هذا المربع لا يؤثر على سلوك الآلة. هذا هو الحد الأقصى لتعقيد المساحة لآلة تورينغ ذات n حالة.

تشكل هذه الوظائف الأربع مجتمعة العلاقة ${\text{num}}(n)\leq \Sigma (n)\leq {\text{space}}(n)\leq S(n)$ [ ^{10 ]} يمكن أيضًا تعريف المزيد من الوظائف عن طريق تشغيل اللعبة على أجهزة حاسوب مختلفة، مثل آلات تورينج ذات الرموز الثلاثة، ^{[ 11 ]} وآلات تورينج غير الحتمية، ^{[ 12 ]} وحساب لامدا ( المتتالية A333479 في OEIS ) ^، أو حتى لغات برمجة عشوائية. ^{[ 11 ]}

دالة النتيجة Σ

تُحدد دالة التقييم الحد الأقصى للتقييم الذي يمكن أن يحققه قندس مشغول على مقياس معين. هذه دالة غير قابلة للحساب ، لأنها تنمو بشكل أسرع تقاربياً من أي دالة قابلة للحساب. ^{[ 13 ]}

دالة التقييم، ${\displaystyle \Sigma$ , معرف بحيث $\Sigma (n)$ هي أعلى نتيجة يمكن تحقيقها (أكبر عدد من الرقم 1 في النهاية على الشريط) بين جميع رموز التوقف المكونة من 2 $n$ آلات تورينج ذات الحالة - من النوع الموصوف أعلاه، عند بدء تشغيلها على شريط فارغ.

من الواضح أن $\Sigma$ هي دالة محددة جيدًا: لكل قيمة n ، يوجد على الأكثر عدد محدود من آلات تورينج ذات n حالة كما هو موضح أعلاه، حتى التماثل، وبالتالي يوجد على الأكثر عدد محدود من أوقات التشغيل الممكنة. ^{[ 4 ]}^{ص 880}

وفقًا للتعريف القائم على النقاط، تُسمى أي آلة تورينغ M ذات n حالة ورمزين، والتي تحقق $σ$ $($ $M$ $) = Σ($ $n$ $) (أي التي تحقق أعلى نتيجة)، بـ"القندس المشغول". لكل قيمة$ n ، يوجد على الأقل 4( n - 1)! من القنادس المشغولة ذات n حالة. (بالنظر إلى أي قندس مشغول ذي n حالة، يمكن الحصول على قندس آخر بمجرد تغيير اتجاه الإزاحة في انتقال التوقف، وثالث بعكس جميع اتجاهات الإزاحة بشكل موحد، ورابع بعكس اتجاه التوقف للقندس المشغول ذي جميع اتجاهات الإزاحة. علاوة على ذلك، ينتج عن تبديل جميع الحالات باستثناء حالتي البدء والتوقف آلة تحقق نفس النتيجة. نظريًا، يمكن أن يكون هناك أكثر من نوع واحد من الانتقالات التي تؤدي إلى حالة التوقف، ولكن عمليًا سيكون ذلك مُهدرًا للموارد، لأنه لا يوجد سوى تسلسل واحد من انتقالات الحالة ينتج النتيجة المطلوبة).

عدم قابلية الحساب

أثبتت ورقة رادو البحثية لعام 1962 أنه إذا $f:\mathbb {N} \to \mathbb {N}$ إذا كانت أي دالة قابلة للحساب ، فإن Σ( n ) > f ( n ) لجميع قيم n الكبيرة بما فيه الكفاية ، وبالتالي فإن Σ ليست دالة قابلة للحساب. ^{[ 4 ]}

علاوة على ذلك، يعني هذا أنه لا يمكن تحديد ما إذا كانت آلة تورينغ عشوائية هي "قندس مشغول" باستخدام خوارزمية عامة . (لا يمكن أن توجد مثل هذه الخوارزمية، لأن وجودها سيسمح بحساب Σ، وهو أمرٌ مُثبت استحالته. على وجه الخصوص، يمكن استخدام مثل هذه الخوارزمية لإنشاء خوارزمية أخرى تحسب Σ على النحو التالي: لأي قيمة معطاة لـ n ، يتم اختبار كل آلة من آلات تورينغ ذات n حالة ورمزين حتى يتم العثور على "قندس مشغول" ذي n حالة؛ ثم تتم محاكاة آلة "القندس المشغول" هذه لتحديد نتيجتها، وهي بحكم التعريف Σ( n )).

على الرغم من أن Σ( n ) دالة غير قابلة للحساب، إلا أن هناك بعض القيم الصغيرة لـ n التي يمكن عندها الحصول على قيمها وإثبات صحتها. ليس من الصعب إثبات أن Σ(0) = 0، Σ(1) = 1، Σ(2) = 4، وبصعوبة متزايدة يمكن إثبات أن Σ(3) = 6، Σ(4) = 13، وΣ(5) = 4098 (المتتالية A028444 في OEIS ) . لم يتم تحديد قيمة Σ( n ) بعد لأي قيمة لـ n أكبر من 5، على الرغم من تحديد حدود دنيا لها (انظر قسم القيم المعروفة أدناه).

تعقيد وعدم إمكانية إثبات Σ

يُعرَّف أحد أشكال تعقيد كولموغوروف كما يلي: ^{[ 14 ]} تعقيد العدد n هو أصغر عدد من الحالات اللازمة لآلة تورينغ من فئة BB تتوقف عند كتلة واحدة من n من الآحاد المتتالية على شريط فارغ مبدئيًا. ينص الشكل المقابل لنظرية عدم اكتمال تشايتين على أنه، في سياق نظام بديهي معين للأعداد الطبيعية ، يوجد عدد k بحيث لا يمكن إثبات أن أي عدد محدد له تعقيد أكبر من k ، وبالتالي لا يمكن إثبات حد أعلى محدد لـ Σ( k ) (وذلك لأنه سيتم إثبات أن "تعقيد n أكبر من k " إذا تم إثبات أن $n$ $> Σ($ $k$ $)$ ). كما ذُكر في المرجع المذكور، بالنسبة لأي نظام بديهي من "الرياضيات العادية"، فإن أصغر قيمة k التي يتحقق عندها هذا الأمر أقل بكثير من 10⇈10 ؛ وبالتالي، في سياق الرياضيات العادية، لا يمكن إثبات قيمة Σ(10⇈10) ولا أي حد أعلى لها. ( تتضح نظرية عدم الاكتمال الأولى لغودل من خلال هذه النتيجة: في نظام بديهي للرياضيات العادية، توجد جملة صحيحة ولكن غير قابلة للإثبات على شكل $Σ(10⇈10) =$ $n$ ، وهناك عدد لا نهائي من الجمل الصحيحة ولكن غير القابلة للإثبات على شكل $Σ(10⇈10) <$ $n$ .)

وظيفة التحويلات القصوى S

بالإضافة إلى الدالة Σ، قدم رادو [1962] دالة قصوى أخرى لآلات تورينج، وهي دالة الإزاحات القصوى ، S ، المعرفة على النحو التالي: ^{[ 4 ]}

$s (M)$ = عدد التحولات التي يقوم بها M قبل التوقف، لأي $M \in E n$ ،
$S (n) = max{s (M) | M \in E n}$ = أكبر عدد من التحولات التي تقوم بها أي آلة تورينج ذات n حالة ورمزين متوقفة.

لأن آلات تورينج العادية تتطلب وجود إزاحة في كل انتقال أو "خطوة" (بما في ذلك أي انتقال إلى حالة التوقف)، فإن دالة max-shifts هي في نفس الوقت دالة max-steps.

أثبت رادو أن S غير قابلة للحساب لنفس السبب الذي يجعل Σ غير قابلة للحساب - أي أنها تنمو أسرع من أي دالة قابلة للحساب. وقد برهن على ذلك ببساطة من خلال ملاحظة أنه لكل n ، فإن S ( n ) ≥ Σ( n ). يمكن لكل إزاحة أن تكتب 0 أو 1 على الشريط، بينما تحسب Σ مجموعة فرعية من الإزاحات التي كتبت 1، وهي تلك التي لم تُستبدل بالكتابة حتى توقف آلة تورينج؛ وبالتالي، تنمو S على الأقل بنفس سرعة Σ، والتي سبق أن ثبت أنها تنمو أسرع من أي دالة قابلة للحساب. ^{[ 4 ]}

استخدم لين ورادو ( دراسات حاسوبية لمسائل آلة تورينج ، 1965) العلاقة التالية بين Σ و S لإثبات أن Σ(3) = 6 وأن S(3) = 21: بالنسبة لقيمة n معينة ، إذا كانت S ( n ) معلومة، فإنه يمكن (من حيث المبدأ) تشغيل جميع آلات تورينج ذات n حالة لما يصل إلى S ( n ) خطوة، وعند هذه النقطة، لن تتوقف أي آلة لم تتوقف بعد. عند هذه النقطة، من خلال ملاحظة أي الآلات توقفت مع وجود أكبر عدد من الآحاد على الشريط (أي، آلات القندس المشغولة)، يمكن الحصول من أشرطتها على قيمة Σ( n ). كان النهج الذي استخدمه لين ورادو في حالة n = 3 هو التخمين بأن S (3) = 21 (بعد تخمين فاشل بقيمة 18)، ثم محاكاة جميع الآلات ذات 3 حالات المختلفة جوهريًا (82944 آلة، تساوي 2 ^× 10³⁴ ⁾ لما يصل إلى 21 خطوة. وجدوا 26073 آلة توقفت، من بينها آلة توقفت بعد 21 خطوة فقط. وبتحليل سلوك الآلات التي لم تتوقف خلال 21 خطوة، نجحوا في إثبات أن أياً من هذه الآلات لن تتوقف أبداً، إذ أن معظمها يتبع نمطاً معيناً. وقد أثبت هذا صحة الفرضية القائلة بأن S (3) = 21، كما حدد أن Σ(3) = 6، وهي القيمة التي تحققت في عدة آلات، حيث توقفت جميعها بعد 11 إلى 14 خطوة. ^[¹⁵^]

في عام 2016، حصل آدم يديديا وسكوت آرونسون على أول حدٍّ أعلى (صريح) للحد الأدنى لقيمة n التي يكون عندها S( n ) غير قابل للإثبات في نظرية زيرميلو-فرانكل . ولتحقيق ذلك، قاما ببناء آلة تورينغ ذات 7910 حالة ^{[ 16 ]} لا يمكن إثبات سلوكها استنادًا إلى البديهيات المعتادة لنظرية المجموعات ( نظرية زيرميلو-فرانكل مع بديهية الاختيار )، في ظل فرضيات اتساق معقولة (خاصية رامزي الثابتة، المكافئة لوجود أعداد أساسية دقيقة كبيرة بشكل تعسفي ). ^{[ 17 ]}^{[ 18 ]}^{[ 19 ]} ثم قام ستيفان أورير بتقليصها إلى 1919 حالة، مع إزالة الاعتماد على خاصية رامزي الثابتة، ^{[ 20 ]}^{[ 21 ]} ولاحقًا إلى 748 حالة. ^{[ 5 ]} وفي يوليو 2023، قام ريبيل بتقليصها إلى 745 حالة. ^{[ 8 ]}^{[ 9 ]} تم الإبلاغ عن المزيد من التحسينات على موقع BB Challenge الإلكتروني .

برهان على عدم قابلية حساب S ( n ) و Σ( n )

لنفترض أن S ( n ) دالة قابلة للحساب، ولنرمز بـ EvalS إلى آلة تورينغ تُقيّم S ( n ). عند إدخال شريط يحتوي على n من الآحاد، ستنتج S ( n ) من الآحاد على الشريط ثم تتوقف. ولنرمز بـ Clean إلى آلة تورينغ تُنظف سلسلة الآحاد المكتوبة مبدئيًا على الشريط. ولنرمز بـ Double إلى آلة تورينغ تُقيّم الدالة n + n . عند إدخال شريط يحتوي على n من الآحاد، ستنتج 2n من الآحاد على الشريط ثم تتوقف. لنُنشئ التركيب Double | EvalS | Clean ، ولنرمز بـ _n₀إلى عدد حالات هذه الآلة. ولنرمز _بـ Create_n₀ إلى آلة تورينغ تُنشئ n₀ _من الآحاد على شريط فارغ مبدئيًا. يمكن بناء هذه الآلة بطريقة بسيطة لتضم n₀ حالة (الحالة i تكتب _{1 ،}_{ثم تُحرك الرأس}_إلى اليمين وتنتقل إلى الحالة i + 1، باستثناء الحالة n₀ التي تتوقف). ولنرمز بـ N إلى المجموع n₀ + n₀ _.

لنفترض أن BadS يرمز إلى التركيب Create_n ₀ | Double | EvalS | Clean . لاحظ أن هذه الآلة لها N حالة. تبدأ بشريط فارغ، فتقوم أولاً بإنشاء سلسلة من n ₀ 1، ثم تضاعفها، منتجةً سلسلة من N 1. بعد ذلك، ستنتج EvalS سلسلة من S ( N ) 1 على الشريط، وفي النهاية ستمسح جميع الـ 1 ثم تتوقف. لكن مرحلة التنظيف ستستمر لـ S ( N ) خطوة على الأقل، لذا فإن زمن عمل BadS أكبر من S ( N )، وهو ما يتناقض مع تعريف الدالة S ( n ).

يمكن إثبات عدم قابلية حساب Σ( n ) بطريقة مماثلة. في البرهان المذكور أعلاه، يجب استبدال الآلة EvalS بالآلة EvalΣ، والآلة Clean بالآلة Increment - وهي آلة تورينج بسيطة تبحث عن أول صفر على الشريط وتستبدله بواحد.

يمكن إثبات عدم قابلية حساب S ( n ) بالرجوع إلى مسألة توقف الشريط الفارغ. تتمثل مسألة توقف الشريط الفارغ في تحديد ما إذا كانت آلة تورينغ ستتوقف عند بدء تشغيلها على شريط فارغ أم لا. تُكافئ مسألة توقف الشريط الفارغ مسألة التوقف القياسية ، وبالتالي فهي غير قابلة للحساب أيضًا. لو كانت S ( n ) قابلة للحساب، لأمكننا حل مسألة توقف الشريط الفارغ ببساطة عن طريق تشغيل أي آلة تورينغ ذات n حالة لعدد S ( n ) من الخطوات؛ فإذا لم تتوقف الآلة بعد، فلن تتوقف أبدًا. لذا، بما أن مسألة توقف الشريط الفارغ غير قابلة للحساب، فإن S ( n ) يجب أن تكون غير قابلة للحساب أيضًا.

عدم قابلية حساب المساحة (ن) والعدد (ن)

كلاهما ${\text{space}}(n)$ و ${\text{num}}(n)$ الدوال غير قابلة للحساب. ^{[ 10 ]} ويمكن إثبات ذلك لـ ${\text{space}}(n)$ بملاحظة أن كل مربع شريط تكتب عليه آلة تورينج الرقم واحد، يجب عليها أيضًا زيارته: بعبارة أخرى، $\Sigma (n)\leq {\text{space}}(n)$ [ ¹⁰^] الـ ${\text{num}}(n)$ يمكن إثبات أن الدالة غير قابلة للحساب عن طريق إثبات، على سبيل المثال، أن ${\text{space}}(n)<{\text{num}}(3n+3)$ يمكن تحقيق ذلك من خلال تصميم آلة تورينج ذات (3n+3) حالة تحاكي بطل الفضاء ذي n حالة، ثم استخدامها لكتابة ما لا يقل عن ${\text{space}}(n)$ ^[¹⁰^]

التعميمات

يمكن تعريف نظائر دالة الإزاحة بسهولة في أي لغة برمجة، شريطة أن تُوصف البرامج بسلاسل بتية، وأن يُحسب عدد خطوات البرنامج. ^{[ 11 ]} على سبيل المثال، يمكن تعميم لعبة القندس المشغول إلى بُعدين باستخدام آلات تورينج على أشرطة ثنائية الأبعاد، أو إلى آلات تورينج التي يُسمح لها بالبقاء في مكانها والتحرك يمينًا ويسارًا. ^{[ 11 ]} بدلاً من ذلك، يمكن تعريف "دالة القندس المشغول" لنماذج حسابية متنوعة بتعقيد كولموغوروف . ^{[ 11 ]} ويتم ذلك بأخذ ${BB}(n)$ أن يكون أكبر عدد صحيح $m$ بحيث $K_{L}(m)\leq n$ ، أين $K_{L}(m)$ هو طول أقصر برنامج في $L$ هذا يُخرج $m$ : ${BB}(n)$ وبالتالي، فإن أكبر عدد صحيح هو برنامج بطول $n$ أو أقل يمكن أن ينتج في $L$ [ ¹¹^]

أطول آلة تشغيل ذات 6 حالات ورمزين، والتي تتميز بخاصية إضافية تتمثل في عكس قيمة الشريط في كل خطوة، تنتج6147 ثانية بعد٤٧٣٣٩٩٧٠ خطوة. لذا ، بالنسبة لفئة آلة تورينج العكسية (RTM)، ^[٢٢]^S^RTM ( ٦ ₎ ≥47339970 و Σ RTM (6 ₎≥6147. وبالمثل، يمكننا تعريف نظير لدالة Σ لآلات التسجيل على أنها أكبر رقم يمكن أن يكون موجودًا في أي سجل عند التوقف، لعدد معين من التعليمات. ^[²³^]

أعداد مختلفة من الرموز

يتمثل أحد التعميمات البسيطة في توسيع نطاق آلات تورينج لتشمل m رمزًا بدلًا من رمزين فقط (0 و1). ^{[ 11 ]} على سبيل المثال، تحتوي آلة تورينج ثلاثية ذات m = 3 رموز على الرموز 0 و1 و2. ويُعرّف التعميم لآلات تورينج ذات n حالة و m رمزًا دوال بيفر المشغولة المعممة التالية :

Σ( n , m ): أكبر عدد من القيم غير الصفرية التي يمكن طباعتها بواسطة آلة ذات n حالة و m رمز، تبدأ على شريط فارغ في البداية قبل أن تتوقف، و
S ( n , m ): أكبر عدد من الخطوات التي تتخذها آلة ذات n حالة و m رمز بدأت على شريط فارغ في البداية قبل التوقف. ^{[ 11 ]}

على سبيل المثال، أطول آلة ذات 3 حالات و3 رموز تم العثور عليها حتى الآن تعمل119 112 334 170 342 540 خطوة قبل التوقف . ^{[ 24 ]}^{[ 25 ]}

آلات تورينج غير الحتمية

أقصى أوقات التوقف والحالات من NDTM ذي الحالة p ، والحالتين، واللونين ^{[ 12 ]}
ص	خطوات	الولايات
1	2	2
2	4	4
3	6	7
4	7	11
5	8	15
6	7	18
7	6	18

يمكن توسيع نطاق هذه المشكلة لتشمل آلات تورينغ غير الحتمية من خلال البحث عن النظام الذي يحتوي على أكبر عدد من الحالات عبر جميع الفروع، أو الفرع الذي يحتوي على أطول عدد من الخطوات. ^{[ 12 ]} يبقى السؤال حول ما إذا كانت آلة تورينغ غير حتمية معينة ستتوقف أم لا مسألةً غير قابلة للاختزال حسابيًا، والحساب المطلوب لإيجاد آلة تورينغ غير حتمية مشغولة أكبر بكثير من الحالة الحتمية، نظرًا لوجود فروع متعددة يجب أخذها في الاعتبار. بالنسبة لنظام ثنائي الحالة وثنائي اللون مع p حالة أو قاعدة، يوضح الجدول على اليمين الحد الأقصى لعدد الخطوات قبل التوقف والحد الأقصى لعدد الحالات الفريدة التي أنشأتها آلة تورينغ غير الحتمية.

التطبيقات

مسائل رياضية مفتوحة

إضافةً إلى طرحها لعبة رياضية بالغة الصعوبة ، تُقدّم دالتا "القندس المشغول" Σ(n) و S ( n ) منهجًا جديدًا تمامًا لحلّ مسائل الرياضيات البحتة. يُمكن نظريًا، ولكن ليس عمليًا، حلّ العديد من المسائل الرياضية المفتوحة بطريقة منهجية بمعرفة قيمة S ( n ) لقيمة n كبيرة بما فيه الكفاية . ^{[ 6 ]}^{[ 26 ]} من الناحية النظرية، تُشفّر قيمة S(n) إجابة جميع التخمينات الرياضية التي يُمكن التحقق منها في وقت لا نهائي بواسطة آلة تورينج ذات n حالة أو أقل . ^{[ 5 ]}

ضع في اعتبارك أي $\Pi _{1}^{0}$ الفرضية : أي فرضية يمكن دحضها من خلال مثال مضاد ضمن عدد محدود من الحالات (مثل فرضية غولدباخ ). اكتب برنامج حاسوب يختبر هذه الفرضية بشكل متسلسل لقيم متزايدة. في حالة فرضية غولدباخ، سننظر في كل عدد زوجي ≥ 4 بشكل متسلسل ونختبر ما إذا كان مجموع عددين أوليين أم لا. لنفترض أن هذا البرنامج يُحاكى على آلة تورينغ ذات n حالة. إذا وجد البرنامج مثالًا مضادًا (عددًا زوجيًا ≥ 4 ليس مجموع عددين أوليين في مثالنا)، فإنه يتوقف ويشير إلى ذلك. مع ذلك، إذا كانت الفرضية صحيحة، فلن يتوقف برنامجنا أبدًا. (يتوقف هذا البرنامج فقط إذا وجد مثالًا مضادًا). ^{[ 5 ]}

الآن، تتم محاكاة هذا البرنامج بواسطة آلة تورينج ذات n حالة، لذا إذا عرفنا S ( n )، يمكننا تحديد (في فترة زمنية محدودة) ما إذا كانت الآلة ستتوقف أم لا بمجرد تشغيلها لعدد محدد من الخطوات. وإذا لم تتوقف الآلة بعد S ( n ) خطوة، فإننا نعلم أنها لن تتوقف أبدًا، وبالتالي لا توجد أمثلة مضادة للفرضية المعطاة (أي لا توجد أعداد زوجية ليست مجموع عددين أوليين). وهذا من شأنه أن يثبت صحة الفرضية. ^{[ 5 ]} وبالتالي ، يمكن نظريًا استخدام قيم محددة (أو حدود عليا) لـ S ( n ) لحل العديد من المسائل المفتوحة في الرياضيات بشكل منهجي. ^{[ 5 ]}

ومع ذلك، تشير النتائج الحالية المتعلقة بمشكلة القندس المشغول إلى أن هذا لن يكون عمليًا لسببين:

من الصعب للغاية إثبات قيم دالة "القندس المشغول" (ودالة "الإزاحة القصوى"). وقد تم إثبات كل قيمة دقيقة معروفة لـ S ( n ) من خلال حصر جميع آلات تورينغ ذات n حالة وإثبات ما إذا كانت كل منها تتوقف أم لا. لذا، يجب حساب S ( n ) بطريقة أقل مباشرة حتى يكون ذلك مفيدًا.
تتضخم قيم S(n) وغيرها من دوال "القندس المشغول" بسرعة كبيرة. فبينما تبلغ قيمة S(5) 47,176,870 فقط، ^{[ 27 ]} فإن قيمة S(6) أكبر من ذلك. $^{^{^{^{9}2}2}}2$ أي، 2 مرفوعة إلى 2 مرفوعة إلى 2 مرفوعة إلى 9، وهو ما يعادل على الأقل 2 مرفوعة إلى 5. ^{[ 28 ]} قيمة S(25)، وهي عدد الخطوات التي يحتاجها البرنامج الحالي لتخمين غولدباخ للوصول إلى إجابة قاطعة، هائلة بشكل لا يُصدق، ومن المستحيل كتابتها، ناهيك عن تشغيل جهاز لحسابها، في الكون المرئي. ^{[ 6 ]}^{[ 7 ]}

اتساق النظريات

من خصائص الدالة S(n) الأخرى أنه لا توجد نظرية سليمة حسابيًا وقابلة للحساب تعتمد على البديهيات يمكنها إثبات جميع قيم الدالة. على وجه التحديد، إذا توفرت نظرية قابلة للحساب وسليمة حسابيًا $T$ هناك عدد $n_{T}$ بحيث يكون ذلك لجميع $n\geq n_{T}$ لا يوجد بيان من هذا النوع $S(n)=k$ يمكن إثبات ذلك في $T$ [ ⁵^] وهذا يعني أنه لكل نظرية قيمة قصوى محددة لـ S(n) يمكنها إثباتها. وهذا صحيح لأنه لكل قيمة من هذه القيم ^. $T$ آلة تورينج مع $n_{T}$ يمكن تصميم الحالات بحيث تسرد كل برهان ممكن في $T$ ^{[ 5 ]} إذا كانت النظرية غير متسقة، فإن جميع العبارات الخاطئة قابلة للإثبات، ويمكن إعطاء آلة تورينج شرط التوقف إذا، وفقط إذا، وجدت برهانًا على سبيل المثال ، $0=1$ [ ⁵^]^أي نظرية تثبت قيمة $S(n_{T})$ يثبت اتساقه الذاتي، مما ينتهك نظرية عدم الاكتمال الثانية لغودل . ^{[ 5 ]} يمكن استخدام هذا لوضع النظريات المختلفة على مقياس، على سبيل المثال البديهيات الأساسية الكبيرة المختلفة في ZFC : إذا كانت كل نظرية $T$ يتم تعيين رقمه $n_{T}$ النظريات ذات القيم الأكبر من $n_{T}$ إثبات اتساق النظريات الأدنى منها، ووضع جميع هذه النظريات على مقياس لا نهائي قابل للعد. ^{[ 5 ]}

أمثلة بارزة

تم بناء آلة تورينج ثنائية مكونة من 745 حالة تتوقف إذا وفقط إذا كانت ZFC غير متسقة. ^{[ 8 ]}^{[ 9 ]}
تم بناء آلة تورينج ذات 744 حالة تتوقف إذا وفقط إذا كانت فرضية ريمان خاطئة. ^{[ 20 ]}^{[ 6 ]}
تم بناء آلة تورينج ذات 43 حالة تتوقف فقط إذا كانت حدسية غولدباخ خاطئة. ثم تم اختزالها إلى آلة ذات 27 حالة، ^{[ 20 ]}^{[ 6 ]} ثم إلى آلة ذات 25 حالة، وتم إثباتها والتحقق منها رسميًا لاحقًا باستخدام لغة إثبات النظريات Lean 4. ^{[ 7 ]}
تم بناء آلة تورينج ذات 15 حالة تتوقف إذا وفقط إذا كانت الفرضية التالية التي صاغها بول إيردوس في عام 1979 خاطئة: لكل n > 8 يوجد على الأقل رقم واحد 2 في التمثيل ذي الأساس 3 للعدد ²ⁿ . ^{[ 29 ]}^{[ 30 ]}
تم اكتشاف آلة تورينج ذات 6 حالات تتوقف فقط في حالة تكرار تطبيق ${\textstyle x_{n+1}=\left\lfloor {\frac {3x_{n}}{2}}\right\rfloor +2}$ بدءًا من 4، ينتج دائمًا ضعف عدد القيم الفردية مقارنة بالقيم الزوجية. وقد سُميت لاحقًا "مضاد الهيدرا". ^[³¹^]

الكنيسة المادية - أطروحة تورينج

تؤثر خصائص نمو دالة "بيفر المشغول" على سلوك الأنظمة الفيزيائية، بافتراض صحة فرضية تشيرش-تورينج الفيزيائية . فإذا كانت هذه الفرضية صحيحة، وكانت جميع الدوال القابلة للحساب الفيزيائي قابلة للحساب بواسطة تورينج، فلن تتمكن أي كمية فيزيائية قابلة للقياس المباشر من النمو أسرع من دالة "بيفر المشغول"، كما لا يمكن لأي دالة قابلة للحساب بواسطة تورينج أن تنمو أسرع منها. ^{[ 32 ]} دوال بسيطة من $BB(n)$ كما سيفرض ذلك حدًا أدنى لمعدلات النمو، بالإضافة إلى حدود عليا ودنيا لمعدلات التقارب. ^{[ 33 ]}^{[ 32 ]}

النتائج المعروفة

الحدود الدنيا

الآلات الخضراء

في عام 1964، طوّر ميلتون غرين حدًا أدنى لمتغير عدّ الآحاد لدالة "القندس المشغول"، ونُشر هذا الحد في وقائع ندوة معهد مهندسي الكهرباء والإلكترونيات (IEEE) لعام 1964 حول نظرية دوائر التبديل والتصميم المنطقي. وصفه هاينر ماركسن ويورغن بونتروك بأنه "حد أدنى غير تافه (ليس بدائيًا تكراريًا)". ^{[ 34 ]} يمكن حساب هذا الحد الأدنى، ولكنه معقد للغاية بحيث لا يمكن التعبير عنه بتعبير واحد بدلالة n . ^{[ 35 ]} وقد تم ذلك باستخدام مجموعة من آلات تورينغ، حيث أثبتت كل منها الحد الأدنى لقيمة معينة من $n$ . ^{[ 35 ]} عندما $n = 8،$ تُعطي الطريقة

$\Sigma (8)\geq 3\times (7\times 3^{92}-1)/2\approx 8.248\times 10^{44}.$

في المقابل، فإن أفضل حد أدنى حالي (حتى عام 2026) على $\Sigma (6)$ يكون $2\uparrow \uparrow \uparrow 5$ ، حيث $\uparrow$ يمثل الرمز ' s رمز السهم لأعلى عند كنوت . ^{[ 36 ]} وهذا يمثل $2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 4$ قيمة $\Sigma (8)$ ربما يكون أكبر من ذلك بكثير.

تم إثبات الحد الأدنى لغرين من خلال بناء متكرر لسلسلة من آلات تورينغ، كل منها مكونة من آلة أصغر ذات حالتين إضافيتين تُطبقان الآلة الأصغر بشكل متكرر على شريط الإدخال. ^{[ 35 ]} تحديد قيمة ⁠ $N$ -منافس نشيط للغاية على شريط يحتوي على $m$ أولئك الذين سيصبحون $B_{N}(m)$ (الناتج النهائي لكل آلة هو قيمتها على $m=0$ (لأن الشريط الفارغ يحتوي على 0 من الواحدات)، فإن علاقات التكرار هي كما يلي: ^{[ 35 ]} ${\begin{aligned}B_{N}(0)&=1,\\B_{1}(m)&=m+1,\\B_{N}(m)&=1+B_{N-2}(1+B_{N}(m-1)).\end{aligned}}$ يؤدي هذا إلى صيغتين لحساب الحد الأدنى $G(N)$ مقدم من $N$ الآلة رقم 1 : ${\begin{aligned}G(N)&=B_{N-2}(B_{N-2}(1)){\text{ for odd }}N,{\text{ and}}\\G(N)&=1+B_{N-3}(1+B_{N-3}(1)){\text{ for even }}N.\end{aligned}}$

الحد الأدنى لغرين $G(N)$ ويمكن ربطها أيضًا بدالة أكرمان . على وجه الخصوص، $A(N,N)<G(4N+3)<A(2N+1,4)$ لجميع الأعداد الصحيحة الموجبة $N$ [ ³⁷ ]

العلاقات بين وظائف القندس المشغول

من البديهي أن $S (n) \geq Σ(n)$ لأن الآلة التي تكتب $Σ(n)$ من الآحاد يجب أن تستغرق على الأقل $Σ(n)$ من الخطوات للقيام بذلك. ^{[ 37 ]} من الممكن إعطاء عدد من الحدود العليا للوقت $S (n)$ مع عدد الآحاد $Σ(n)$ :

$S(n)\leq (n+1)\times \Sigma (5n)\times 2^{\Sigma (5n)}$ (رادو ^{[ 37 ]} )
$S(n)\leq \Sigma (9n)$ (بورو ^{[ 37 ]} )
$S(n)\leq (2n-1)\times \Sigma (3n+3)$ (بن عمرام وجولستروم وزويك ^{[ 37 ]} )

من خلال تعريف $num(n)$ على أنه الحد الأقصى لعدد الآحاد التي يُسمح لآلة تورينج ذات $n$ حالة بإخراجها بشكل متجاور، بدلاً من أي موضع (أكبر عدد أحادي يمكنها إخراجه)، فمن الممكن إثبات ذلك ^{[ 37 ]}^{[ 10 ]}

${\begin{aligned}\operatorname {num} (n)&<\Sigma (n)\\S(n)&<\operatorname {num} (n+o(n))\\S(n)&<\operatorname {num} (3n+6)\end{aligned}}$

كما قدم بن عمرام وبيترسن، 2002، حدًا محسّنًا تقاربيًا على $S (n)$ . يوجد ثابت $c$ بحيث أنه لجميع $n \geq 2$ ، ^{[ 37 ]}

$S(n)\leq \Sigma \left(n+\left\lceil {\frac {8n}{\log _{2}n}}\right\rceil +c\right).$

القيم الدقيقة والحدود الدنيا والعليا

يُبين الجدول التالي القيم الدقيقة وبعض الحدود الدنيا المعروفة لـ S ( n ) و Σ( n ) والعديد من دوال بيفر المشغولة الأخرى. في هذا الجدول، تُستخدم آلات تورينج ذات الرمزين. القيم المُشار إليها بعلامة استفهام (؟) لا تقل عن حجم القيم الأخرى على يسارها (لأن جميع آلات الحالة n هي أيضًا آلات حالة (n+1))، ولا تزيد عن القيم التي تعلوها (لأن S(n) ≥ space(n) ≥ Σ(n) ≥ num(n)). لذا، من المعروف أن space(6) أكبر من 2. $\uparrow \uparrow \uparrow$ 5، كمساحة(ن) ≥ Σ(ن) و Σ(6) > 2 $\uparrow \uparrow \uparrow$ 5.يمثل الرقم 47176870 حدًا أعلى للفضاء (5)، لأن S(5) =47176870 ( ^{[ 3 ]} ) و S(n) ≥ space(n). 4098 هو حد أعلى لـ num(5)، لأن Σ(5) = 4098 و Σ(n) ≥ num(n). آخر عنصر مُدرج بعلامة استفهام هو num(6)، لأن Σ(6) > 2 $\uparrow \uparrow \uparrow$ 5، لكن Σ(n) ≥ num(n)، نفس الشيء بالنسبة للرقم(7).

قيم دوال القندس المشغول
وظيفة	2-ولاية	3-ولاية	أربع ولايات	خمس ولايات	ست ولايات	سبع ولايات
S(n)	6 ^{[ 5 ]}	21 ^{[ 5 ]}	107 ^{[ 5 ]}	47 176 870 ^{[ 3 ]}^{[ 38 ]}	> 2 $\uparrow \uparrow \uparrow$ 5 ^{[ 36 ]}	> 2 $\uparrow ^{11}$ 2 $\uparrow ^{11}$ 3 ^{[ 36 ]}
المسافة (ن)	4 ^{[ 37 ]}	7 ^{[ 37 ]}	16 ^{[ 37 ]}	12289 ^{[ 38 ]}	> 2 $\uparrow \uparrow \uparrow$ 5 space(n) ≥ Σ(n)	> 2 $\uparrow ^{11}$ 2 $\uparrow ^{11}$ 3 ^{[ 36 ]}
Σ(n)	4 ^{[ 37 ]}	6 ^{[ 37 ]}	13 ^{[ 37 ]}	4098 ^{[ 38 ]}^{[ 36 ]}	> 2 $\uparrow \uparrow \uparrow$ 5 ^{[ 36 ]}	> 2 $\uparrow ^{11}$ 2 $\uparrow ^{11}$ 3 ^{[ 36 ]}
num(n)	4 ^{[ 37 ]}	6 ^{[ 37 ]}	12 ^{[ 37 ]}	165 ^{[ 39 ]}	؟	؟

تم اكتشاف القندس المشغول ذو الخمس حالات بواسطة هاينر ماركسن ويورغن بونتروك في عام 1989، ولكن لم يثبت أنه القندس المشغول الخامس الفائز إلا في عام 2024 بواسطة مجموعة رياضية هواة على الإنترنت، باستخدام برهان تم صياغته في روك . ^{[ 40 ]}^{[ 41 ]}

قائمة القنادس المشغولة

هذه جداول قواعد لآلات تورينج التي تولد Σ(1) و S (1)، و Σ(2) و S (2)، و Σ(3) (ولكن ليس S (3))، و Σ(4) و S (4)، و Σ(5) و S (5)، وأفضل حد أدنى معروف لـ Σ(6) و S (6).

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

تبدأ كل آلة في الحالة A بشريط لا نهائي يحتوي على جميع الأصفار. وبالتالي، فإن الرمز الأولي المقروء من الشريط هو 0.

مفتاح النتيجة: (يبدأ من الموضع الذي يعلوه خط ، ويتوقف عند الموضع الذي تحته خط )

قندس مشغول ذو حالة واحدة ورمزين
	أ
0	1R H
1	(غير مستخدم)

النتيجة: 0 0 1 0 0 (خطوة واحدة، مجموع "1" واحد)

قندس مشغول ذو حالتين ورمزين
	أ	ب
0	1R B	1 لتر أ
1	1 لتر ب	1R H

النتيجة: 0 0 1 1 1 1 0 0 (6 خطوات، أربعة "1" إجمالاً)

قندس مشغول بثلاث حالات ورمزين ^{[ 42 ]}^{[ 15 ]}
	أ	ب	ج
0	1R B	0R C	1 لتر ج
1	1R H	1R B	1 لتر أ

النتيجة: 0 0 1 1 1 1 1 1 0 0 (14 خطوة، ستة "1" إجمالاً).

هذه إحدى الآلات غير المتكافئة العديدة التي تعطي ستة أرقام 1. على عكس الآلات السابقة، فإن هذه الآلة تعمل بكفاءة عالية مع Σ، ولكن ليس مع S. ( S (3) = 21، وتحصل الآلة على خمسة أرقام 1 فقط. ^{[ 15 ]} )

قندس مشغول ذو 4 ولايات ورمزين
	أ	ب	ج	د
0	1R B	1 لتر أ	1R H	1R D
1	1 لتر ب	0 لتر سي	1 لتر دي	أو أ

النتيجة: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 خطوات، 13 "1" إجمالاً)

قندس مشغول ذو 5 ولايات ورمزين
	أ	ب	ج	د	هـ
0	1R B	1R C	1R D	1 لتر أ	1R H
1	1 لتر ج	1R B	0L E	1 لتر دي	0 لتر أ

النتيجة: 4098 "1" مع 8191 "0" متداخلة في 47,176,870 خطوة.

لاحظ في الصورة على اليمين كيف أن هذا الحل مشابه نوعياً لتطور بعض الأوتوماتا الخلوية .

أفضل منافس حالي مكون من 6 حالات ورمزين ^{[ 36 ]}
	أ	ب	ج	د	هـ	F
0	1R B	1R C	1 لتر دي	1R A	0 لتر دي	1R A
1	1R A	1R H	0R F	0L E	1R C	0R E

النتيجة: أكثر من 2↑↑↑5 "1" في أكثر من 2↑↑↑5 خطوات، حيث 2↑↑↑5 = 2↑↑2↑↑2↑↑2↑↑2 و ↑↑ يمثل التكرار .

التصورات

في الجدول التالي، تُمثَّل قواعد كل قندس مشغول (لتحقيق أقصى قيمة لـ Σ) بصريًا، حيث تُشير المربعات البرتقالية إلى الرقم "1" على الشريط، بينما تُشير المربعات البيضاء إلى الرقم "0". ويُشار إلى موضع الرأس بالشكل البيضاوي الأسود، بينما يُمثل اتجاه الرأس الحالة. تُرتَّب الأشرطة الفردية أفقيًا، مع تقدم الوقت من الأعلى إلى الأسفل. وتُمثَّل حالة التوقف بقاعدة تُطابق حالةً مع نفسها (لا يتحرك الرأس).

تطور القنادس المشغولة ذات 1-4 حالات

قواعد العمل في ولاية واحدة

قواعد العمل في ولايتين

قواعد العمل في ثلاث ولايات

قواعد العمل في أربع ولايات

تطور خوارزمية "بيفر المشغول" ذات الحالة الواحدة حتى التوقف. تؤدي الحالة الأولية إلى التوقف، حيث يتم كتابة الرقم "1" مرة واحدة قبل الإنهاء.

تطور القندس النشيط ذي الحالتين حتى التوقف

تطور القندس النشيط ذي الثلاث ولايات حتى توقفه

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

انظر أيضاً

ملحوظات

1 2 "قصة # مخططات الزمكان" . تحدي بيزي بيفر . تم الاسترجاع في 9 يوليو 2024 .
1 2 3 4 5 وايسشتاين، إريك دبليو. "بيفر المشغول" . وولفرام ماث وورلد . مؤرشف من الأصل في 7 ديسمبر 2023. تم الاسترجاع في 21 نوفمبر 2023 .
1 2 3 بروبيكر، بن (2 يوليو 2024). "علماء رياضيات هواة يكتشفون آلة تورينج الخامسة "النشيطة"" . مجلة كوانتا . تم الاطلاع عليه في 3 يوليو 2024 .
1 2 3 4 5 6 7 8 9 10 11 12 رادو، تيبور (مايو 1962). "حول الدوال غير القابلة للحساب" (ملف PDF) . مجلة بيل سيستم التقنية . 41 (3): 877-884 . doi : 10.1002/j.1538-7305.1962.tb00480.x . مؤرشف (ملف PDF) من الأصل في 12 أكتوبر 2021. تم الاطلاع عليه في 7 يوليو 2022 .
١ ٢ ٣ ٤ ٥ ٦ ٧ ٨ ٩ ١٠ ١١ ١٢ ١٣ ١٤ آرونسون، سكوت (٢٩ سبتمبر ٢٠٢٠). "حدود بيفر المشغولة" (ملف PDF) . أخبار SIGACT . ٥١ (٣): ٣٢-٥٤ . doi : 10.1145/3427361.3427369 . ISSN 0163-5700 . مؤرشف من الأصل (ملف PDF) في ٥ يوليو ٢٠٢٢.
1 2 3 4 5 6 7 8 بافلوس، جون (10 ديسمبر 2020). "كيف تُسلط أبطأ برامج الحاسوب الضوء على الحدود الأساسية للرياضيات" . مجلة كوانتا . مؤرشف من الأصل في 10 ديسمبر 2020. تم الاطلاع عليه في 11 ديسمبر 2020 .
1 2 3 لينغ، ييجون. "مستودع جيثب 'goldbach_tm27'" . GitHub .
1 2 3 آرونسون، سكوت (5 يوليو 2023). "الحياة، والتدوين، ووظيفة بيزي بيفر تستمر" . شتيتل-أوبتمايزد . مؤرشف من الأصل في 28 أغسطس 2023. تم الاسترجاع في 27 أغسطس 2023 .
1 2 3 ريبيل، يوهانس (مارس 2023). عدم قابلية حسم BB(748): فهم نظريات عدم الاكتمال لغودل (ملف PDF) (رسالة بكالوريوس). جامعة أوغسبورغ . مؤرشف (ملف PDF) من الأصل في 17 سبتمبر 2024. تم الاطلاع عليه في 24 سبتمبر 2024 .
١ ٢ ٣ ٤ ٥ ٦ ٧ بن عمرام، أ.م.؛ جولستروم، ب.أ.؛ زويك، يو. (١ أغسطس ١٩٩٦). "ملاحظة حول القنادس المشغولة وغيرها من المخلوقات" . نظرية الأنظمة الرياضية . ٢٩ (٤): ٣٧٥-٣٨٦ . doi : 10.1007/BF01192693 . ISSN 1433-0490 .
1 2 3 4 5 6 7 8 آرونسون، سكوت (2 يوليو 2024). "يُعرف الآن أن BusyBeaver(5) هو 47,176,870" . Shtetl-Optimized . تم الاسترجاع في 4 يوليو 2024 .
1 2 3 وولفرام، ستيفن (4 فبراير 2021). "آلات تورينج متعددة الاتجاهات" . www.wolframphysics.org . مؤرشف من الأصل في 7 يوليو 2022. تم الاسترجاع في 7 يوليو 2022 .
↑ تشايتين 1987 ، ص. 2.
↑ بولوس، بورغيس وجيفري، 2007. "الحوسبة والمنطق"
لين ، شين ؛ رادو، تيبور (أبريل 1965). "دراسات حاسوبية لمسائل آلة تورينج" . مجلة ACM . 12 (2): 196-212 . doi : 10.1145/321264.321270 . S2CID 17789208 .
↑ يديديا، آدم؛ آرونسون، سكوت (مايو 2016). "آلة تورينغ صغيرة نسبياً يكون سلوكها مستقلاً عن نظرية المجموعات". arXiv : 1605.04343 [ cs.FL ].
↑ آرون، جاكوب (11 مايو 2016). "يجب أن تعمل آلة تورينج هذه إلى الأبد ما لم تكن الرياضيات خاطئة" . مجلة نيو ساينتست . مؤرشف من الأصل في 20 أكتوبر 2016. تم الاطلاع عليه في 25 سبتمبر 2016 .
↑ احتوت النسخة الصادرة في 3 مايو على 7918 حالة: آرونسون، سكوت (3 مايو 2016). "العدد 8000 من أعداد بيزي بيفر يفلت من نظرية مجموعات ZF" . مُحسَّن بواسطة شتيتل . مؤرشف من الأصل في 27 سبتمبر 2016. تم الاطلاع عليه في 25 سبتمبر 2016 .
↑ فريدمان، هارفي م. (15 يناير 2001). "الأعداد الأساسية الدقيقة والترتيبات الخطية" . حوليات المنطق البحت والتطبيقي . 107 (1): 1-34 . doi : 10.1016/S0168-0072(00)00019-1 . ISSN 0168-0072 .
1 2 3 آرونسون، سكوت (3 مايو 2016). "ثلاثة إعلانات" . شتيتل-أوبتمايزد . تم الاسترجاع في 27 أبريل 2018 .
↑ "sorear/metamath-turing-machines: مُعدِّدات إثباتات الرياضيات الفوقية وغيرها" . GitHub . ١٣ فبراير ٢٠١٩. مؤرشف من الأصل في ١٧ أبريل ٢٠٢١. تم الاطلاع عليه في ١٩ مايو ٢٠١٨ .
↑ "آلة تورينج العكسية" . skelet.ludost.net . تم الاطلاع عليه بتاريخ 10 فبراير 2022 .
↑ "A060843 - OEIS" . oeis.org . تم الاطلاع عليه بتاريخ 19 فبراير 2026 .
↑ مسابقات باسكال ميشيل " بيزي بيفر" مؤرشفة بتاريخ 2023-10-06 في صفحة Wayback Machine التي تسرد أفضل المتنافسين المعروفين.
↑ ميشيل، باسكال (14 ديسمبر 2015). "مشكلات في نظرية الأعداد من منافسة القندس المشغول". الأساليب المنطقية في علوم الحاسوب . 11 (4): 10.
↑ تشايتين 1987 ، ص 3.
↑ بيشوف، مانون (25 يوليو 2024). "علماء الرياضيات وجدوا أخيرًا خامس "أكثر القنادس انشغالًا"" . مجلة ساينتفك أمريكان . تم الاطلاع عليه بتاريخ 10 سبتمبر 2025 .
↑ آرونسون، سكوت (28 يونيو 2025). "BusyBeaver(6) كبير جدًا بالفعل" . Shtetl-Optimized . تم الاسترجاع في 16 يوليو 2025 .
↑ ستيرين، تريستان؛ وودز، داميان (2021). "صلابة قيمة القندس المشغول BB(15)". arXiv : 2107.12475 [ cs.LO ].
↑ إيردوس، بول (1979). " بعض المسائل غير التقليدية في نظرية الأعداد" . مجلة الرياضيات . 52 (2): 67-70 . doi : 10.1080/0025570X.1979.11976756 . JSTOR 2689842. مؤرشف من الأصل في 13 يونيو 2022. تم الاطلاع عليه في 7 يوليو 2022 .
↑ "مضاد الهيدرا" . BusyBeaverWiki . تم الاطلاع عليه بتاريخ 18 يونيو 2025 .
1 2 أورد، توبي (2024). "حدود معدلات النمو والتقارب لجميع العمليات الفيزيائية". arXiv : 2410.10928 [ physics.hist-ph ].
↑ كارميلا بادافيتش-كالاغان (1 نوفمبر 2024). "قد يكون هناك حد أقصى للسرعة الكونية لنمو أي شيء" . مجلة نيو ساينتست .
↑ برادي، ألين هـ. (مارس 1998). "هاينر ماركسن ويورغن بونتروك. مهاجمة القندس المشغول 5. نشرة الرابطة الأوروبية لعلوم الحاسوب النظرية، العدد 40 (فبراير 1990)، الصفحات 247-251. - باسكال ميشيل. منافسة القندس المشغول ومسائل شبيهة بمسائل كولاتز. أرشيف المنطق الرياضي، المجلد 32 (1993)، الصفحات 351-367" . مجلة المنطق الرمزي (مراجعة كتاب). 63 (1): 331-332 . doi : 10.2307/2586607 . ISSN 0022-4812 . JSTOR 2586607. مؤرشف من الأصل في 5 يوليو 2024. تم الاسترجاع في 5 يوليو 2024 . نسخة HTML مجانية من تأليف الكاتب، مؤرشفة بتاريخ 9 أكتوبر 2006 على موقع Wayback Machine.
1 2 3 4 غرين، ميلتون دبليو. (11 نوفمبر 1964). "الحد الأدنى لدالة سيجما رادو لآلات تورينغ الثنائية". وقائع الندوة السنوية الخامسة لعام 1964 حول نظرية دوائر التبديل والتصميم المنطقي . جمعية مهندسي الكهرباء والإلكترونيات. الصفحات 91-94 . doi : 10.1109/SWCT.1964.3 .
1 2 3 4 5 6 7 8 ميشيل، باسكال. "دراسة تاريخية عن القنادس المشغولة" . تم الاطلاع عليه بتاريخ 24 يناير 2026 .
١ ٢ ٣ ٤ ٥ ٦ ٧ ٨ ٩ ١٠ ١١ ١٢ ١٣ ١٤ ١٥ ١٦ بن عمرام، أ.م.؛ بيترسن، هـ. (٢٠٠٢). "حدود محسّنة للدوال المتعلقة بالقنادس المشغولة". نظرية أنظمة الحوسبة . ٣٥ (١): ١-١١ . doi : 10.1007/s00224-001-1052-0 . MR 1879169 .
1 2 3 بلانشارد، جوستين؛ بريجز، دانيال. ديكا، كونراد. فينر، ناثان؛ فورستر، يانيك. جورجييف، جورجي؛ هاوس، ماثيو إل. هانتر، راشيل؛ إيجيل. كادزيوكا، ماجا؛ كروبيتز، بافيل؛ ليغوكي، شون. mxdys; ناسيسزيفسكي، ماتيوس؛ سافاسك. سترين، تريستان؛ شو، كريس؛ يوين، جايسون؛ زيمرمان ، ثيو (15 سبتمبر 2025). “تحديد القيمة الخامسة للقندس المشغول”. أرخايف : 2509.12337 [ cs.LO ].
↑ "0RB1LD_1LC1RB_1LD1RE_1LA1LE_1LZ0RC - BusyBeaverWiki" . wiki.bbchallenge.org . تم الاطلاع عليه بتاريخ 17 يوليو 2026 .
↑ [ 2 يوليو 2024 ] لقد أثبتنا أن 'BB(5) = 47,176,870 '" تحدي القندس المشغول " . 2 يوليو 2024. مؤرشف من الأصل في 2 يوليو 2024. تم الاطلاع عليه في 2 يوليو 2024 .
↑ بروبيكر، بن (2 يوليو 2024). "علماء رياضيات هواة يكتشفون آلة تورينج الخامسة "النشيطة"" . مجلة كوانتا . تم الاطلاع عليه في 4 فبراير 2026 .
↑ شين لين (1963). دراسات حاسوبية لمشاكل آلة تورينج (أطروحة دكتوراه). جامعة ولاية أوهايو .

مراجع

رادو، تيبور (مايو 1962). "حول الدوال غير القابلة للحساب" (ملف PDF) . مجلة بيل سيستم التقنية . 41 (3): 877-884 . doi : 10.1002/j.1538-7305.1962.tb00480.x . مؤرشف (ملف PDF) من الأصل في 12 أكتوبر 2021. تم الاطلاع عليه في 7 يوليو 2022 .
هنا قام رادو بتعريف مشكلة القندس المشغول لأول مرة وأثبت أنها غير قابلة للحساب وتنمو بشكل أسرع من أي دالة قابلة للحساب.
لين، شين؛ رادو، تيبور (أبريل 1965). "دراسات حاسوبية لمسائل آلة تورينج" . مجلة ACM . 12 (2): 196-212 . doi : 10.1145/321264.321270 . S2CID 17789208 .
نُشرت نتائج هذه الورقة البحثية جزئيًا في أطروحة لين للدكتوراه عام 1963، تحت إشراف رادو. أثبت لين ورادو أن Σ(3) = 6 و S (3) = 21 من خلال إثبات أن جميع آلات تورينغ ذات 3 حالات ورمزين والتي لا تتوقف خلال 21 خطوة لن تتوقف أبدًا. (تم إثبات معظمها تلقائيًا بواسطة برنامج حاسوبي، بينما تم إثبات 40 منها عن طريق الفحص البشري).
برادي، ألين هـ. (أبريل 1983). "تحديد قيمة دالة رادو غير القابلة للحساب Σ( k ) لآلات تورينج ذات الأربع حالات" . رياضيات الحساب . 40 (162): 647-665 . doi : 10.1090/S0025-5718-1983-0689479-6 . JSTOR 2007539 .
أثبت برادي أن مجموع (4) يساوي 13 وأن S (4) يساوي 107. عرّف برادي فئتين جديدتين لآلات تورينغ غير المتوقفة ذات الحالات الثلاث والرمزين: أشجار عيد الميلاد والعدادات. استخدم برنامجًا حاسوبيًا لإثبات أن جميع الآلات، باستثناء 27 آلة تعمل على 107 خطوات، هي أنواع مختلفة من أشجار عيد الميلاد والعدادات التي يمكن إثبات قدرتها على العمل بلا حدود. أما الآلات الـ 27 المتبقية (المشار إليها بالآلات المتبقية)، فقد أثبت برادي بنفسه، من خلال فحصها، أنها لا تتوقف.
ماشلين، رونا؛ ستاوت، كوينتين ف. (يونيو 1990). "السلوك المعقد للآلات البسيطة" . فيزيكا د: الظواهر غير الخطية . 42 ( 1-3 ): 85-98 . Bibcode : 1990PhyD...42...85M . doi : 10.1016/0167-2789(90)90068-Z . hdl : 2027.42/28528 . مؤرشف من الأصل في 30 يناير 2012. تم الاسترجاع في 7 يوليو 2022 .
يصف ماكلين وستوت مشكلة القندس المشغول والعديد من التقنيات المستخدمة لإيجاد القنادس المشغولة (والتي يطبقانها على آلات تورينج ذات 4 حالات ورمزين، مما يؤكد برهان برادي). ويقترحان كيفية تقدير صيغة معدلة لاحتمالية توقف تشايتين (Ω).
ماركسن، هاينر؛ بونتروك، يورغن (فبراير 1990). "مهاجمة بيفر المشغول 5" . نشرة الجمعية الأوروبية لعلوم وتكنولوجيا الحاسوب . 40 : 247-251 . مؤرشف من الأصل في 9 أكتوبر 2006. تم الاطلاع عليه في 19 يناير 2020 .
أثبت ماركسن وبونتروك أن Σ(5) ≥ 4098 و S (5) ≥ 47 176 870 ووصف بالتفصيل الطريقة التي استخدموها للعثور على هذه الآلات وإثبات أن العديد من الآلات الأخرى لن تتوقف أبدًا.
غرين، ميلتون و. (1964). "دالة سيجما رادو للحد الأدنى لآلات تورينغ الثنائية". وقائع الندوة السنوية الخامسة حول نظرية دوائر التبديل والتصميم المنطقي ، 1964. ص 91-94 . doi : 10.1109/SWCT.1964.3 . مؤرشف من الأصل في 3 فبراير 2019. تم الاطلاع عليه في 7 يوليو 2022 .
يقوم غرين بإنشاء آلات بشكل متكرر لأي عدد من الحالات، ويقدم الدالة المتكررة التي تحسب نقاطها (تحسب σ)، مما يوفر حدًا أدنى لـ Σ. نمو هذه الدالة مماثل لنمو دالة أكرمان .
ديودني، ألكسندر ك. (1984). "فخ حاسوبي للقندس المشغول، آلة تورينج الأكثر اجتهادًا". مجلة ساينتفك أمريكان . 251 (2): 10-17 .
تم وصف برامج القنادس النشطة بواسطة ألكسندر ديودني في مجلة ساينتفك أمريكان ، أغسطس 1984، الصفحات 19-23، وكذلك مارس 1985 صفحة 23 وأبريل 1985 صفحة 30 .
تشايتين، غريغوري ج. (1987). "حساب دالة بيفر المشغول" (ملف PDF) . في: كوفر، تي إم؛ غوبيناث، ب. (محرران). مشاكل مفتوحة في الاتصالات والحوسبة . سبرينغر. الصفحات 108-112 . ISBN 978-0-387-96621-2تمت أرشفة هذا الملف من النسخة الأصلية (PDF) بتاريخ 30 ديسمبر 2017. تم الاطلاع عليه بتاريخ 7 يوليو 2022 .
برادي، ألين هـ. (1995). "لعبة القندس النشيط ومعنى الحياة". في: هيركن، رولف (محرر). آلة تورينج العالمية: دراسة نصف قرن ( الطبعة الثانية). فيينا، نيويورك: سبرينغر-فيرلاغ. ص 237-254 . ISBN 978-3-211-82637-9.
يصف برادي (صاحب الشهرة في الولايات الأربع) تاريخًا موجزًا للوحش، ويُطلق على ملاحقته اسم "لعبة القندس النشيط". كما يصف ألعابًا أخرى (مثل الأوتوماتا الخلوية ولعبة كونواي للحياة ). ومن بين الأجزاء ذات الأهمية الخاصة "لعبة القندس النشيط ثنائية الأبعاد" (صفحة ٢٤٧). مع ١٩ مرجعًا.
بوث، تايلور ل. (1967). الآلات التسلسلية ونظرية الأوتوماتا . نيويورك: وايلي. ISBN 978-0-471-08848-6.
راجع الفصل التاسع، آلات تورينج. كتابٌ صعب، مُوجَّهٌ لمهندسي الكهرباء والمتخصصين التقنيين. يناقش الاستدعاء الذاتي، والاستدعاء الذاتي الجزئي مع الإشارة إلى آلات تورينج، ومسألة التوقف. يُنسب كتاب بوث مسألة القندس المشغول إلى رادو. كما يُعرّف بوث مسألة القندس المشغول لرادو في "المسائل المنزلية" 3، 4، 5، 6 من الفصل التاسع، صفحة 396. المسألة 3 هي "إثبات أن مسألة القندس المشغول غير قابلة للحل... لجميع قيم n".
بن عمرام، أ.م.؛ بيترسن، هـ. (2002). "حدود محسّنة للدوال المتعلقة بخوارزمية بيزي بيفرز". نظرية أنظمة الحوسبة . 35 : 1-11 . CiteSeerX 10.1.1.136.5997 . doi : 10.1007/s00224-001-1052-0 . S2CID 10429773 .
حدود محسّنة.
لافيت، ج.؛ بابازيان، س. (يونيو 2007). "بنية آلات تورينج الصغيرة". الحوسبة والمنطق في العالم الحقيقي، وقائع المؤتمر الثالث حول قابلية الحوسبة في أوروبا . ص 219-227 . CiteSeerX 10.1.1.104.3021 .
تحتوي هذه المقالة على تصنيف كامل لآلات تورينج ذات الحالة 2 والرمز 3، وبالتالي برهان على القندس المشغول (2، 3): Σ(2، 3) = 9 و S(2، 3) = 38.
بولوس، جورج س.؛ بورغيس، جون ب.؛ جيفري، ريتشارد س. (2007). الحوسبة والمنطق ( الطبعة الخامسة). مطبعة جامعة كامبريدج. ISBN 978-0-521-87752-7.
كروبيتز، بافيل (2010). مشكلة القندس المشغول (ملف PDF) (رسالة بكالوريوس) (باللغة السلوفاكية). جامعة تشارلز في براغ.
هذا هو وصف الأفكار والخوارزميات وتنفيذها، مع وصف التجارب التي تفحص آلات تورينج ذات 5 حالات و6 حالات عن طريق التشغيل المتوازي على 31 جهاز كمبيوتر رباعي النواة، وأخيرًا أفضل النتائج لآلة تورينج ذات 6 حالات.

روابط خارجية

صفحة هاينر ماركسن ، الذي وجد مع يورغن بونتروك السجلات المذكورة أعلاه لآلة تورينغ ذات 5 و 6 حالات.
دراسة باسكال ميشيل التاريخية لنتائج القندس النشيط والتي تتضمن أيضًا أفضل النتائج وبعض التحليلات.
تعريف فئة RTM - آلات تورينج العكسية، وهي فئة فرعية بسيطة وقوية من آلات تورينج.
" مشكلة القندس المشغول: هجوم الألفية الجديدة " ( مؤرشف ) في مختبر رينسيلير RAIR. وقد أسفر هذا الجهد عن العديد من الأرقام القياسية الجديدة وحدد العديد من القيم للصيغة الرباعية.
أرشيف موقع دانيال بريجز الإلكتروني ومنتدى لحل مشكلة القندس المشغول ذي 5 حالات ورمزين، استنادًا إلى قائمة الآلات غير المنتظمة لـ Skelet (جورجي جورجيف).
ليغوسكي، شون (17 يوليو 2021). "سلوك يشبه سلوك كولاتز لدى قنادس بيزي" . sligocki . تم الاسترجاع في 12 يوليو 2022 .
آرونسون، سكوت (1999)، من يستطيع تسمية الرقم الأكبر؟
وايسشتاين، إريك دبليو. "القندس المشغول" . عالم الرياضيات .
آلات تورينج بيزي بيفر - كمبيوتر فايل ، يوتيوب
باسكال ميشيل. مسابقة القندس النشيط: دراسة تاريخية . 70 صفحة. 2017. <hal-00396880v5>
تسلسل OEIS A060843 (مشكلة بيزي بيفر)
صفحة ويكي تحدي بيزي بيفر

[Story_#_space-time-diagrams-1] 1 2 "قصة # مخططات الزمكان" . تحدي بيزي بيفر . تم الاسترجاع في 9 يوليو 2024 .

[:2-2] 1 2 3 4 5 وايسشتاين، إريك دبليو. "بيفر المشغول" . وولفرام ماث وورلد . مؤرشف من الأصل في 7 ديسمبر 2023. تم الاسترجاع في 21 نوفمبر 2023 .

[:4-3] 1 2 3 بروبيكر، بن (2 يوليو 2024). "علماء رياضيات هواة يكتشفون آلة تورينج الخامسة "النشيطة"" . مجلة كوانتا . تم الاطلاع عليه في 3 يوليو 2024 .

[rado-4] 1 2 3 4 5 6 7 8 9 10 11 12 رادو، تيبور (مايو 1962). "حول الدوال غير القابلة للحساب" (ملف PDF) . مجلة بيل سيستم التقنية . 41 (3): 877-884 . doi : 10.1002/j.1538-7305.1962.tb00480.x . مؤرشف (ملف PDF) من الأصل في 12 أكتوبر 2021. تم الاطلاع عليه في 7 يوليو 2022 .

[:62-5] ١ ٢ ٣ ٤ ٥ ٦ ٧ ٨ ٩ ١٠ ١١ ١٢ ١٣ ١٤ آرونسون، سكوت (٢٩ سبتمبر ٢٠٢٠). "حدود بيفر المشغولة" (ملف PDF) . أخبار SIGACT . ٥١ (٣): ٣٢-٥٤ . doi : 10.1145/3427361.3427369 . ISSN 0163-5700 . مؤرشف من الأصل (ملف PDF) في ٥ يوليو ٢٠٢٢.

[:1-6] 1 2 3 4 5 6 7 8 بافلوس، جون (10 ديسمبر 2020). "كيف تُسلط أبطأ برامج الحاسوب الضوء على الحدود الأساسية للرياضيات" . مجلة كوانتا . مؤرشف من الأصل في 10 ديسمبر 2020. تم الاطلاع عليه في 11 ديسمبر 2020 .

[yijun-7] 1 2 3 لينغ، ييجون. "مستودع جيثب 'goldbach_tm27'" . GitHub .

[AaronsonJuly2023-8] 1 2 3 آرونسون، سكوت (5 يوليو 2023). "الحياة، والتدوين، ووظيفة بيزي بيفر تستمر" . شتيتل-أوبتمايزد . مؤرشف من الأصل في 28 أغسطس 2023. تم الاسترجاع في 27 أغسطس 2023 .

[:3-9] 1 2 3 ريبيل، يوهانس (مارس 2023). عدم قابلية حسم BB(748): فهم نظريات عدم الاكتمال لغودل (ملف PDF) (رسالة بكالوريوس). جامعة أوغسبورغ . مؤرشف (ملف PDF) من الأصل في 17 سبتمبر 2024. تم الاطلاع عليه في 24 سبتمبر 2024 .

[:6-10] ١ ٢ ٣ ٤ ٥ ٦ ٧ بن عمرام، أ.م.؛ جولستروم، ب.أ.؛ زويك، يو. (١ أغسطس ١٩٩٦). "ملاحظة حول القنادس المشغولة وغيرها من المخلوقات" . نظرية الأنظمة الرياضية . ٢٩ (٤): ٣٧٥-٣٨٦ . doi : 10.1007/BF01192693 . ISSN 1433-0490 .

[:5-11] 1 2 3 4 5 6 7 8 آرونسون، سكوت (2 يوليو 2024). "يُعرف الآن أن BusyBeaver(5) هو 47,176,870" . Shtetl-Optimized . تم الاسترجاع في 4 يوليو 2024 .

[NDTM-12] 1 2 3 وولفرام، ستيفن (4 فبراير 2021). "آلات تورينج متعددة الاتجاهات" . www.wolframphysics.org . مؤرشف من الأصل في 7 يوليو 2022. تم الاسترجاع في 7 يوليو 2022 .

[FOOTNOTEChaitin19872-13] تشايتين 1987 ، ص. 2.

[14] بولوس، بورغيس وجيفري، 2007. "الحوسبة والمنطق"

[:10-15] لين ، شين ؛ رادو، تيبور (أبريل 1965). "دراسات حاسوبية لمسائل آلة تورينج" . مجلة ACM . 12 (2): 196-212 . doi : 10.1145/321264.321270 . S2CID 17789208 .

[16] يديديا، آدم؛ آرونسون، سكوت (مايو 2016). "آلة تورينغ صغيرة نسبياً يكون سلوكها مستقلاً عن نظرية المجموعات". arXiv : 1605.04343 [ cs.FL ].

[17] آرون، جاكوب (11 مايو 2016). "يجب أن تعمل آلة تورينج هذه إلى الأبد ما لم تكن الرياضيات خاطئة" . مجلة نيو ساينتست . مؤرشف من الأصل في 20 أكتوبر 2016. تم الاطلاع عليه في 25 سبتمبر 2016 .

[:0-18] احتوت النسخة الصادرة في 3 مايو على 7918 حالة: آرونسون، سكوت (3 مايو 2016). "العدد 8000 من أعداد بيزي بيفر يفلت من نظرية مجموعات ZF" . مُحسَّن بواسطة شتيتل . مؤرشف من الأصل في 27 سبتمبر 2016. تم الاطلاع عليه في 25 سبتمبر 2016 .

[19] فريدمان، هارفي م. (15 يناير 2001). "الأعداد الأساسية الدقيقة والترتيبات الخطية" . حوليات المنطق البحت والتطبيقي . 107 (1): 1-34 . doi : 10.1016/S0168-0072(00)00019-1 . ISSN 0168-0072 .

[Aaronson3-20] 1 2 3 آرونسون، سكوت (3 مايو 2016). "ثلاثة إعلانات" . شتيتل-أوبتمايزد . تم الاسترجاع في 27 أبريل 2018 .

[21] "sorear/metamath-turing-machines: مُعدِّدات إثباتات الرياضيات الفوقية وغيرها" . GitHub . ١٣ فبراير ٢٠١٩. مؤرشف من الأصل في ١٧ أبريل ٢٠٢١. تم الاطلاع عليه في ١٩ مايو ٢٠١٨ .

[22] "آلة تورينج العكسية" . skelet.ludost.net . تم الاطلاع عليه بتاريخ 10 فبراير 2022 .

[23] "A060843 - OEIS" . oeis.org . تم الاطلاع عليه بتاريخ 19 فبراير 2026 .

[michel_comp-24] مسابقات باسكال ميشيل " بيزي بيفر" مؤرشفة بتاريخ 2023-10-06 في صفحة Wayback Machine التي تسرد أفضل المتنافسين المعروفين.

[25] ميشيل، باسكال (14 ديسمبر 2015). "مشكلات في نظرية الأعداد من منافسة القندس المشغول". الأساليب المنطقية في علوم الحاسوب . 11 (4): 10.

[FOOTNOTEChaitin19873-26] تشايتين 1987 ، ص 3.

[j906-27] بيشوف، مانون (25 يوليو 2024). "علماء الرياضيات وجدوا أخيرًا خامس "أكثر القنادس انشغالًا"" . مجلة ساينتفك أمريكان . تم الاطلاع عليه بتاريخ 10 سبتمبر 2025 .

[28] آرونسون، سكوت (28 يونيو 2025). "BusyBeaver(6) كبير جدًا بالفعل" . Shtetl-Optimized . تم الاسترجاع في 16 يوليو 2025 .

[29] ستيرين، تريستان؛ وودز، داميان (2021). "صلابة قيمة القندس المشغول BB(15)". arXiv : 2107.12475 [ cs.LO ].

[30] إيردوس، بول (1979). " بعض المسائل غير التقليدية في نظرية الأعداد" . مجلة الرياضيات . 52 (2): 67-70 . doi : 10.1080/0025570X.1979.11976756 . JSTOR 2689842. مؤرشف من الأصل في 13 يونيو 2022. تم الاطلاع عليه في 7 يوليو 2022 .

[31] "مضاد الهيدرا" . BusyBeaverWiki . تم الاطلاع عليه بتاريخ 18 يونيو 2025 .

[ord-bounds-32] 1 2 أورد، توبي (2024). "حدود معدلات النمو والتقارب لجميع العمليات الفيزيائية". arXiv : 2410.10928 [ physics.hist-ph ].

[33] كارميلا بادافيتش-كالاغان (1 نوفمبر 2024). "قد يكون هناك حد أقصى للسرعة الكونية لنمو أي شيء" . مجلة نيو ساينتست .

[34] برادي، ألين هـ. (مارس 1998). "هاينر ماركسن ويورغن بونتروك. مهاجمة القندس المشغول 5. نشرة الرابطة الأوروبية لعلوم الحاسوب النظرية، العدد 40 (فبراير 1990)، الصفحات 247-251. - باسكال ميشيل. منافسة القندس المشغول ومسائل شبيهة بمسائل كولاتز. أرشيف المنطق الرياضي، المجلد 32 (1993)، الصفحات 351-367" . مجلة المنطق الرمزي (مراجعة كتاب). 63 (1): 331-332 . doi : 10.2307/2586607 . ISSN 0022-4812 . JSTOR 2586607. مؤرشف من الأصل في 5 يوليو 2024. تم الاسترجاع في 5 يوليو 2024 . نسخة HTML مجانية من تأليف الكاتب، مؤرشفة بتاريخ 9 أكتوبر 2006 على موقع Wayback Machine.

[:7-35] 1 2 3 4 غرين، ميلتون دبليو. (11 نوفمبر 1964). "الحد الأدنى لدالة سيجما رادو لآلات تورينغ الثنائية". وقائع الندوة السنوية الخامسة لعام 1964 حول نظرية دوائر التبديل والتصميم المنطقي . جمعية مهندسي الكهرباء والإلكترونيات. الصفحات 91-94 . doi : 10.1109/SWCT.1964.3 .

[pascal.chronological-36] 1 2 3 4 5 6 7 8 ميشيل، باسكال. "دراسة تاريخية عن القنادس المشغولة" . تم الاطلاع عليه بتاريخ 24 يناير 2026 .

[:8-37] ١ ٢ ٣ ٤ ٥ ٦ ٧ ٨ ٩ ١٠ ١١ ١٢ ١٣ ١٤ ١٥ ١٦ بن عمرام، أ.م.؛ بيترسن، هـ. (٢٠٠٢). "حدود محسّنة للدوال المتعلقة بالقنادس المشغولة". نظرية أنظمة الحوسبة . ٣٥ (١): ١-١١ . doi : 10.1007/s00224-001-1052-0 . MR 1879169 .

[bb5-paper-38] 1 2 3 بلانشارد، جوستين؛ بريجز، دانيال. ديكا، كونراد. فينر، ناثان؛ فورستر، يانيك. جورجييف، جورجي؛ هاوس، ماثيو إل. هانتر، راشيل؛ إيجيل. كادزيوكا، ماجا؛ كروبيتز، بافيل؛ ليغوكي، شون. mxdys; ناسيسزيفسكي، ماتيوس؛ سافاسك. سترين، تريستان؛ شو، كريس؛ يوين، جايسون؛ زيمرمان ، ثيو (15 سبتمبر 2025). “تحديد القيمة الخامسة للقندس المشغول”. أرخايف : 2509.12337 [ cs.LO ].

[39] "0RB1LD_1LC1RB_1LD1RE_1LA1LE_1LZ0RC - BusyBeaverWiki" . wiki.bbchallenge.org . تم الاطلاع عليه بتاريخ 17 يوليو 2026 .

[40] [ 2 يوليو 2024 ] لقد أثبتنا أن 'BB(5) = 47,176,870 '" تحدي القندس المشغول " . 2 يوليو 2024. مؤرشف من الأصل في 2 يوليو 2024. تم الاطلاع عليه في 2 يوليو 2024 .

[41] بروبيكر، بن (2 يوليو 2024). "علماء رياضيات هواة يكتشفون آلة تورينج الخامسة "النشيطة"" . مجلة كوانتا . تم الاطلاع عليه في 4 فبراير 2026 .

[42] شين لين (1963). دراسات حاسوبية لمشاكل آلة تورينج (أطروحة دكتوراه). جامعة ولاية أوهايو .

[ 1 ]

[ 4 ]

[ 7 ]

[ 8 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 16 ]

[ 17 ]

[ 19 ]

[ 20 ]

[ 21 ]

[٢٢]

[

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[

[ 32 ]

[ 33 ]

[ 34 ]

[ 36 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ 42 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗