نظرية بوست

تشغيل آلة تورينج${\displaystyle T}$عند الإدخال${\displaystyle n}$يمكن صياغتها منطقيًا في حساب الدرجة الأولى . على سبيل المثال، قد نستخدم الرموز${\displaystyle A_{k}}$،${\displaystyle B_{k}}$، و${\displaystyle C_{k}}$بالنسبة لتكوين الشريط وحالة الجهاز وموقعه على طول الشريط بعد${\displaystyle k}$الخطوات، على التوالي.${\displaystyle T}$يحدد نظام الانتقال العلاقة بين${\displaystyle (A_{k},B_{k},C_{k})}$و${\displaystyle (A_{k+1},B_{k+1},C_{k+1})}$قيمها الأولية (لـ${\displaystyle k=0}$تمثل ) المدخلات والحالة الابتدائية والصفر على التوالي. تتوقف الآلة إذا وفقط إذا كان هناك رقم${\displaystyle k}$بحيث${\displaystyle B_{k}}$هي حالة التوقف.

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

في حالة${\displaystyle T}$يتوقف في وقت${\displaystyle n_{1}}$العلاقة بين${\displaystyle (A_{k},B_{k},C_{k})}$و${\displaystyle (A_{k+1},B_{k+1},C_{k+1})}$يجب أن يتحقق هذا الشرط فقط عندما تكون قيمة k محدودة من الأعلى بـ${\displaystyle n_{1}}$.

وبالتالي توجد صيغة${\displaystyle \varphi (n,n_{1})}$في الحساب من الدرجة الأولى بدون مُكمِّمات غير محدودة ، بحيث${\displaystyle T}$يتوقف عند الإدخال${\displaystyle n}$في أغلب الأحيان${\displaystyle n_{1}}$إذا وفقط إذا${\displaystyle \varphi (n,n_{1})}$راضٍ.

على سبيل المثال، بالنسبة لآلة تورينج الخالية من البادئات والتي تستخدم أبجدية ثنائية ولا تحتوي على رمز فارغ، يمكننا استخدام الرموز التالية:

• ${\displaystyle A_{k}}$هو الرمز 1 لتكوين الشريط بأكمله بعد${\displaystyle k}$الخطوات (والتي يمكننا كتابتها كرقم يبدأ بالبت الأقل أهمية، حيث تكون قيمة الموقع رقم m على الشريط هي البت الأقل أهمية رقم m ). على وجه الخصوص${\displaystyle A_{0}}$يمثل هذا التكوين الأولي للشريط، والذي يتوافق مع المدخلات إلى الجهاز.
• ${\displaystyle B_{k}}$هو الرمز الأحادي لحالة آلة تورينج بعد${\displaystyle k}$خطوات. على وجه الخصوص،${\displaystyle B_{0}=q_{I}}$، الحالة الأولية لآلة تورينج.
• ${\displaystyle C_{k}}$الرمز 1 هو رمز موقع آلة تورينج على الشريط بعد${\displaystyle k}$خطوات. على وجه الخصوص${\displaystyle C_{0}=0}$.
• ${\displaystyle M(q,b)}$هي دالة الانتقال لآلة تورينج، مكتوبة كدالة من زوج (حالة الآلة، بت تمت قراءته بواسطة الآلة) إلى ثلاثية (حالة الآلة الجديدة، بت تمت كتابته بواسطة الآلة، حركة الآلة +1 أو -1 على طول الشريط).
• ${\displaystyle bit(j,m)}$يمثل البت رقم j من العدد${\displaystyle m}$. يمكن كتابة هذا كصيغة حسابية من الدرجة الأولى بدون محددات كمية غير محدودة.

بالنسبة لآلة تورينج الخالية من البادئات، يمكننا استخدام التكوين الأولي للشريط للمدخل n${\displaystyle t(n)=cat(2^{ceil(log_{2}n)}-1,0,n)}$حيث يرمز cat إلى الربط؛ وبالتالي${\displaystyle t(n)}$هو${\displaystyle \log(n)}$سلسلة نصية بطول - من${\displaystyle 1-s}$ثم يتبع ذلك${\displaystyle 0}$ثم بواسطة${\displaystyle n}$.

تشغيل آلة تورينج في البداية${\displaystyle n_{1}}$وبالتالي، يمكن كتابة الخطوات على أنها اقتران بين الشروط الأولية والصيغ التالية، التي تم تحديدها كميًا على${\displaystyle k}$للجميع${\displaystyle k<n_{1}}$:

• ${\displaystyle (B_{k+1},bit(C_{k},A_{k+1}),D)=M(B_{k},bit(C_{k},A_{k}))}$بما أن M لها نطاق محدود، يمكن استبدال ذلك بصيغة حسابية من الدرجة الأولى خالية من المُكمِّمات. ومن الواضح أن الصيغة الدقيقة تعتمد على M.
• ${\displaystyle C_{k+1}=C_{k}+D}$
• ${\displaystyle \forall j:j\neq C_{k}\rightarrow bit(j,A_{k+1})=bit(j,A_{k})}$لاحظ أنه في البداية${\displaystyle n_{1}}$خطوات،${\displaystyle T}$لا يصل أبدًا إلى موقع على طول الشريط أكبر من${\displaystyle n_{1}}$وبالتالي، يمكن تحديد الكمية الشاملة على j بواسطة${\displaystyle n_{1}}$+1، لأن البتات التي تقع بعد هذا الموقع ليس لها أي صلة بتشغيل الجهاز.

يتوقف T عند الإدخال${\displaystyle n}$في أغلب الأحيان${\displaystyle n_{1}}$إذا وفقط إذا${\displaystyle \varphi (n,n_{1})}$يتحقق الشرط التالي:

${\displaystyle {\begin{aligned}\varphi (n,n_{1})=&(A_{0}=t(n))\land (B_{0}=q_{I})\land (C_{0}=0)\land (B_{n_{1}}=q_{H})\\&\land \forall k<n_{1}:((B_{k+1},bit(C_{k},A_{k+1}),1)=M(B_{k},bit(C_{k},A_{k}))\land C_{k+1}=C_{k}+1)&\\&\lor ((B_{k+1},bit(C_{k},A_{k+1}),-1)=M(B_{k},bit(C_{k},A_{k}))\land C_{k+1}=C_{k}-1))&\\&\land \forall j<n_{1}+1:j\neq C_{k}\rightarrow (bit(j,A_{k+1})=bit(j,A_{k}))&\end{aligned}}}$

هذه صيغة حسابية من الدرجة الأولى بدون مُكمِّمات غير محدودة، أي أنها في${\displaystyle \Sigma _{0}^{0}}$.

يترك${\displaystyle S}$لتكن مجموعة يمكن تعدادها حسابيًا بواسطة آلة تورينج . إذن توجد آلة تورينج${\displaystyle T}$بحيث يكون لكل${\displaystyle n}$،${\displaystyle T}$يتوقف عند إعطاء${\displaystyle n}$كمدخل إذا وفقط إذا${\displaystyle n}$هو في${\displaystyle S}$.

يمكن صياغة ذلك رسميًا باستخدام الصيغة الحسابية من الدرجة الأولى المذكورة أعلاه. أعضاء${\displaystyle S}$الأرقام${\displaystyle n}$بما يحقق الصيغة التالية:

${\displaystyle \exists n_{1}:\varphi (n,n_{1})}$

هذه الصيغة موجودة في${\displaystyle \Sigma _{1}^{0}}$. لذلك،${\displaystyle S}$هو في${\displaystyle \Sigma _{1}^{0}}$وبالتالي فإن كل مجموعة قابلة للتعداد الحسابي تقع في${\displaystyle \Sigma _{1}^{0}}$.

والعكس صحيح أيضاً: لكل صيغة${\displaystyle \varphi (n)}$في${\displaystyle \Sigma _{1}^{0}}$باستخدام k من المحددات الوجودية، يمكننا تعداد${\displaystyle k}$قم بتكوين مجموعات من الأعداد الطبيعية، وشغّل آلة تورينج التي تفحصها جميعًا حتى تجد أن الصيغة مُحققة. تتوقف آلة تورينج هذه عند مجموعة الأعداد الطبيعية التي تُحقق الصيغة.${\displaystyle \varphi (n)}$وبالتالي يقوم بتعداد مجموعته المقابلة.

وبالمثل، فإن تشغيل آلة أوراكل${\displaystyle T}$مع أوراكل O يتوقف بعد أكثر من${\displaystyle n_{1}}$رد على المدخلات${\displaystyle n}$يمكن وصفها بصيغة من الدرجة الأولى${\displaystyle \varphi _{O}(n,n_{1})}$باستثناء الصيغة${\displaystyle \varphi _{1}(n,n_{1})}$يشمل الآن:

• مسند جديد،${\displaystyle O_{m}}$، مما يعطي الإجابة المطلوبة. يجب أن يحقق هذا الشرط صيغة معينة سيتم مناقشتها لاحقًا.
• شريط إضافي - شريط العرافة - عليه${\displaystyle T}$يجب كتابة العدد m لكل استدعاء O ( m ) إلى جهاز التنبؤ؛ ويمكن صياغة الكتابة على هذا الشريط منطقيًا بطريقة مشابهة للكتابة على شريط الجهاز. لاحظ أن جهاز التنبؤ الذي يتوقف بعد أكثر من${\displaystyle n_{1}}$لا يملك ستيبس الوقت الكافي للكتابة على الأكثر${\displaystyle n_{1}}$الأرقام الموجودة على شريط أوراكل. لذا لا يمكن استدعاء أوراكل إلا بالأرقام m التي تحقق الشرط التالي:${\displaystyle m<2^{n_{1}}}$.

إذا كان الهدف من استخدام أداة التنبؤ هو حل مشكلة اتخاذ قرار ،${\displaystyle O_{m}}$تكون الإجابة دائمًا "نعم" أو "لا"، والتي يمكننا صياغتها رسميًا على أنها 0 أو 1. لنفترض أن مشكلة القرار نفسها يمكن صياغتها رسميًا بواسطة صيغة حسابية من الدرجة الأولى${\displaystyle \psi ^{O}(m)}$. ثم${\displaystyle T}$يتوقف عند${\displaystyle n}$على الأكثر${\displaystyle n_{1}}$الخطوات إذا وفقط إذا تحققت الصيغة التالية: ${\displaystyle \varphi _{O}(n,n_{1})=\forall m<2^{n_{1}}:((\psi ^{O}(m)\rightarrow (O_{m}=1))\land (\lnot \psi ^{O}(m)\rightarrow (O_{m}=0)))\land {\varphi _{O}}_{1}(n,n_{1})}$

أين${\displaystyle {\varphi _{O}}_{1}(n,n_{1})}$هي صيغة من الدرجة الأولى بدون محددات كمية غير محدودة.

إذا كان O بمثابة وسيط لحل مشكلة توقف الآلة${\displaystyle T'}$، ثم${\displaystyle \psi ^{O}(m)}$هو نفسه "يوجد"${\displaystyle m_{1}}$بحيث${\displaystyle T'}$بدءاً من المدخل m، يكون في حالة التوقف بعد${\displaystyle m_{1}}$خطوات". وهكذا: ${\displaystyle \psi ^{O}(m)=\exists m_{1}:\psi _{H}(m,m_{1})}$ أين${\displaystyle \psi _{H}(m,m_{1})}$هي صيغة من الدرجة الأولى تُضفي الطابع الرسمي على${\displaystyle T'}$. لو${\displaystyle T'}$هي آلة تورينج (بدون أوراكل)،${\displaystyle \psi _{H}(m,m_{1})}$هو في${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}}$(أي أنه لا يحتوي على محددات كمية غير محدودة).

بما أن هناك عددًا محدودًا من الأعداد m التي تحقق${\displaystyle m<2^{n_{1}}}$، يمكننا اختيار نفس عدد الخطوات لجميعها: هناك عدد${\displaystyle m_{1}}$بحيث${\displaystyle T'}$يتوقف بعد${\displaystyle m_{1}}$خطوات دقيقة على تلك المدخلات${\displaystyle m<2^{n_{1}}}$والتي تتوقف من أجلها على الإطلاق.

بالانتقال إلى الصيغة الطبيعية السابقة ، نجد أن آلة أوراكل تتوقف عند الإدخال${\displaystyle n}$إذا وفقط إذا تحققت الصيغة التالية: ${\displaystyle \varphi (n)=\exists n_{1}\exists m_{1}\forall m_{2}:(\psi _{H}(m,m_{2})\rightarrow (O_{m}=1))\land (\lnot \psi _{H}(m,m_{1})\rightarrow (O_{m}=0)))\land {\varphi _{O}}_{1}(n,n_{1})}$

(بشكل غير رسمي، هناك "عدد أقصى من الخطوات")${\displaystyle m_{1}}$مثل كل وحي لا يتوقف في الأول${\displaystyle m_{1}}$الخطوات لا تتوقف على الإطلاق؛ ومع ذلك، لكل${\displaystyle m_{2}}$كل عراف يتوقف بعد${\displaystyle m_{2}}$(تتوقف الخطوات).

لاحظ أنه قد نستبدل كليهما${\displaystyle n_{1}}$و${\displaystyle m_{1}}$بمقدار رقم واحد - وهو الحد الأقصى لها - دون تغيير قيمة الصواب لـ${\displaystyle \varphi (n)}$وهكذا يمكننا أن نكتب: ${\displaystyle \varphi (n)=\exists n_{1}\forall m_{2}:(\psi _{H}(m,m_{2})\rightarrow (O_{m}=1))\land (\lnot \psi _{H}(m,n_{1})\rightarrow (O_{m}=0)))\land {\varphi _{O}}_{1}(n,n_{1})}$

للحصول على حل لمشكلة التوقف في آلات تورينج،${\displaystyle \psi _{H}(m,m_{1})}$هو في${\displaystyle \Pi _{0}^{0}}$و${\displaystyle \varphi (n)}$هو في${\displaystyle \Sigma _{2}^{0}}$وبالتالي، فإن كل مجموعة قابلة للحساب والتعداد بواسطة آلة أوراكل مع أوراكل لـ${\displaystyle \emptyset ^{(1)}}$، موجود في${\displaystyle \Sigma _{2}^{0}}$.

والعكس صحيح أيضاً: لنفترض${\displaystyle \varphi (n)}$هي صيغة في${\displaystyle \Sigma _{2}^{0}}$مع${\displaystyle k_{1}}$أدوات التحديد الوجودي متبوعة بـ${\displaystyle k_{2}}$المُكمِّمات الشاملة. أو بعبارة أخرى،${\displaystyle \varphi (n)}$لديه${\displaystyle k_{1}}$> أدوات التحديد الوجودية متبوعة بنفي صيغة في${\displaystyle \Sigma _{1}^{0}}$يمكن تعداد الصيغة الأخيرة بواسطة آلة تورينج، وبالتالي يمكن التحقق منها فورًا بواسطة وسيط.${\displaystyle \emptyset ^{(1)}}$.

وبذلك يمكننا تعداد${\displaystyle k_{1}}$- مجموعات من الأعداد الطبيعية وتشغيل آلة أوراكل مع أوراكل لـ${\displaystyle \emptyset ^{(1)}}$ثم يمر هذا الجهاز بجميعها حتى يجد حلاً مناسباً للمعادلة. ويتوقف عند مجموعة الأعداد الطبيعية التي تحقق هذا الشرط تحديداً.${\displaystyle \varphi (n)}$وبالتالي يقوم بتعداد مجموعته المقابلة.

بشكل أعم، لنفترض أن كل مجموعة قابلة للحساب والتعداد بواسطة آلة أوراكل مع أوراكل لـ${\displaystyle \emptyset ^{(p)}}$هو في${\displaystyle \Sigma _{p+1}^{0}}$ثم بالنسبة لآلة أوراكل مع أوراكل لـ${\displaystyle \emptyset ^{(p+1)}}$،${\displaystyle \psi ^{O}(m)=\exists m_{1}:\psi _{H}(m,m_{1})}$هو في${\displaystyle \Sigma _{p+1}^{0}}$.

منذ${\displaystyle \psi ^{O}(m)}$هو نفسه${\displaystyle \varphi (n)}$بالنسبة لقفزة تورينج السابقة، يمكن بناؤها (كما فعلنا للتو مع${\displaystyle \varphi (n)}$أعلاه) بحيث${\displaystyle \psi _{H}(m,m_{1})}$في${\displaystyle \Pi _{p}^{0}}$بعد الانتقال إلى الشكل الرسمي السابق، الجديد${\displaystyle \varphi (n)}$هو في${\displaystyle \Sigma _{p+2}^{0}}$.

بالاستقراء، كل مجموعة قابلة للحساب والتعداد بواسطة آلة أوراكل مع أوراكل لـ${\displaystyle \emptyset ^{(p)}}$، موجود في${\displaystyle \Sigma _{p+1}^{0}}$.

ويمكن إثبات الاتجاه الآخر بالاستقراء أيضًا: لنفترض أن كل صيغة في${\displaystyle \Sigma _{p+1}^{0}}$يمكن تعدادها بواسطة آلة أوراكل مزودة بأوراكل لـ${\displaystyle \emptyset ^{(p)}}$.

والآن لنفترض${\displaystyle \varphi (n)}$هي صيغة في${\displaystyle \Sigma _{p+2}^{0}}$مع${\displaystyle k_{1}}$أدوات التحديد الوجودي متبوعة بـ${\displaystyle k_{2}}$المُكمِّمات الشاملة وما إلى ذلك. أو ما يُعادلها،${\displaystyle \varphi (n)}$لديه${\displaystyle k_{1}}$> أدوات التحديد الوجودية متبوعة بنفي صيغة في${\displaystyle \Sigma _{p+1}^{0}}$يمكن تعداد الصيغة الأخيرة بواسطة آلة أوراكل مزودة بأوراكل لـ${\displaystyle \emptyset ^{(p)}}$وبالتالي يمكن التحقق منها فورًا بواسطة وسيط روحي لـ${\displaystyle \emptyset ^{(p+1)}}$.

وبذلك يمكننا تعداد${\displaystyle k_{1}}$- مجموعات من الأعداد الطبيعية وتشغيل آلة أوراكل مع أوراكل لـ${\displaystyle \emptyset ^{(p+1)}}$ثم يمر هذا الجهاز بجميعها حتى يجد حلاً مناسباً للمعادلة. ويتوقف عند مجموعة الأعداد الطبيعية التي تحقق هذا الشرط تحديداً.${\displaystyle \varphi (n)}$وبالتالي يقوم بتعداد مجموعته المقابلة.