مشغل Mu

في نظرية الحوسبة ، يبحث عامل μ ، أو عامل التصغير ، أو عامل البحث غير المحدود ، عن أصغر عدد طبيعي يحقق خاصية معينة. وبإضافة عامل μ إلى الدوال التكرارية الأولية، يصبح من الممكن تعريف جميع الدوال القابلة للحوسبة .

تعريف

لنفترض أن R ( y , x1 , ..., xk ) علاقة ثابتة _من الرتبة ( k + 1 ) على الأعداد الطبيعية . المؤثر μ _، سواءً كان محدودًا أو غير محدود، هو دالة عددية معرفة من الأعداد الطبيعية إلى الأعداد الطبيعية. مع ذلك، يتضمن تعريف μ y شرطًا على الأعداد الطبيعية، يمكن اعتباره شرطًا يكون صحيحًا عندما يتحقق الشرط، وخاطئًا عندما لا يتحقق.

يظهر عامل μ المحدود في وقت سابق في كلين (1952) الفصل التاسع الدوال التكرارية الأولية، القسم 45 المسندات، تمثيل العامل الأولي على النحو التالي:

"

\displaystyle \mu y_{y<z}R(y).\ \ {\mbox{أصغر}}\ y<z\ {\mbox{بحيث}}\ R(y),\ {\mbox{إذا}}\ (\exists y)_{y<z}R(y)؛\ {\mbox{وإلا}},\ z.}

(ص 225)

يشير ستيفن كلين إلى أنه يُسمح بأي من قيود المتباينات الستة على مدى المتغير y ، أي y < z ، وy ≤ z ، وw < y < z ، وw < y ≤ z ، وw ≤ y < z، و w ≤ y ≤ z . "عندما لا يحتوي المدى المُشار إليه على أي قيمة y بحيث تكون R ( y ) صحيحة، فإن قيمة التعبير "μy " هي العدد الأصلي للمدى" (ص 226)؛ ولهذا السبب يظهر الافتراضي " z " في التعريف أعلاه. كما هو موضح أدناه، يُعرَّف عامل μ المحدود "μy < _{z " بدلالة} دالتين تكراريتين بدائيتين تُسميان المجموع المحدود Σ والضرب المحدود Π، ودالة مسندة "تُجري الاختبار"، ودالة تمثيلية تُحوِّل {t, f} إلى {0, 1}.

في الفصل الحادي عشر، القسم 57، الدوال التكرارية العامة، يُعرّف كلين عامل μ غير المحدود على المتغير y بالطريقة التالية:

"

(\exists y)\mu yR(y)=\{{\mbox{أصغر عدد طبيعي}}\ y\ {\mbox{بحيث}}\ R(y)\}

(ص 279، حيث "

(\exists y)

" تعني " يوجد y بحيث ... "

في هذه الحالة، تُرجع R نفسها، أو دالتها المُمثلة لها ، القيمة 0 عندما يتحقق الشرط (أي عندما تكون القيمة صحيحة )؛ ثم تُرجع الدالة العدد y . لا يوجد حد أعلى لـ y ، وبالتالي لا تظهر أي تعابير متباينة في تعريفها.

بالنسبة لـ R ( y ) المعطاة، فإن عامل μ غير المحدود μ yR ( y ) (لاحظ أنه لا يوجد شرط لـ " $(\exists y)$ " ) هي دالة جزئية . يقوم كلين بجعلها دالة كلية بدلاً من ذلك (انظر الصفحة 317):

$\varepsilon yR(x,y)={\begin{cases}{\text{أصغر قيمة }}y{\text{ بحيث }}R(x,y),&{\text{إذا }}(\exists y)R(x,y)\\0,&{\text{فيما عدا ذلك}}.\end{cases}}$

تمت دراسة النسخة الكاملة من عامل μ غير المحدود في الرياضيات العكسية من الرتبة العليا بالشكل التالي: ^[¹^]

$(\exists \mu ^{2})(\forall f^{1}){\big (}(\exists n^{0})(f(n)=0)\rightarrow f(\mu (f))=0{\big )},$

حيث تشير الأرقام المرتفعة إلى أن n من الرتبة الصفرية، و f من الرتبة الأولى، و μ من الرتبة الثانية. يؤدي هذا المبدأ إلى نظام العوامل الخمسة الكبرى ACA ₀ عند دمجه مع النظرية الأساسية المعتادة للرياضيات العكسية من الرتب العليا.

ملكيات

(أ) في سياق الدوال التكرارية الأولية ، حيث يكون متغير البحث y للمؤثر μ محدودًا، على سبيل المثال y < z في الصيغة أدناه، إذا كانت الدالة R تكرارية أولية (برهان كلين #E، صفحة 228)، فإن

μ y _{y < z} R ( y , x ₁ , ..., x _n ) هي دالة تكرارية بدائية.

(ii) في سياق الدوال التكرارية (الكلي)، حيث يكون متغير البحث y غير محدود ولكنه مضمون الوجود لجميع قيم x i _{لمعاملات} المسند التكراري الكلي R ،

( x1 ₎ , ..., ( xn ₎

(\exists y)

R ( y , x _i , ..., x _n ) يعني أن μ yR ( y , x _i , ..., x _n ) هي دالة تكرارية كلية .

هنا ( xi ₎ تعني "لكل xi _" و

\exists y

يعني "يوجد على الأقل قيمة واحدة لـ y بحيث ..." (انظر كلين (1952) ص 279.)

ثم تؤدي عوامل التشغيل التكرارية الأولية الخمسة بالإضافة إلى عامل التشغيل μ غير المحدود ولكن الكلي إلى ما أسماه كلين بالوظائف التكرارية "العامة" (أي الوظائف الكلية المحددة بواسطة عوامل التشغيل التكرارية الستة).

(iii) في سياق الدوال التكرارية الجزئية : لنفترض أن العلاقة R صحيحة لـ y ، x₁ _، ...، _xₙ إذا وفقط إذا كانت دالة تكرارية جزئية معرفة على y ، x₁ _، ...، xₙ _وتساوي صفرًا. ولنفترض أيضًا أن هذه الدالة التكرارية الجزئية معرفة (ولكن ليس بالضرورة أن تساوي صفرًا) كلما كانت μyR ( y , x₁ , ..., _xₖ ) معرفة وكان y يساوي μyR ( y , x₁ , ..., _xₖ ) _أو_{أصغر منه. عندئذٍ ،} تكون الدالة μyR ( y , x₁ , _... , _xₖ) أيضًا دالة تكرارية جزئية.

يتم استخدام عامل μ في توصيف الدوال القابلة للحساب كدوال μ-تكرارية .

في الرياضيات البنائية ، يرتبط عامل البحث غير المحدود بمبدأ ماركوف .

أمثلة

مثال 1: المؤثر μ المحدود هو دالة تكرارية أولية

فيما يلي ، يمثل x السلسلة x _i ، ... ، x _n .

يمكن التعبير عن المؤثر μ المحدود ببساطة باستخدام دالتين تكراريتين بدائيتين (يُشار إليهما فيما يلي بـ "prf") تُستخدمان أيضًا لتعريف دالة CASE، وهما دالة حاصل ضرب الحدود Π ودالة مجموع الحدود Σ (انظر Kleene #B، صفحة 224). (عند الحاجة، يُمكن استخدام أي حد للمتغير، مثل s ≤ t أو t < z ، أو 5 < x < 17، إلخ). على سبيل المثال:

Π _{s ≤ t} f _s ( x , s ) = f ₀ ( x , 0) × f ₁ ( x , 1) × ... × f _t ( x , t )
Σ _{t < z} g _t ( x , t ) = g ₀ ( x , 0) + g ₁ ( x , 1) + ... + g _z-1 ( x , z -1)

قبل المتابعة، نحتاج إلى تعريف دالة ψ تُسمى " الدالة المُمَثِّلة " للمسند R. تُعرَّف الدالة ψ من المدخلات (t = "صحيح"، f = "خطأ") إلى المخرجات (0، 1) ( لاحظ الترتيب! ). في هذه الحالة، تأتي مدخلات ψ، أي {t، f}، من مخرجات R.

ψ(R = t) = 0
ψ(R = f) = 1

يوضح كلين أن μ y _{y < z} R ( y ) يتم تعريفها على النحو التالي؛ نرى أن دالة الضرب Π تعمل مثل عامل OR المنطقي، وأن المجموع Σ يعمل إلى حد ما مثل عامل AND المنطقي ولكنه ينتج {Σ≠0, Σ=0} بدلاً من {1, 0} فقط:

μ y _{y < z} R ( y ) = Σ _{t < z} Π _{s ≤ t} ψ( R ( x , t , s )) =

[ψ( x , 0, 0)] +

[ψ( س , 1, 0) × ψ( س , 1, 1)] +

[ψ( س , 2, 0) × ψ( س , 2, 1) × ψ( س , 2, 2)] +

... +

[ψ( x , z -1, 0) × ψ( x , z -1, 1) × ψ( x , z -1, 2) × . . . × ψ ( x , z -1, z -1)]

لاحظ أن Σ هي في الواقع دالة تكرارية أولية، حيث أساسها Σ( x , 0) = 0 وخطوة الاستقراء Σ( x , y + 1) = Σ( x , y ) + Π( x , y ). والناتج Π هو أيضًا دالة تكرارية أولية، حيث أساسها Π( x , 0) = ψ( x , 0) وخطوة الاستقراء Π( x , y + 1) = Π( x , y ) × ψ( x , y + 1).

تصبح المعادلة أسهل عند النظر إليها من خلال مثال، كما قدمه كلين. لقد ابتكر ببساطة عناصر الدالة الممثلة ψ( R ( y )). وقد خصص للدوال الممثلة χ( y ) بدلاً من ψ( x , y ).

y	0	1	2	3	4	5	6	7= z
χ( y )	1	1	1	0	1	0	0
π( y ) = Π _{s ≤ y} χ( s )	1	1	1	0	0	0	0	0
σ( y ) = Σ _{t < y} π( t )	1	2	3	3	3	3	3	3
أصغر قيمة _لـ y < z بحيث تكون R ( y ) "صحيحة": φ( y ) = μy y _<_z R ( y )				3

المثال 2: عامل μ غير المحدود ليس بدائيًا-تكراريًا

المؤثر μ غير المحدود - الدالة μ y - هو المؤثر الذي يُعرَّف عادةً في النصوص. لكن قد يتساءل القارئ عن سبب بحث المؤثر μ غير المحدود عن دالة R ( x , y ) بحيث تُعطي القيمة صفر ، بدلاً من أي عدد طبيعي آخر.

في حاشية، يسمح مينسكي لمُعامله بالإنهاء عندما تُنتج الدالة الموجودة بداخله تطابقًا مع المعامل " k "؛ هذا المثال مفيد أيضًا لأنه يُظهر تنسيق مؤلف آخر:

"لـ μ _t [φ( t ) = k ]" (ص 210)

سبب استخدام الصفر هو أن المؤثر غير المحدود μ y يُعرَّف بدلالة دالة "الضرب" Π، حيث يُسمح لمؤشرها y "بالتوسع" أثناء بحث المؤثر μ. وكما هو موضح في المثال أعلاه، فإن حاصل ضرب Π _{x < y} لسلسلة من الأعداد ψ( x , 0) *, ..., * ψ( x , y ) يساوي صفرًا عندما يكون أحد عناصرها ψ( x , i ) يساوي صفرًا.

Π _{s < y} = ψ( x , 0) * , ..., * ψ( x , y ) = 0

إذا كان أي ψ( x , i ) = 0 حيث 0 ≤ i ≤ s . وبالتالي فإن Π يعمل كـ AND منطقي.

تُنتج الدالة μ y كمخرج عدد طبيعي واحد y = {0, 1, 2, 3, ...}. ومع ذلك، داخل المؤثر، يمكن أن يظهر أحد حالتين: (أ) دالة نظرية الأعداد χ التي تُنتج عددًا طبيعيًا واحدًا، أو (ب) مُسند R الذي يُنتج إما {t = صحيح، f = خطأ}. (وفي سياق الدوال التكرارية الجزئية ، أقر كلين لاحقًا بنتيجة ثالثة: "μ = غير مُحدد". ^{[ 2 ]} )

يقسم كلين تعريفه للمؤثر μ غير المحدود لمعالجة الحالتين (أ) و(ب). في الحالة (ب)، قبل أن يُستخدم المسند R ( x , y ) في العمليات الحسابية ضمن حاصل الضرب Π، يجب أولًا تطبيق دالة التمثيل χ على ناتجه {t, f} لإنتاج {0, 1}. أما في الحالة (أ)، إذا استُخدم تعريف واحد، فيجب أن تُنتج دالة نظرية الأعداد χ الصفر لتحقيق شرط المؤثر μ. بعد حسم هذه المسألة، يُبرهن كلين في "برهان ثالث" واحد أن كلا النوعين (أ) أو (ب)، بالإضافة إلى المؤثرات التكرارية الأولية الخمسة، يُنتج الدوال التكرارية (الكليّة) ، مع هذا الشرط للدالة الكلية :

بالنسبة لجميع المعلمات x ، يجب تقديم برهان لإظهار أن y موجود بحيث يحقق (أ) μ y ψ( x , y ) أو (ب) μ yR ( x , y ).

يُقر كلين أيضًا بوجود حالة ثالثة (ج) لا تتطلب إثبات "لكل x يوجد y بحيث ψ( x , y )". ويستخدم هذا في برهانه على وجود دوال تكرارية كلية أكثر مما يمكن تعداده؛ انظر الحاشية إثبات الدالة الكلية .

برهان كلين غير رسمي ويستخدم مثالاً مشابهاً للمثال الأول، لكنه أولاً يحول عامل μ إلى شكل مختلف يستخدم "ضرب الحدود" Π الذي يعمل على الدالة χ والذي ينتج عنه عدد طبيعي n ، والذي يمكن أن يكون أي عدد طبيعي، و 0 في الحالة التي يكون فيها اختبار عامل μ "متحققاً".

التعريف المعاد صياغته باستخدام دالة باي:

μ y _{y < z} χ( y ) =

(i): π( x , y ) = Π _{s < y} χ( x , s )
(ii): φ( x ) = τ(π( x , y ), π( x , y' ), y )
(iii): τ( z' , 0, y ) = y ;τ( u , v , w ) غير معرف لـ u = 0 أو v > 0.

هذا أمر دقيق. للوهلة الأولى، تبدو المعادلات وكأنها تستخدم الاستدعاء الذاتي البدائي. لكن كلين لم يزودنا بخطوة أساسية وخطوة استقراء بالصيغة العامة التالية:

الخطوة الأساسية: φ(0, x ) = φ( x )
خطوة الحث: φ(0, x ) = ψ(y, φ(0, x ), x )

لفهم ما يحدث، علينا أولًا أن نتذكر أننا خصصنا مُعاملًا (عددًا طبيعيًا) لكل متغير xᵢ _. ثانيًا، نلاحظ وجود مُعامل لاحق يعمل على تكرار y (أي y' ). ثالثًا، نلاحظ أن الدالة μ y _{y < z} χ( y , x ) تُنتج حالات من χ( y , x ) أي χ(0, x )، χ(1, x )، ... حتى تُصبح إحدى الحالات تساوي صفرًا. رابعًا، عندما تُصبح إحدى الحالات χ( n , x ) تساوي صفرًا، فإنها تُؤدي إلى أن يُصبح الحد الأوسط من τ، أي v = π( x , y' ) يساوي صفرًا. أخيرًا، عندما يُصبح الحد الأوسط v = صفرًا، تُنفذ الدالة μ y _{y < z} χ( y ) السطر (iii) وتتوقف. تم تبديل عرض كلين للمعادلتين (ii) و (iii) لتوضيح هذه النقطة التي يمثلها السطر (iii) مخرجًا - وهو مخرج يتم اتخاذه فقط عندما يجد البحث بنجاح قيمة y لتحقيق χ( y ) ويكون الحد الأوسط π( x , y' ) يساوي 0؛ ثم ينهي العامل بحثه مع τ( z' , 0, y ) = y .

τ(π( x , y ) , π( x , y' ) , y ) ، أي:

τ(π( س , 0), π( س , 1), 0),
τ(π( x , 1), π( x , 2), 1)
τ(π( x , 2), π( x , 3), 2)
τ(π( x , 3), π( x , 4), 3)
... حتى يحدث تطابق عند y = n ثم:
τ( z' , 0, y ) = τ( z' , 0, n ) = n ويتم البحث عن عامل μ.

بالنسبة لمثال كلين "...ضع في اعتبارك أي قيم ثابتة لـ ( x _i , ..., x _n ) واكتب ببساطة 'χ( y )' لـ 'χ( x _i , ..., x _n ), y )'":

y	0	1	2	3	4	5	6	7	إلخ.
χ( y )	3	1	2	0	9	0	1	5	...
π( y ) = Π _{s ≤ y} χ( s )	1	3	3	6	0	0	0	0	...
				↑
أصغر قيمة _لـ y < z بحيث تكون R ( y ) "صحيحة": φ( y ) = μy y _<_z R ( y )				3

مثال 3: تعريف عامل μ غير المحدود بدلالة آلة مجردة

يقدم كل من مينسكي (1967) ص 21 وبولوس-بورغيس-جيفري (2002) ص 60-61 تعريفات للمشغل μ كآلة مجردة ؛ انظر الحاشية تعريفات بديلة لـ μ .

يتبع العرض التوضيحي التالي نموذج مينسكي دون "الخاصية" المذكورة في الحاشية. سيستخدم العرض نموذج آلة عدّ "مُشتق" يرتبط ارتباطًا وثيقًا بمسلمات بيانو والدوال التكرارية الأولية . يتكون النموذج من: (أ) آلة حالة محدودة مع جدول تعليمات وما يُسمى "سجل الحالة" الذي سنُعيد تسميته "سجل التعليمات" (IR)، (ب) عدد قليل من "السجلات" التي لا يمكن أن يحتوي كل منها إلا على عدد طبيعي واحد، (ج) مجموعة تعليمات من أربعة "أوامر" موضحة في الجدول التالي:

فيما يلي، تعني الرموز "[r]" "محتويات"، وتشير "→r" إلى إجراء يتعلق بالسجل r.

تعليمات	ذاكري	الإجراء على السجل (السجلات) "r"	إجراءات سجل التعليمات، IR
سجل CLeaR	CLR ( r )	0 → r	[IR] + 1 → IR
سجل الزيادة	شركة (ر)	[ r ] + 1 → r	[IR] + 1 → IR
انتقل إذا كان متساويًا	JE (r ₁ , r ₂ , z)	لا أحد	إذا كان [r1 _] = [r2 _] فإن z → IR، وإلا فإن [IR] + 1 → IR
وقف	ح	لا أحد	[ الأشعة تحت الحمراء ] → الأشعة تحت الحمراء

تقوم خوارزمية عامل التصغير μ y [φ( x , y )]، في جوهرها، بإنشاء سلسلة من حالات الدالة φ( x , y ) مع ازدياد قيمة المعامل y (وهو عدد طبيعي)؛ وتستمر هذه العملية (انظر الملاحظة † أدناه) حتى يحدث تطابق بين مخرجات الدالة φ( x , y ) وعدد محدد مسبقًا (عادةً 0). وبالتالي، يتطلب تقييم φ( x , y ) في البداية، تعيين عدد طبيعي لكل متغير من متغيراتها x، وتعيين "رقم تطابق" (عادةً 0) للمسجل " w "، ورقم (عادةً 0) للمسجل y .

ملاحظة †: سيستمر عامل μ غير المحدود في عملية محاولة المطابقة هذه إلى ما لا نهاية أو حتى يتم العثور على تطابق. لذا، يجب أن يكون سجل " y " غير محدود - أي يجب أن يكون قادرًا على "استيعاب" رقم ذي حجم عشوائي. على عكس نموذج الحاسوب "الحقيقي"، تسمح نماذج الآلات المجردة بذلك. في حالة عامل μ المحدود ، سيبدأ عامل μ ذو الحد الأدنى بمحتويات y مضبوطة على رقم غير الصفر. سيتطلب عامل μ ذو الحد الأعلى سجلًا إضافيًا "ub" لاحتواء الرقم الذي يمثل الحد الأعلى بالإضافة إلى عملية مقارنة إضافية؛ يمكن للخوارزمية أن توفر كلا الحدين الأدنى والأعلى.

فيما يلي، نفترض أن سجل التعليمات (IR) يصادف "الروتين" μ y عند رقم التعليمات " n ". أول إجراء له هو إنشاء رقم في سجل " w " مخصص - وهو "مثال" على الرقم الذي يجب أن تنتجه الدالة φ( x , y ) قبل أن تتمكن الخوارزمية من الإنهاء (عادةً ما يكون هذا الرقم هو الصفر، ولكن انظر الحاشية حول استخدام أرقام أخرى غير الصفر). الإجراء التالي للخوارزمية عند رقم التعليمات " n +1" هو مسح سجل " y " - حيث سيعمل " y " كعداد تصاعدي يبدأ من 0. ثم عند رقم التعليمات " n +2"، تُقيّم الخوارزمية دالتها φ( x , y ) - نفترض أن هذا يتطلب j تعليمات لإنجازه - وفي نهاية تقييمها، تُودع φ( x , y) ناتجها في السجل "φ". في التعليمة ( n + j +3)rd، تقارن الخوارزمية الرقم الموجود في سجل " w " (على سبيل المثال 0) بالرقم الموجود في سجل "φ" - إذا كانا متطابقين، فقد نجحت الخوارزمية وتخرج من خلال exit ؛ وإلا فإنها تزيد محتويات سجل " y " وتعود مرة أخرى مع قيمة y الجديدة لاختبار الدالة φ( x , y ) مرة أخرى.

الأشعة تحت الحمراء		تعليمات	إجراءات التسجيل	إجراء على سجل التعليمات IR
ن	μ y [φ( x , y )]:	CLR ( w )	0 → w	[IR] + 1 → IR
ن + 1		CLR ( y )	0 → y	[IR] + 1 → IR
ن +2	حلقة:	φ( x , y )	φ([ x ], [ y ]) → φ	[IR] + j + 1 → IR
ن + ي + 3		JE (φ, w , exit)	لا أحد	الحالة: { إذا كان [φ] = [ w ] ، فاخرج → IR، وإلا [IR] + 1 → IR}
ن + ي + 4		INC ( y )	[ y ] + 1 → y	[IR] + 1 → IR
ن + ي + 5		JE (0, 0, loop)	قفزة غير مشروطة	الحالة: { إذا كان [ r ₀ ] = [ r ₀ ] ، فقم بالتكرار → IR، وإلا فقم بالتكرار → IR }
ن + ي +6	مخرج:	إلخ.

انظر أيضاً

الحواشي

عرض توضيحي للوظائف الكاملة

ما هو إلزامي لكي تكون الدالة دالة كلية هو إثبات بطريقة أخرى (مثل الاستقراء ) أنه لكل مجموعة من قيم معلماتها x _i، سيحقق عدد طبيعي y عامل μ بحيث يمكن إنهاء الخوارزمية التي تمثل الحساب:

"...يجب علينا دائمًا التريث قبل افتراض أن نظام المعادلات يُعرّف دالة عامة تكرارية (أي كلية). عادةً ما نحتاج إلى أدلة إضافية على ذلك، مثلاً في شكل برهان استقرائي يُثبت أن الحساب، لكل قيمة من قيم الوسيط، ينتهي بقيمة فريدة." (مينسكي (1967)، ص 186)

"بمعنى آخر، لا ينبغي لنا أن ندعي أن الدالة قابلة للحساب بشكل فعال على أساس أنها قد ثبت أنها عامة (أي شاملة) تكرارية، ما لم يكن البرهان على أنها عامة تكرارية فعالاً." (Kleene (1952) ص 319)

للاطلاع على مثال عملي لما يعنيه هذا، انظر الأمثلة في قسم الدوال التكرارية العامة . حتى أبسط خوارزمية طرح مختصرة " س - ص = د " قد تُنتج، في الحالات غير المُعرَّفة عندما س < ص ، ما يلي: (1) عدم وجود إنهاء، (2) عدم وجود أعداد (أي وجود خطأ في التنسيق بحيث لا يُعتبر الناتج عددًا طبيعيًا)، أو (3) تضليل: أعداد خاطئة بالتنسيق الصحيح. تتطلب خوارزمية الطرح "الصحيحة" عناية فائقة بجميع "الحالات".

( x , y ) = {(0, 0), ( a , 0), (0, b ), ( a ≥ b , b ), ( a = b , b ), ( a < b , b )}.

لكن حتى بعد إثبات أن الخوارزمية تُنتج المخرجات المتوقعة في الحالات {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}، يبقى لدينا شعورٌ بالقلق إلى أن نتمكن من ابتكار "برهانٍ مقنع" يُثبت أن الحالات ( x , y ) = ( n , m ) تُعطي جميعها النتائج المتوقعة. وبالعودة إلى نقطة كلين: هل "برهاننا" (أي الخوارزمية التي نمثلها في هذا البرهان) مقنعٌ بما يكفي ليُعتبر فعالاً ؟

نماذج الآلة المجردة البديلة للمؤثر μ غير المحدود من مينسكي (1967) وبولوس-بورغيس-جيفري (2002)

يُعرّف مينسكي (1967) في الصفحة 210 عامل μ غير المحدود، لكن مع عيبٍ غريب: لن يُعطي العامل t = 0 عند تحقق شرطه (اختبار IF-THEN-ELSE)، بل يُعطي t = 2. في صيغة مينسكي، العداد هو " t "، والدالة φ( t , x ) تُخزّن قيمته في المسجل φ. في تعريف μ المعتاد، يحتوي المسجل w على 0، لكن مينسكي يُشير إلى أنه يُمكن أن يحتوي على أي عدد k . مجموعة تعليمات مينسكي مُكافئة لما يلي، حيث "JNE" = الانتقال إلى z إذا لم يكن متساويًا:

{ CLR ( r ), INC ( r ), JNE ( r _j , rk _, z ) }

الأشعة تحت الحمراء		تعليمات	إجراءات التسجيل	إجراءات سجل التعليمات، IR
ن	μ y φ( x ):	CLR ( w )	0 → w	[IR] + 1 → IR
ن + 1		CLR ( t )	0 → t	[IR] + 1 → IR
ن +2	حلقة:	φ ( y , x )	φ( [ t ], [ x ] ) → φ	[IR] + j + 1 → IR
ن + ي + 3		INC ( t )	[ t ] + 1 → t	[IR] + 1 → IR
ن + ي + 4		JNE (φ, w , loop)	لا أحد	الحالة: { إذا كان [φ] ≠ [ w ] ، فإن "خروج" → IR، وإلا فإن [IR] + 1 → IR }
ن + ي + 5		INC ( t )	[ t ] + 1 → t	[IR] + 1 → IR
ن + ي +6	مخرج:	إلخ.

كما تم تعريف عامل μ غير المحدود بواسطة Boolos-Burgess-Jeffrey (2002) ص 60-61 لآلة عداد ذات مجموعة تعليمات مكافئة لما يلي:

{ CLR (r), INC (r), DEC (r), JZ (r, z), H }

في هذه النسخة، يُسمى العداد "y" بـ "r2"، وتُخزّن الدالة f( x , r2) قيمته في المسجل "r3". ولعلّ السبب في قيام خوارزمية Boolos-Burgess-Jeffrey بمسح r3 هو تسهيل الانتقال غير المشروط إلى الحلقة ؛ ويتم ذلك غالبًا باستخدام مسجل مخصص "0" يحتوي على القيمة "0".

الأشعة تحت الحمراء		تعليمات	إجراءات التسجيل	إجراءات سجل التعليمات، IR
ن	μ _{r ₂} [f( x , r ₂ )]:	CLR ( r ₂ )	0 → r ₂	[IR] + 1 → IR
ن + 1	حلقة:	f( y , x )	f([ t ], [ x ]) → r ₃	[IR] + j + 1 → IR
ن +2		JZ ( r ₃ , exit )	لا أحد	إذا كان [ r3 _] = 0 ، فاخرج → IR، وإلا فاخرج + 1 → IR
ن + ي + 3		CLR ( r ₃ )	0 → r ₃	[IR] + 1 → IR
ن + ي + 4		شركة ( ر ₂ )	[ r ₂ ] + 1 → r ₂	[IR] + 1 → IR
ن + ي + 5		JZ ( r ₃ , loop)		الحالة: { إذا كان [ r ₃ ] = 0 ، فقم بالتكرار → IR، وإلا [IR] + 1 → IR }
ن + ي +6	مخرج:	إلخ.

مراجع

↑ كولينباخ (2005) .
↑ الصفحات 332 وما بعدها

كلين، ستيفن (2009) [1952]، مقدمة في ما وراء الرياضيات ، نورث هولاند، ISBN 9780923891572، OCLC 935015457
كولينباخ، أولريش (2005)، الرياضيات العكسية من الرتبة العليا، الرياضيات العكسية 2001 (ملف PDF) ، محاضرات في المنطق، مطبعة جامعة كامبريدج ، الصفحات 281-295 ، CiteSeerX 10.1.1.643.551 ، doi : 10.1017/9781316755846.018 ، ISBN 9781316755846انظر التعريف 3.8 والفرضية 3.9.
مينسكي، مارفن ل. (1972) [1967]، الحوسبة: الآلات المحدودة واللامحدودة ، برنتيس هول، ISBN 9780131654495OCLC 974146753

في الصفحات 210-215 يوضح مينسكي كيفية إنشاء عامل μ باستخدام نموذج آلة التسجيل ، وبالتالي إثبات تكافؤه مع الدوال التكرارية العامة .

بولوس، جورج ؛ بورغيس، جون ؛ جيفري، ريتشارد (2002)، "S6.2 التصغير" ، الحوسبة والمنطق (الطبعة الرابعة )، مطبعة جامعة كامبريدج، ص 70-71 ، ISBN 9780521701464

[FOOTNOTEKohlenbach2005-1] كولينباخ (2005) .

[2] الصفحات 332 وما بعدها

[

[ 2 ]