أطروحة تشيرش-تورينغ

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

في عام 1933، قام كورت غودل ، مع جاك هيربراند ، بصياغة تعريف فئة الدوال التكرارية العامة : أصغر فئة من الدوال (ذات عدد كبير من الوسائط) المغلقة تحت التركيب والتكرار والتصغير ، وتشمل الصفر والخلف وجميع الإسقاطات .
في عامي 1932-1933، ^ابتكر^ألونسو^تشيرش طريقةً لتعريف الدوال تُسمى حساب لامدا . ضمن حساب لامدا، عرّف ترميزًا للأعداد الطبيعية يُسمى أرقام تشيرش . تُسمى الدالة على الأعداد الطبيعية قابلةً للحساب باستخدام لامدا إذا أمكن تمثيل الدالة المقابلة لها على أرقام تشيرش بواسطة حدٍّ من حساب لامدا.
في عامي 1935-1936، قام ألونزو تشيرش ^{[ 7 ]} بصياغة مفهوم الدوال القابلة للحساب بشكل فعال من خلال اقتراح أنها دوال تكرارية عامة، أو بشكل مكافئ، دوال قابلة للتعريف بواسطة λ.
في عام ١٩٣٦، وقبل اطلاعه على أعمال تشرش، ^{[ ١٢ ]} ابتكر آلان تورينج نموذجًا نظريًا للآلات، التي تُعرف الآن بآلات تورينج، والقادرة على إجراء العمليات الحسابية من خلال معالجة الرموز على شريط. وبوجود ترميز مناسب للأعداد الطبيعية على شكل متواليات من الرموز، تُسمى الدالة على الأعداد الطبيعية قابلة للحساب بواسطة تورينج إذا تمكنت آلة تورينج من حساب الدالة المقابلة على الأعداد الطبيعية المُرمّزة. واقترح تورينج تعريف الدوال القابلة للحساب فعليًا بأنها تلك التي تكون قابلة للحساب بواسطة تورينج.

أثبت كلٌّ من تشرش ^{[ 13 ]} ، وكلين ^{[ 14 ]} ، وتورينج ^{[ 15 ]}^{[ 17 ]} أن هذه الفئات الثلاث المُعرَّفة رسميًا للدوال القابلة للحساب تتطابق: فالدالة قابلة للحساب من نوع λ إذا وفقط إذا كانت قابلة للحساب من نوع تورينج، وإذا وفقط إذا كانت عامة تكرارية . وقد دفع هذا علماء الرياضيات وعلوم الحاسوب إلى الاعتقاد بأن مفهوم قابلية الحساب يُوصَف بدقة من خلال هذه العمليات الثلاث المتكافئة. وقد عززت محاولات رسمية أخرى لتوصيف قابلية الحساب هذا الاعتقاد لاحقًا (انظر أدناه ).

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

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

بيان بكلمات تشيرش وتورينج

يتناول جيه بي روسر ( 1939 ) مفهوم "الحسابية الفعّالة" على النحو التالي: "من الواضح أن وجود برهاني تشرش وروسر [أي البرهاني التي تثبت عدم وجود طريقة فعّالة لتحديد الحقيقة] يفترض تعريفًا دقيقًا لكلمة "فعّال". ويُستخدم مصطلح "الطريقة الفعّالة" هنا بمعنى خاص، وهو طريقة تكون كل خطوة من خطواتها محددة مسبقًا بدقة، ومن المؤكد أنها ستُنتج الإجابة في عدد محدود من الخطوات". ^[¹⁸^] وبالتالي، يُستخدم الظرف-الصفة "فعّال" بمعنى "1أ: إحداث تأثير حاسم أو مرغوب فيه"، و"قادر على إنتاج نتيجة". ^[¹⁹^]^[²⁰^]

فيما يلي، تعني عبارة "قابل للحساب بفعالية" "مُنتَج بأي وسيلة فعّالة بديهيًا"، بينما تعني عبارة "قابل للحساب بفعالية" "مُنتَج بواسطة آلة تورينج أو جهاز ميكانيكي مكافئ". وتتطابق "تعريفات" تورينج الواردة في حاشية أطروحته للدكتوراه عام 1938 بعنوان " أنظمة المنطق القائمة على الأعداد الترتيبية" ، والتي أشرف عليها تشرش، تقريبًا مع التعريفات الواردة في الحاشية.

^† سنستخدم مصطلح "الدالة القابلة للحساب" للدلالة على دالة يمكن حسابها بواسطة آلة، وسنستخدم مصطلح "قابلة للحساب فعلياً" للإشارة إلى الفكرة البديهية دون تحديدها بشكل خاص بأي من هذه التعريفات. ^{[ 21 ]}

يمكن صياغة هذه الفرضية على النحو التالي: كل دالة قابلة للحساب فعليًا هي دالة قابلة للحساب . ^{[ 22 ]} كما ذكر تشرش أيضًا أنه "لا يُعتبر أي إجراء حسابي خوارزمية إلا إذا أمكن تمثيله كآلة تورينج". ^{[ 23 ]}

قال تورينج ذلك بهذه الطريقة:

ذُكر ... أن "الدالة قابلة للحساب فعليًا إذا أمكن إيجاد قيمها بعملية ميكانيكية بحتة". يمكننا أن نأخذ هذا حرفيًا، مع فهم أن المقصود بعملية ميكانيكية بحتة هي عملية يمكن تنفيذها بواسطة آلة. يؤدي هذا التطور... إلى ... تعريف قابلية الحساب ^† بقابلية الحساب الفعلي. [ ^† هي الحاشية المذكورة أعلاه.] ^{[ 21 ]}

تاريخ

كانت إحدى المشكلات المهمة التي واجهت علماء المنطق في ثلاثينيات القرن العشرين هي مشكلة القرار التي طرحها ديفيد هيلبرت وويلهلم أكرمان ، ^{[ 24 ]} والتي تساءلت عما إذا كانت هناك آلية لفصل الحقائق الرياضية عن الأكاذيب الرياضية. تطلّب هذا المسعى تحديد مفهوم "الخوارزمية" أو "الحسابية الفعّالة" بدقة كافية لبدء البحث. ^{[ 25 ]} لكن منذ البداية، انطلقت محاولات ألونسو تشيرش بنقاش لا يزال مستمرًا حتى اليوم. ^{[ 26 ]} هل يُقصد بمفهوم "الحسابية الفعّالة" ما يلي: (أ) "بديهية أو بديهيات" في نظام بديهي، (ب) مجرد تعريف "يحدد" قضيتين أو أكثر، (ج) فرضية تجريبية يتم التحقق منها من خلال ملاحظة الأحداث الطبيعية، أم (د) مجرد اقتراح من أجل الجدل (أي "أطروحة")؟

حوالي 1930-1952

أثناء دراسة المسألة، قدّم تشرش وطالبه ستيفن كلين مفهوم الدوال القابلة للتعريف وفقًا لـ λ ، وتمكّنا من إثبات أن العديد من فئات الدوال الكبيرة الشائعة في نظرية الأعداد قابلة للتعريف وفقًا لـ λ. ^{[ 27 ]} بدأ النقاش عندما اقترح تشرش على غودل تعريف الدوال "القابلة للحساب فعليًا" على أنها الدوال القابلة للتعريف وفقًا لـ λ. إلا أن غودل لم يقتنع ووصف الاقتراح بأنه "غير مُرضٍ على الإطلاق". ^{[ 28 ]} بل اقترح غودل، في مراسلاته مع تشرش (حوالي 1934-1935)، وضع بديهيات لمفهوم "قابلية الحساب الفعّالة"؛ وفي الواقع، ذكر تشرش في رسالة إلى كلين عام 1935 ما يلي:

كانت فكرته الوحيدة في ذلك الوقت هي أنه قد يكون من الممكن، من حيث قابلية الحساب الفعالة كمفهوم غير محدد، صياغة مجموعة من البديهيات التي من شأنها أن تجسد الخصائص المقبولة عمومًا لهذا المفهوم، والقيام بشيء ما على هذا الأساس. ^{[ 29 ]}

لكن غودل لم يُقدّم أي توجيهات إضافية. وفي نهاية المطاف، اقترح منهجه التكراري، المُعدّل باقتراح هيربراند، والذي كان غودل قد فصّله في محاضراته عام 1934 في برينستون، نيو جيرسي (قام كلين وروسر بنسخ الملاحظات). لكنه لم يعتقد أنه يُمكن تحديد الفكرتين بشكل مُرضٍ "إلا بشكل استدلالي". ^{[ 30 ]}

بعد ذلك، كان من الضروري تحديد وإثبات تكافؤ مفهومين للحساب الفعال. وباستخدام حساب لامدا والتكرار "العام"، قدم كلين، بمساعدة تشرش وج. باركلي روسر، براهين (1933، 1935) تُظهر تكافؤ الحسابين. ثم عدّل تشرش أساليبه لتشمل استخدام تكرار هيربراند-غودل، ثم أثبت (1936) أن مسألة القرار غير قابلة للحل: فلا توجد خوارزمية قادرة على تحديد ما إذا كانت الصيغة الصحيحة تمتلك شكلًا طبيعيًا من نوع بيتا . ^{[ 31 ]}

بعد سنوات عديدة، في رسالة إلى ديفيس (حوالي عام ١٩٦٥)، ذكر غودل أنه "لم يكن مقتنعًا على الإطلاق، وقت إلقاء هذه المحاضرات [١٩٣٤]، بأن مفهومه عن الاستدعاء الذاتي يشمل جميع أنواع الاستدعاء الذاتي الممكنة". ^{[ ٣٢ ]} وبحلول عامي ١٩٦٣-١٩٦٤، تنصل غودل من استدعاء هيربراند-غودل الذاتي وحساب لامدا لصالح آلة تورينغ باعتبارها تعريفًا لـ "الخوارزمية" أو "الإجراء الميكانيكي" أو "النظام الرسمي". ^{[ ٣٣ ]}

فرضية تؤدي إلى قانون طبيعي؟: في أواخر عام 1936، قُدِّمت ورقة آلان تورينج (التي أثبتت أيضًا أن مسألة القرار غير قابلة للحل) شفهيًا، لكنها لم تكن قد نُشرت بعد. ^[³⁴^] من ناحية أخرى، نُشرت ورقة إميل بوست عام 1936 وتم اعتمادها بشكل مستقل عن عمل تورينج. ^[³⁵^] عارض بوست بشدة "تحديد" تشرش للحوسبة الفعالة بحساب لامدا والتكرار، مصرحًا بما يلي:

في الواقع، فإن العمل الذي أنجزه تشيرش وآخرون يتجاوز مرحلة الفرضية العملية بكثير. لكن إخفاء هذا التحديد تحت ستار تعريفٍ ما ... يحجب عنا الحاجة إلى التحقق منه باستمرار. ^{[ 36 ]}

بل اعتبر مفهوم "الحساب الفعال" مجرد "فرضية عمل" قد تقود بالاستدلال الاستقرائي إلى " قانون طبيعي " بدلاً من "تعريف أو بديهية". ^{[ 37 ]} وقد انتقد تشيرش هذه الفكرة بشدة. ^{[ 38 ]}

وهكذا، فإن بوست في ورقته البحثية لعام 1936 كان يستبعد أيضاً اقتراح غودل لتشرش في الفترة 1934-1935 بأن الأطروحة يمكن التعبير عنها كمسلمة أو مجموعة من المسلمات. ^{[ 29 ]}

أضاف تورينج تعريفًا آخر، وساوى روسر بين التعريفات الثلاثة : في غضون فترة وجيزة، نُشرت ورقة تورينج البحثية لعامي 1936-1937 بعنوان "حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار " ^{[ 34 ]} . وقد طرح فيها مفهومًا آخر لـ"الحسابية الفعّالة" مع تقديم آلاته من نوع "أ" (المعروفة الآن باسم نموذج تورينج الحسابي المجرد). وفي ملخص برهان أُضيف كمُلحق لورقته البحثية لعامي 1936-1937، بيّن تورينج أن فئات الدوال المُعرّفة بواسطة حساب لامدا وآلات تورينج تتطابق. ^{[ 39 ]} وسرعان ما أدرك تشرش مدى إقناع تحليل تورينج. وفي مراجعته لورقة تورينج البحثية، أوضح أن مفهوم تورينج جعل "التطابق مع الفعالية بالمعنى العادي (غير المُعرّف صراحةً) واضحًا على الفور". ^{[ 40 ]}

في غضون بضع سنوات (عام 1939)، اقترح تورينج، كما فعل تشيرش وكلين من قبله، أن تعريفه الرسمي لعامل الحوسبة الميكانيكية هو التعريف الصحيح. ^{[ 41 ]} وهكذا، بحلول عام 1939، كان كل من تشيرش (1934) وتورينج (1939) قد اقترحا بشكل فردي أن "أنظمتهما الرسمية" يجب أن تكون تعريفات "للحساب الفعال"؛ ^{[ 42 ]} ولم يصغ أي منهما تصريحاتهما كأطروحات .

حدد روسر (1939) رسمياً المفاهيم الثلاثة كتعريفات:

جميع التعريفات الثلاثة متكافئة، لذا لا يهم أي منها يُستخدم. ^{[ 43 ]}

يقترح كلين الأطروحة الأولى : ترك هذا الأمر التعبير الصريح عن "الأطروحة" لكلين. في عام 1943، اقترح كلين "أطروحته الأولى": ^{[ 44 ]}

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

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

الفرضية الأولى: كل دالة قابلة للحساب بشكل فعال (مسند قابل للتقرير بشكل فعال) هي دالة عامة متكررة . ^{[ 45 ]}

النظرية XXX: الفئات التالية من الدوال الجزئية متطابقة، أي لها نفس الأعضاء: (أ) الدوال الجزئية التكرارية، (ب) الدوال القابلة للحساب ... ^{[ 46 ]}

أطروحة تورينج: إن أطروحة تورينج التي تنص على أن كل دالة يمكن اعتبارها قابلة للحساب بشكل طبيعي قابلة للحساب وفقًا لتعريفه، أي بواسطة إحدى آلاته، تعادل أطروحة تشيرش بموجب النظرية XXX. ^{[ 46 ]}

وأخيرًا، يستخدم كلين لأول مرة مصطلح "أطروحة تشيرش-تورينج" في قسم يساعد فيه على تقديم توضيحات للمفاهيم الواردة في ورقة آلان تورينج "مسألة الكلمات في أنصاف المجموعات مع الإلغاء"، كما طالب بذلك نقد من ويليام بون. ^{[ 47 ]}

التطورات اللاحقة

في محاولة لفهم مفهوم "الحوسبة الفعّالة" بشكل أفضل، قام روبن غاندي (تلميذ تورينغ وصديقه) عام ١٩٨٠ بتحليل الحوسبة الآلية (مقارنةً بالحوسبة البشرية التي تُنفذها آلة تورينغ). وقد دفعه فضوله وتحليله للأتمتة الخلوية (بما في ذلك لعبة الحياة لكونواي )، والتوازي، والأتمتة البلورية، إلى اقتراح أربعة "مبادئ (أو قيود) ... يُقال إن أي آلة يجب أن تستوفيها". ^{[ ٤٨ ]} ويستند مبدأه الرابع والأهم، "مبدأ السببية"، إلى "السرعة المحدودة لانتشار التأثيرات والإشارات؛ إذ يرفض علم الفيزياء المعاصر إمكانية حدوث تأثير فوري عن بُعد". ^{[ 49 ]} انطلاقاً من هذه المبادئ وبعض القيود الإضافية - (1أ) حد أدنى للأبعاد الخطية لأي من الأجزاء، (1ب) حد أعلى لسرعة الانتشار (سرعة الضوء)، (2) تقدم منفصل للآلة، و(3) سلوك حتمي - ينتج نظرية مفادها أن "ما يمكن حسابه بواسطة جهاز يفي بالمبادئ من الأول إلى الرابع قابل للحساب". ^{[ 50 ]}

في أواخر التسعينيات، قام ويلفريد سيغ بتحليل مفهومي تورينغ وغاندي عن "الحسابية الفعّالة" بهدف "صقل المفهوم غير الرسمي، وصياغة سماته العامة بشكل بديهي، ودراسة الإطار البديهي". ^{[ 51 ]} في أعماله المنشورة عامي 1997 و2002، يقدم سيغ سلسلة من القيود على سلوك الحاسوب - "وكيل الحوسبة البشري الذي يعمل بشكل آلي". وتتلخص هذه القيود فيما يلي:

"(ب.1) (الحدودية) هناك حد ثابت لعدد التكوينات الرمزية التي يمكن للكمبيوتر التعرف عليها على الفور.
"(ب.2) (التقييد) هناك حد ثابت لعدد الحالات الداخلية التي يمكن أن يكون عليها الكمبيوتر."
"(L.1) (المحلية) لا يمكن للحاسوب تغيير سوى عناصر التكوين الرمزي المرصود."
"(L.2) (المحلية) يمكن للحاسوب أن يحول الانتباه من تكوين رمزي إلى آخر، ولكن يجب أن تكون التكوينات الجديدة الملاحظة ضمن مسافة محدودة من التكوين الذي تمت ملاحظته مباشرة قبل ذلك."
"(د) (الحتمية) يحدد التكوين (الفرعي) الذي يمكن التعرف عليه على الفور بشكل فريد خطوة الحساب التالية (و id [الوصف الفوري])"؛ بعبارة أخرى: "تحدد الحالة الداخلية للحاسوب مع التكوين المرصود بشكل فريد خطوة الحساب التالية والحالة الداخلية التالية." ^{[ 52 ]}

لا تزال هذه المسألة موضع نقاش مستمر داخل الأوساط الأكاديمية. ^{[ 53 ]}^{[ 54 ]}

تعريف الأطروحة

يمكن اعتبار هذه الأطروحة مجرد تعريف رياضي عادي. تشير تعليقات غودل حول هذا الموضوع إلى هذا الرأي، على سبيل المثال: "لقد أثبت تورينغ التعريف الصحيح للحوسبة الميكانيكية بما لا يدع مجالاً للشك". ^{[ 55 ]} وقد طرح روبرت آي. سواري [ ¹¹^] الحجة القائلة بأن الأطروحة ليست أكثر من مجرد تعريف، حيث جادل أيضًا بأن تعريف تورينغ للحوسبة لا يقل احتمالًا عن تعريف إبسيلون-دلتا للدالة المتصلة من ^حيث صحته .

نجاح الأطروحة

تم اقتراح نماذج أخرى (إلى جانب الاستدعاء الذاتي، وحساب لامدا، وآلة تورينج) لوصف قابلية الحساب/الحسابية الفعالة. أضاف كلين (1952) إلى القائمة الدوال " القابلة للحساب في النظام S1 _{" لكورت غودل (1936)، و"}الأنظمة المعيارية " (أو العادية ) لإميل بوست (1943، 1946) . ^[⁵⁶^] في خمسينيات القرن العشرين، قام هاو وانغ ومارتن ديفيس بتبسيط نموذج آلة تورينج ذي الشريط الواحد بشكل كبير (انظر آلة بوست-تورينج ). قام مارفن مينسكي بتوسيع النموذج إلى شريطين أو أكثر، وبسط الأشرطة بشكل كبير إلى "عدادات تصاعدية-تنازلية"، والتي طورها ميلزاك ولامبيك لاحقًا إلى ما يُعرف الآن بنموذج آلة العداد . في أواخر الستينيات وأوائل السبعينيات، وسّع الباحثون نموذج آلة العدّ ليشمل آلة التسجيل ، وهي قريبة الصلة بالمفهوم الحديث للحاسوب . وتشمل النماذج الأخرى المنطق التوافقي وخوارزميات ماركوف . ويضيف غوريفيتش نموذج آلة المؤشر لكولموغوروف وأوسبنسكي (1953، 1958): "... أرادوا فقط ... إقناع أنفسهم بأنه لا توجد طريقة لتوسيع مفهوم الدالة القابلة للحساب." ^[⁵⁷^]

تتضمن جميع هذه المساهمات براهين على أن النماذج مكافئة حسابيًا لآلة تورينج؛ ويُقال إن هذه النماذج كاملة تورينج . ولأن جميع هذه المحاولات المختلفة لصياغة مفهوم "الحسابية/الإمكانية الحسابية الفعالة" قد أسفرت عن نتائج متكافئة، يُفترض الآن عمومًا أن فرضية تشرش-تورينج صحيحة. في الواقع، اقترح غودل (1936) شيئًا أقوى من ذلك؛ فقد لاحظ أن هناك شيئًا "مطلقًا" في مفهوم "المعقول في S1 _" .

يمكن أيضًا إثبات أن الدالة القابلة للحساب في أحد الأنظمة S _i ، أو حتى في نظام من النوع المتسامي، هي بالفعل قابلة للحساب في S _1. وبالتالي، فإن مفهوم "قابل للحساب" هو مفهوم مطلق بمعنى محدد، بينما تعتمد جميع المفاهيم الرياضية الفوقية المألوفة الأخرى (مثل قابل للإثبات، قابل للتعريف، إلخ) بشكل أساسي على النظام الذي تُعرَّف فيه ... ^{[ 58 ]}

الاستخدام غير الرسمي في البراهين

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

يقدم ديرك فان دالين المثال التالي لتوضيح هذا الاستخدام غير الرسمي لأطروحة تشيرش-تورينغ: ^{[ 60 ]}

مثال: تحتوي كل مجموعة قابلة للتعداد بشكل متكرر لانهائي (RE) على مجموعة متكررة لانهائية .
البرهان: ليكن A مجموعة عشوائية لانهائية. نسرد عناصر A بشكل فعال، n₀ _، n₁ _، n₂ _، n₃ _، ...
من هذه القائمة، نستخرج قائمة فرعية متزايدة: نضع m₀ ₌ n₀ _، وبعد عدد محدود من الخطوات نجد nₖ _بحيث يكون _nₖ > m₀ _، ثم نضع m₁ ₌ nₖ _. نكرر هذه العملية لإيجاد m₂ _> m₁ _، وهكذا. ينتج عن ذلك قائمة فعالة للمجموعة الفرعية B = {m₀ _, m₁ _, m₂ _, ...} من A، مع الخاصية mᵢ _< mᵢ _{+ 1} .
الادعاء : B قابلة للتقرير. لاختبار k في B، يجب التحقق مما إذا كان k = mᵢ _لبعض i. بما أن متتالية mᵢ _{متزايدة} ، علينا إنتاج k+1 عنصرًا على الأكثر من القائمة ومقارنتها بـ k. إذا لم يكن أي منها مساويًا لـ k، فإن k ليس في B. بما أن هذا الاختبار فعال، فإن B قابلة للتقرير، وبحسب فرضية تشيرش ، فهي قابلة للاستدعاء الذاتي.

لجعل المثال السابق دقيقًا تمامًا، سيتعين على المرء بناء آلة تورينج، أو دالة لامدا، أو استخدام بديهيات الاستدعاء الذاتي بعناية، أو في أفضل الأحوال، استخدام نظريات مختلفة من نظرية الحوسبة بذكاء. ولكن لأن عالم نظرية الحوسبة يعتقد أن حوسبة تورينج تُجسد بدقة ما يمكن حسابه بفعالية، ولأن إجراءً فعالًا مُفصَّلًا باللغة الإنجليزية لتحديد المجموعة B، فإن عالم نظرية الحوسبة يقبل هذا كدليل على أن المجموعة استدعاءية بالفعل.

الاختلافات

أدى نجاح فرضية تشرش-تورينج إلى اقتراح صيغ مختلفة منها. فعلى سبيل المثال، تنص فرضية تشرش-تورينج الفيزيائية على ما يلي: "جميع الدوال القابلة للحساب فيزيائيًا قابلة للحساب بواسطة تورينج". ^{[ 61 ]}^{: 101}

لا تتناول فرضية تشيرش-تورينج كفاءة محاكاة نموذج حاسوبي لآخر. فقد ثبت، على سبيل المثال، أن آلة تورينج العالمية (متعددة الأشرطة) لا تعاني إلا من تباطؤ لوغاريتمي عند محاكاة أي آلة تورينج. ^{[ 62 ]}

يتناول أحد أشكال نظرية تشرش-تورينج إمكانية محاكاة نموذج حسابي "معقول" بكفاءة. تُعرف هذه النظرية بنظرية الجدوى ^{[ 63 ]،} وتُعرف أيضًا بنظرية تشرش-تورينج الكلاسيكية في نظرية التعقيد ، أو بنظرية تشرش-تورينج الموسعة ، وهي ليست من ابتكار تشرش أو تورينج، بل ظهرت تدريجيًا مع تطور نظرية التعقيد . وتنص على ما يلي ^[⁶⁴^] : " يمكن لآلة تورينج الاحتمالية محاكاة أي نموذج حسابي واقعي بكفاءة". وتعني كلمة "بكفاءة" هنا الاختزالات التي تصل إلى زمن متعدد الحدود . وقد أطلق إيثان بيرنشتاين وأوميش فازيراني (1997) على هذه النظرية في الأصل اسم نظرية تشرش-تورينج في نظرية التعقيد الحسابي . وبناءً على ذلك، تفترض نظرية تشرش-تورينج في نظرية التعقيد أن جميع النماذج الحسابية "المعقولة" تُنتج نفس فئة المسائل التي يمكن حسابها في زمن متعدد الحدود. بافتراض صحة الفرضية القائلة بأن زمن كثير الحدود الاحتمالي ( BPP ) يساوي زمن كثير الحدود الحتمي ( P )، فإن كلمة "احتمالي" اختيارية في أطروحة تشرش-تورينج في نظرية التعقيد. وقد قدم سيس إف. سلوت وبيتر فان إمدي بواس أطروحة مماثلة تُسمى أطروحة الثبات ، تنص على ما يلي: " يمكن للآلات " المعقولة" محاكاة بعضها البعض ضمن تكلفة زمنية محدودة متعددة الحدود وتكلفة مكانية ثابتة." ^[⁶⁵^] ظهرت هذه الأطروحة لأول مرة في ورقة بحثية في مؤتمر STOC '84، وكانت أول ورقة تُظهر إمكانية تحقيق تكلفة زمنية متعددة الحدود وتكلفة مكانية ثابتة في آنٍ واحد لمحاكاة آلة الوصول العشوائي على آلة تورينج. ^[⁶⁶^]

إذا ثبت أن BQP مجموعة شاملة تمامًا لـ BPP ، فإن ذلك سيُبطل فرضية تشرش-تورينج في نظرية التعقيد. بعبارة أخرى، ستكون هناك خوارزميات كمومية فعّالة تُؤدي مهامًا لا توجد لها خوارزميات احتمالية فعّالة . مع ذلك، لن يُبطل هذا فرضية تشرش-تورينج الأصلية، إذ يُمكن دائمًا محاكاة الحاسوب الكمومي بواسطة آلة تورينج، ولكنه سيُبطل فرضية تشرش-تورينج الكلاسيكية في نظرية التعقيد لأسباب تتعلق بالكفاءة. ونتيجةً لذلك، تنص فرضية تشرش-تورينج في نظرية التعقيد الكمومي على ما يلي: ^{[ 64 ]} " يُمكن لآلة تورينج الكمومية محاكاة أي نموذج حسابي واقعي بكفاءة."

يزعم يوجين إيبرباخ وبيتر فيجنر أن أطروحة تشيرش-تورينج تُفسَّر أحيانًا على نطاق واسع جدًا، إذ يقولان: "مع أن آلات تورينج تُعبِّر عن سلوك الخوارزميات، فإن الادعاء الأوسع بأن الخوارزميات تُجسِّد بدقة ما يمكن حسابه هو ادعاء باطل". ^{[ 67 ]} ويزعمان أن أشكال الحوسبة التي لا تشملها الأطروحة لا تزال ذات صلة اليوم، وهي مصطلحات يُطلقان عليها اسم الحوسبة الفائقة لتورينج .

الآثار الفلسفية

فسّر الفلاسفة فرضية تشرش-تورينج على أنها ذات دلالات على فلسفة العقل . ^{[ 68 ]}^{[ 69 ]}^{[ 70 ]} ويذكر ب. جاك كوبلاند أن مسألة وجود عمليات فيزيائية حتمية فعلية، على المدى البعيد، يصعب محاكاتها بواسطة آلة تورينج، لا تزال سؤالًا تجريبيًا مفتوحًا؛ كما يذكر أن مسألة وجود مثل هذه العمليات في عمل الدماغ البشري لا تزال سؤالًا تجريبيًا مفتوحًا. ^{[ 71 ]} وهناك أيضًا بعض الأسئلة المفتوحة المهمة التي تتناول العلاقة بين فرضية تشرش-تورينج والفيزياء، وإمكانية الحوسبة الفائقة . وعند تطبيقها على الفيزياء، تحمل هذه الفرضية عدة معانٍ محتملة:

الكون يُعادل آلة تورينج؛ لذا، فإن حساب الدوال غير التكرارية مستحيلٌ فيزيائيًا. وقد أُطلق على هذا اسم فرضية تشرش-تورينج القوية، أو مبدأ تشرش-تورينج-دويتش ، وهو أساس الفيزياء الرقمية .
لا يُعادل الكون آلة تورينج (أي أن قوانين الفيزياء ليست قابلة للحساب بواسطة تورينج)، لكن الأحداث الفيزيائية غير القابلة للحساب لا يمكن "تسخيرها" لبناء حاسوب فائق . على سبيل المثال، يندرج ضمن هذه الفئة كونٌ تتضمن فيه الفيزياء أعدادًا حقيقية عشوائية ، بدلًا من أعداد حقيقية قابلة للحساب .
الكون أشبه بحاسوب فائق ، ومن الممكن بناء أجهزة مادية لتسخير هذه الخاصية وحساب الدوال غير التكرارية. على سبيل المثال، يبقى السؤال مطروحًا حول ما إذا كانت جميع أحداث ميكانيكا الكم قابلة للحساب بواسطة آلة تورينغ، مع العلم أن النماذج الدقيقة، مثل آلات تورينغ الكمومية، تُكافئ آلات تورينغ الحتمية. (ليس بالضرورة أن تكون متكافئة من حيث الكفاءة؛ انظر أعلاه). وقد اقترح جون لوكاس وروجر بنروز أن العقل البشري قد يكون نتاج نوع من الحوسبة "غير الخوارزمية" المُعززة بميكانيكا الكم. ^{[ 72 ]}^{[ 73 ]}

هناك العديد من الاحتمالات التقنية الأخرى التي تقع خارج هذه الفئات الثلاث أو بينها، ولكن هذه الفئات تُستخدم لتوضيح نطاق المفهوم.

تُناقش الجوانب الفلسفية للأطروحة، فيما يتعلق بالحواسيب الفيزيائية والبيولوجية، في كتاب أوديفردي الدراسي لعام 1989 حول نظرية الاستدعاء الذاتي. ^{[ 74 ]}^{: 101-123}

الدوال غير القابلة للحساب

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

تتيح العديد من النماذج الحسابية حساب الدوال غير القابلة للحساب (وفقًا لمعادلة تشيرش-تورينج). وتُعرف هذه النماذج باسم الحواسيب الفائقة .

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

انظر أيضاً

آلة تجريدية
أطروحة تشيرش في الرياضيات البنائية
مبدأ تشرش-تورينغ-دويتش ، الذي ينص على أنه يمكن محاكاة كل عملية فيزيائية بواسطة جهاز حاسوب عالمي
منطق قابلية الحوسبة
نظرية الحوسبة
قرر
الحوسبة الفائقة
نموذج الحوسبة
أوراكل (علوم الحاسوب)
خوارزمية فائقة التكرار
اكتمال تورينج

ملحوظات

↑ تُعرف أيضًا باسم أطروحة الحوسبة ،^{[ 1 ]} أطروحة تورينج-تشيرش ،^{[ 2 ]} تخمين تشيرش -تورينج ، أطروحة تشيرش ، تخمين تشيرش ، وأطروحة تورينج .

مراجع

↑ سواري، روبرت آي. (2009-09-01). "آلات تورينج أوراكل، والحوسبة عبر الإنترنت، وثلاثة إزاحات في نظرية الحوسبة" . حوليات المنطق البحت والتطبيقي . الحوسبة والمنطق في العالم الحقيقي: CiE 2007. 160 (3): 368-399 . doi : 10.1016/j.apal.2009.01.008 . ISSN 0168-0072 .
↑ كونراد، مايكل (مايو 1985). "حول مبادئ تصميم الحاسوب الجزيئي". اتصالات رابطة آلات الحوسبة . 28 (5): 464-480 . doi : 10.1145/3532.3533 .
↑ شتاينرت-ثريلكيلد، شين. "حسابات لامدا" . موسوعة الإنترنت للفلسفة . تم الاسترجاع في 24-02-2026 .
↑ تشرش، ألونسو (مايو 1935). "مسألة غير قابلة للحل في نظرية الأعداد الأولية. تقرير أولي" (ملف PDF) . نشرة الجمعية الرياضية الأمريكية . 41 (5): 332-333 . تاريخ الاسترجاع : 24 فبراير 2026 .
↑ تشرش، ألونسو (يوليو 1935). "مسألة غير قابلة للحل في نظرية الأعداد الأولية (تقرير أولي)" (ملف PDF) . نشرة الجمعية الرياضية الأمريكية . 41 (7): 453. تاريخ الاسترجاع: 24 فبراير 2026 .
↑ تشرش، ألونسو (أبريل 1936). "مسألة غير قابلة للحل في نظرية الأعداد الأولية" . المجلة الأمريكية للرياضيات . 58 (2): 345-363 . doi : 10.2307/2371045 . تاريخ الاسترجاع : 24 فبراير 2026 .
↑ تم استلام ملخص ورقة تشيرش من قبل نشرة الجمعية الرياضية الأمريكية في 22 مارس 1935،^{[ 4 ]} وتم تقديمه إلى الجمعية الرياضية الأمريكية في 19 أبريل 1935،^{[ 5 ]} ونُشر في 15 أبريل 1936.^{[ 6 ]}
↑ مراسلات بين ماكس نيومان وتشرش في أوراق ألونسو تشرش
↑ تورينج، آلان (2004). جوهر تورينج : كتابات رائدة في الحوسبة والمنطق والفلسفة والذكاء الاصطناعي والحياة الاصطناعية، بالإضافة إلى أسرار إنجما (ملف PDF) . أكسفورد: مطبعة كلارندون. ص 44. ISBN 9780198250791تم الاطلاع عليه بتاريخ 2021-12-06 .
↑ تورينج، أ.م. (1937). "حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار" . وقائع الجمعية الرياضية بلندن . s2-42 (1): 230–265 . doi : 10.1112/plms/s2-42.1.230 . تاريخ الاسترجاع : 24 فبراير 2026 .
1 2 سواري، روبرت آي. ( سبتمبر 1996). "قابلية الحوسبة والاستدعاء الذاتي". نشرة المنطق الرمزي . 2 (3): 284-321 . CiteSeerX 10.1.1.35.5803 . doi : 10.2307/420992 . JSTOR 420992. S2CID 5894394 .
↑ شعر تورينج، الذي أحرز تقدمًا ملحوظًا في كتابة نتائجه، بخيبة أمل عندما علم بورقة تشرش بعد وقت قصير من نشرها.^{[ 8 ]}^{[ 9 ]} أنجز تورينج ورقته بسرعة وسارع بنشرها؛ حيث استلمتها وقائع الجمعية الرياضية بلندن في 28 مايو 1936، وقُرئت في 12 نوفمبر 1936، ونُشرت في السلسلة 2، المجلد 42 (1936-1937)^{[ 10 ]} ؛ وظهرت في قسمين: في الجزء 3 (الصفحات 230-240)، الصادر في 30 نوفمبر 1936، وفي الجزء 4 (الصفحات 241-265)، الصادر في 23 ديسمبر 1936؛ وأضاف تورينج تصحيحات في المجلد 43 (1937)، الصفحات 544-546.^{[ 11 ]}^{: 45}
↑ الكنيسة 1936أ
↑ كلين 1936
↑ تورينج 1937أ
↑ كلين 1936
↑ تورينج 1937ب . مخطط البرهان في الصفحة 153: $\lambda {\mbox{-definable}}$ ${\stackrel {triv}{\implies }}$ $\lambda {\mbox{-}}K{\mbox{-definable}}$ ${\stackrel {160}{\implies }}$ ${\mbox{قابلية تورينج الحسابية}}$ ${\stackrel {161}{\implies }}$ $\mu {\mbox{-recursive}}$ ${\stackrel {Kleene}{\implies }}$ ^{[ 16 ]} $\lambda {\mbox{-definable}}$
↑ روسر 1939 في ديفيس 1965 : 225 .
↑ "فعال". قاموس ميريام ويبستر الجامعي الجديد ( الطبعة التاسعة).
↑ انظر أيضًا "فعال". قاموس ميريام-ويبستر الإلكتروني ( الطبعة الحادية عشرة) . تم الاطلاع عليه بتاريخ 26-07-2014 . والذي يقدم أيضًا هذه التعريفات لكلمة "فعال" - الأول ["إحداث تأثير حاسم أو مرغوب فيه"] كتعريف للمعنى "1أ" لكلمة "فعال"، والثاني ["قادر على إحداث نتيجة"] كجزء من "مناقشة المرادفات لكلمة فعال" هناك، (في الجزء التمهيدي، حيث يلخص أوجه التشابه بين معاني الكلمات "فعال" و"فعال" و"كفؤ" و"ناجح").
1 2 تورينج، أ.م. (1938). أنظمة المنطق القائمة على الأعداد الترتيبية (ملف PDF) (أطروحة دكتوراه). جامعة برينستون. ص 8. مؤرشف من الأصل (ملف PDF) بتاريخ 23-10-2012 . تم الاطلاع عليه بتاريخ 23-06-2012 .
↑ يقول غاندي (1980 : 123) على هذا النحو: "ما يمكن حسابه فعليًا قابل للحساب". ويسمي هذا "أطروحة تشيرش".
↑ كوبلاند، ب. جاك (2024)، "أطروحة تشيرش-تورينغ" ، في زالتا، إدوارد ن.؛ نودلمان، أوري (محرران)، موسوعة ستانفورد للفلسفة (طبعة شتاء 2024 )، مختبر أبحاث الميتافيزيقا، جامعة ستانفورد ، تاريخ الاسترجاع 11 يونيو 2025
^ هيلبرت، ديفيد. أكرمان، فيلهلم (1972) [الطبعة الأولى. 1928]. Grundzüge der theoretischen Logik [ أساسيات المنطق النظري ] (باللغة الألمانية) ( الطبعة السادسة). برلين، ألمانيا: سبرينغر. رقم ISBN 3-540-05843-5.نُشرت ترجمة إنجليزية بعنوان "مبادئ المنطق الرياضي" (1950). بروفيدنس، رود آيلاند، الولايات المتحدة الأمريكية: دار نشر تشيلسي التابعة لجمعية الرياضيات الأمريكية.
↑ تعليق ديفيس قبل تشيرش 1936 في ديفيس 1965 : 88. يستخدم تشيرش عبارة "قابلية الحساب الفعالة" في الصفحة 100 وما بعدها.
في مراجعته لكتاب " أطروحة تشيرش بعد 70 عامًا" الذي حرره آدم أولسزوسكي وآخرون عام 2006، يقترح بيتر سميث ، في نقده لورقة بحثية لموراسكي وولينسكي، أربعة "خطوط" فيما يتعلق بوضع أطروحة تشيرش-تورينغ: (1) فرضية تجريبية، (2) بديهية أو نظرية، (3) تعريف، (4) شرح. لكن سميث يرى أن (4) لا يمكن تمييزه عن (3). سميث، بيتر (11 يوليو/تموز 2007). "أطروحة تشيرش بعد 70 عامًا" (ملف PDF) . مجلة "منطق مهم" .
↑ الحاشية 3 في Church 1936a مشكلة غير قابلة للحل في نظرية الأعداد الأولية ، في Davis 1965 :89 .
↑ داوسون 1997 : 99 .
1 2 سيغ 1997 :160 .
↑ Sieg 1997 :160 ، نقلاً عن رسالة عام 1935 التي كتبها Church إلى Kleene ، الحاشية 3 في Gödel 1965 في Davis 1965 :44 .
↑ Church 1936 في Davis 1965 :105 وما بعدها.
↑ تعليق ديفيس قبل غودل 1965 في ديفيس 1965 : 40 .
↑ لمناقشة مفصلة حول تبني غودل لآلات تورينغ كنماذج للحوسبة، انظر: Shagrir, Oron (2006-06-15). "غودل حول تورينغ حول قابلية الحوسبة" (ملف PDF) . أطروحة تشرش بعد 70 عامًا . دي غرويتر. الصفحات 393-419 . doi : 10.1515/9783110325461.393 . ISBN 978-3-11-032494-5أُرشف من النسخة الأصلية (PDF) بتاريخ 17 ديسمبر 2015. تم الاطلاع عليه بتاريخ 8 فبراير 2016 .
1 2 تورينج 1937أ .
↑ حاشية المحرر لما بعد عام 1936 عملية التجميع المحدودة. الصياغة الأولى. في ديفيس 1965 : 289 .
↑ Post 1936 in Davis 1965 :291, footnote 8.
↑ ما بعد عام 1936 في ديفيس 1965 : 291 .
^ سيج 1997 :171 و176–177 .
↑ تورينج 1936-1937 في ديفيس 1965 : 263 وما بعدها.
↑ الكنيسة 1937 .
↑ تورينج 1939 في ديفيس: 160.
↑ Church 1934 في Davis 1965 :100 ، وكذلك Turing 1939 في Davis 1965 :160 .
↑ روسر 1939 في ديفيس 1965 :226 (تمت إضافة الخط المائل).
↑ Kleene 1943 ، ص. 60 في Davis 1965 :274 (تم حذف الحواشي).
↑ كلين 1952 : 300.
1 2 كلين 1952 :376.
↑ كلين 1952 : 382، 536
↑ غاندي 1980 : 123 وما بعدها.
↑ غاندي 1980 : 135
↑ غاندي 1980 : 126
^ سيج 1998-1999 في سيج، سومر وتالكوت 2002 :390ff. ; أيضا سيج 1997 :154 وما يليها.
↑ في حاشية، يقسم سيغ تصميم بوست لعام 1936 (ب) إلى (ب.1) و(ب.2)، و(ل) إلى (ل.1) و(ل.2)، ويصف (د) بشكل مختلف. وفيما يتعلق بآلة غاندي المقترحة ، يضيف لاحقًا LC.1 وLC.2 وGA.1 وGA.2. هذه التصاميم معقدة؛ انظر سيغ 1998-1999 في سيغ، سومر وتالكوت 2002 : 390 وما بعدها.
↑ يمكن الاطلاع على مجموعة من الأوراق البحثية في كتاب أولسزوسكي، وولينسكي ، ويانوش (2006) . كما يمكن الاطلاع على مراجعة لهذه المجموعة في: سميث، بيتر (11 يوليو/تموز 2007). "أطروحة الكنيسة بعد 70 عامًا" (ملف PDF) .
↑ انظر أيضًا: هودجز، أندرو (2005). "هل كان لدى تشرش وتورينج أطروحة حول الآلات؟" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 4 مارس 2016. تم الاطلاع عليه بتاريخ 27 يوليو 2014 .
↑ غودل، كورت (1995) [193؟]. "قضايا ديوفانتية غير قابلة للحسم" . في: فيفرمان، سولومون ( محرر). الأعمال الكاملة . المجلد 3. نيويورك: مطبعة جامعة أكسفورد . ص 168. ISBN 978-0-19-507255-6. OCLC 928791907 .
↑ كلين 1952:320
↑ غوريفيتش 1988:2
↑ ترجمة غودل (1936) بقلم ديفيس في كتاب "غير القابل للحسم" صفحة 83، وتختلف في استخدام كلمة "قابل للحساب" في الترجمة الواردة في كلين (1952) صفحة 321
^ هورستين في Olszewski، Woleński & Janusz 2006 :256 .
↑ غاباي 2001 : 284
↑ بيتشينيني، غوالتيرو (يناير 2007). " الحوسبة، أطروحة تشيرش-تورينغ، ومغالطة تشيرش-تورينغ" . سينثيز . 154 (1): 97-120 . CiteSeerX 10.1.1.360.9796 . doi : 10.1007/s11229-005-0194-z . S2CID 494161. مؤرشف (PDF) من الأصل بتاريخ 24 أبريل 2008.
↑ أرورا، سانجيف؛ باراك، بواز (2009). نظرية التعقيد: منهج حديث . مطبعة جامعة كامبريدج . ISBN 978-0-521-42426-4.القسمان 1.4، "الآلات كأوتار وآلة تورينج العالمية" و 1.7، "إثبات النظرية 1.9".
↑ "الوصف الرسمي للمشكلة" (ملف PDF) . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 24-11-2005.
1 2 كاي، فيليب؛ لافلام، ريموند؛ موسكا، ميشيل (2007). مقدمة في الحوسبة الكمومية . مطبعة جامعة أكسفورد. ص 5-6 . ISBN 978-0-19-857049-3.
↑ فان إمده بواس، بيتر (1990). "نماذج ومحاكاة الآلات". دليل علوم الحاسوب النظرية أ . إلسيفير . ص 5.
↑ سلوت، سي.؛ فان إمده بواس، ب. (ديسمبر 1984). حول الشريط مقابل النواة: تطبيق دوال التجزئة المثالية ذات الكفاءة المكانية على ثبات المساحة . STOC .
^ إيبرباخ وفيجنر 2003 ، ص. 287 .
↑ أبرامسون، دارين (2011). "فلسفة العقل هي (جزئيًا) فلسفة علوم الحاسوب" . العقول والآلات . 21 (2): 203-219 . doi : 10.1007/s11023-011-9236-0 . S2CID 32116031 .
↑ كوبلاند، ب. جاك (10 نوفمبر 2017). "أطروحة تشيرش-تورينغ" . في زالتا، إدوارد ن. (محرر). موسوعة ستانفورد للفلسفة . الرقم الدولي الموحد للدوريات 1095-5054 . رقم OCLC 429049174 .
↑ للاطلاع على مصادر جيدة للأوراق البحثية الأصلية، انظر: تشالمرز، ديفيد ج. ، محرر (2002). فلسفة العقل: قراءات كلاسيكية ومعاصرة . نيويورك: مطبعة جامعة أكسفورد. ISBN 978-0-19-514581-6. OCLC 610918145 .
↑ كوبلاند، ب. جاك (2004). "الحوسبة". في فلوريدي، لوتشيانو (محرر). دليل بلاكويل لفلسفة الحوسبة والمعلومات . وايلي-بلاكويل. ص 15. ISBN 978-0-631-22919-3.
↑ انظر: بنروز، روجر (1990). "الخوارزميات وآلات تورينج". عقل الإمبراطور الجديد: حول الحواسيب والعقول وقوانين الفيزياء . أكسفورد: مطبعة جامعة أكسفورد. ص 47-49 . ISBN 978-0-19-851973-7. OCLC 456785846 .
↑ انظر أيضًا وصف "الطبيعة غير الخوارزمية للبصيرة الرياضية"، بنروز، روجر (1990). "أين تكمن فيزياء العقل؟". عقل الإمبراطور الجديد: حول الحواسيب والعقول وقوانين الفيزياء . أكسفورد: مطبعة جامعة أكسفورد. الصفحات 416-418 . ISBN 978-0-19-851973-7. OCLC 456785846 .
↑ بييرجورجيو أوديفردي (1989). نظرية الاستدعاء الكلاسيكية . دراسات في المنطق وأسس الرياضيات. المجلد 125. أمستردام، هولندا: نورث هولاند.
↑ بورغين، مارك (2005). الخوارزميات فائقة التكرار . سلسلة دراسات في علوم الحاسوب. نيويورك: سبرينغر. ISBN 978-0-387-95569-8. OCLC 990755791 .

مصادر

باروايز، جون ؛ كيسلر، إتش جيه ؛ كونين، كينيث ، محرران. (1980). ندوة كلين . أمستردام: شركة نورث هولاند للنشر. ISBN 978-0-444-85345-5.
بن عمرام، أ.م. (2005). "أطروحة تشيرش-تورينغ وما يشابهها" . أخبار سيغاكت . 36 (3): 113-116 . CiteSeerX 10.1.1.74.7308 . doi : 10.1145/1086649.1086651 . S2CID 13566703. مؤرشف من الأصل (PS) بتاريخ 2017-07-06 . تم الاطلاع عليه بتاريخ 2017-10-24 .
بيرنشتاين، إي. فازيراني، يو (1997). “نظرية التعقيد الكمي”. مجلة SIAM للحوسبة . 26 (5): 1411- 1473. CiteSeerX 10.1.1.655.1186 . دوى : 10.1137/S0097539796300921 .
بلاس، أندرياس ؛ غوريفيتش، يوري (أكتوبر 2003). "الخوارزميات: بحث عن تعريفات مطلقة" (ملف PDF) . نشرة الجمعية الأوروبية لعلوم الحاسوب النظرية (81). مؤرشف (ملف PDF) من الأصل بتاريخ 27 يوليو 2004.
بورغين، مارك (2005). "الخوارزميات فائقة التكرار". دراسات في علوم الحاسوب . سبرينغر. ISBN 978-0-387-95569-8.
تشرش، ألونسو (1932). "مجموعة من المسلمات لتأسيس المنطق". حوليات الرياضيات . 33 (2): 346-366 . doi : 10.2307/1968337 . JSTOR 1968337 .
تشرش، ألونسو (أبريل 1936أ). "مسألة غير قابلة للحل في نظرية الأعداد الأولية" ( ملف PDF) . المجلة الأمريكية للرياضيات . 58 (2): 345-363 . doi : 10.2307/2371045 . JSTOR 2371045. S2CID 14181275. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 27 فبراير 2020.
تشرش، ألونسو (يونيو 1936 ب ). "ملاحظة حول مشكلة القرار". مجلة المنطق الرمزي . 1 (1): 40-41 . doi : 10.2307/2269326 . JSTOR 2269326. S2CID 42323521 .
تشرش، ألونسو (مارس 1937). "مراجعة: أ.م. تورينج، حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار". مجلة المنطق الرمزي . 2 (1): 42-43 . doi : 10.2307/2268810 . JSTOR 2268810 .
تشرش، ألونسو (1941). حسابات تحويل لامدا . برينستون: مطبعة جامعة برينستون.
كوبر، إس بي؛ أوديفردي، ب. (2003). "عدم قابلية الحوسبة في الطبيعة". في: إس بي كوبر؛ إس إس غونشاروف (محرران). قابلية الحوسبة والنماذج: منظورات شرقية وغربية . دار نشر كلوير الأكاديمية/بلينوم. ص 137-160 .
ديفيس، مارتن ، محرر (1965). غير القابل للتقرير، أوراق أساسية حول القضايا غير القابلة للتقرير، والمسائل غير القابلة للحل، والدوال القابلة للحساب . نيويورك: دار رافين للنشر.يتضمن هذا القسم أوراقًا أصلية لغودل، وتشرش، وتورينج، وروسر، وكلين، وبوست المذكورة في هذا القسم.
- غودل، كورت. "حول القضايا غير القابلة للتقرير للأنظمة الرياضية الرسمية". في ديفيس (1965) .

داوسون، جون دبليو الابن (1997). المعضلات المنطقية: حياة وأعمال كورت غودل . ويليسلي، ماساتشوستس، الولايات المتحدة الأمريكية: إيه كيه بيترز .
إيبرباخ، إي.؛ فيجنر، ب. (أكتوبر 2003). "ما وراء آلات تورينج" (ملف PDF) . نشرة الرابطة الأوروبية لعلوم الحاسوب النظرية (81): 279-304 . CiteSeerX 10.1.1.61.9759 . مؤرشف (ملف PDF) من الأصل بتاريخ 15 مارس 2016.
غاباي، د.م. (2001). دليل المنطق الفلسفي . المجلد 1 ( الطبعة الثانية).
غاندي، روبن (1980). "أطروحة تشيرش ومبادئ الآليات". في: إتش جيه باروايز؛ إتش جيه كيسلر؛ ك. كونين (محررون). ندوة كلين . شركة نورث هولاند للنشر. ص 123-148 .
غاندي، روبن (1994). هيركن، رولف (محرر). آلة تورينج العالمية: مسح نصف قرن . نيويورك: فيينا سبرينغر-فيرلاغ. ص 51 وما يليها. رقم ISBN 978-3-211-82637-9.
جودل ، كورت (1936). "Über die Lānge von Beweisen" [ في طول البراهين ] . Ergenbnisse Eines Mathematishen Kolloquiums (باللغة الألمانية) (7). الثقل: 23 – 24.استشهد به كلين (1952) .
غوريفيتش، يوري (يونيو 1988). "حول آلات كولموغوروف والقضايا ذات الصلة". نشرة الرابطة الأوروبية لعلوم الحاسوب النظرية (35): 71-82 .
غوريفيتش، يوري (يوليو 2000). " آلات الحالة المجردة المتسلسلة تلتقط الخوارزميات المتسلسلة" (ملف PDF) . معاملات ACM في المنطق الحسابي . 1 (1): 77-111 . CiteSeerX 10.1.1.146.3017 . doi : 10.1145/343369.343384 . S2CID 2031696. مؤرشف (ملف PDF) من الأصل بتاريخ 16 أكتوبر 2003.
هيربراند، جاك (1932). "Sur la Non-تناقض دي l'arithmétique". Journal für die Reine und Angewandte Mathematik (باللغة الفرنسية). 166 : 1– 8. دوى : 10.1515/crll.1932.166.1 . S2CID 116636410 .
هوفستاتر، دوغلاس ر. (5 فبراير 1999). "الفصل السابع عشر: تشرش، تورينج، تارسكي، وآخرون". غودل، إيشر، باخ: ضفيرة ذهبية أبدية (طبعة الذكرى العشرين ). بيسيك بوكس . الصفحات 559-585 . ISBN 0-465-02656-7.
كلين، ستيفن كول (يناير 1935). "نظرية الأعداد الصحيحة الموجبة في المنطق الصوري" . المجلة الأمريكية للرياضيات . 57 (1): 153-173 و219-244. doi : 10.2307/2372027 . JSTOR 2372027 .
كلين، ستيفن كول (1936). "قابلية تعريف لامدا والتكرارية" . مجلة ديوك الرياضية . 2 (2): 340-353 . doi : 10.1215/s0012-7094-36-00227-2 .
كلين، ستيفن كول (1943). "المسندات والمكممات الاسترجاعية" . معاملات الجمعية الرياضية الأمريكية . 53 (1): 41-73 . doi : 10.2307/1990131 . JSTOR 1990131 . أعيد طبعه في كتاب The Undecidable ، ص 255 وما بعدها. قام كلين بتنقيح تعريفه لـ "التكرار العام" وشرع في الفصل "12. النظريات الخوارزمية" ليطرح "الأطروحة الأولى" (ص 274)؛ وسيكرر هذه الأطروحة لاحقًا (في كلين 1952 : 300) ويسميها "أطروحة الكنيسة" ( كلين 1952 : 317) (أي أطروحة الكنيسة ).
كلين، ستيفن كول (1952). مقدمة في ما وراء الرياضيات . نورث هولاند. OCLC 523942 .
كنوت، دونالد (1973). فن برمجة الحاسوب . المجلد 1/الخوارزميات الأساسية ( الطبعة الثانية). أديسون-ويسلي.
كوجل، بيتر (نوفمبر 2005). "حان الوقت للتفكير خارج الصندوق الحسابي". اتصالات رابطة مكائن الحوسبة . 48 (11): 32-37 . CiteSeerX 10.1.1.137.6939 . doi : 10.1145/1096000.1096001 . S2CID 29843806 .
لويس، إتش آر ؛ باباديميتريو، سي إتش (1998). عناصر نظرية الحوسبة . أبر سادل ريفر، نيو جيرسي، الولايات المتحدة الأمريكية: برنتيس هول.
مانا، زوهار (2003) [1974]. النظرية الرياضية للحساب . دوفر. ISBN 978-0-486-43238-0.{{cite book}}: CS1 maint: موقع الناشر مفقود ( رابط )
ماركوف، أ.أ. (1960) [1954]. "نظرية الخوارزميات". ترجمات الجمعية الرياضية الأمريكية . 2 (15): 1-14 .
أولسزوسكي، آدم؛ وولينسكي، يان؛ يانوش، روبرت، محرران. (2006). أطروحة تشيرش بعد 70 عامًا . فرانكفورت: أونتوس. ISBN 978-3-938793-09-1. OCLC 909679288 .
بور-إل، إم بي ؛ ريتشاردز، جي آي (1989). قابلية الحوسبة في التحليل والفيزياء . سبرينغر فيرلاغ .
روسر، ج. ب. (1939). "عرض غير رسمي لبراهين نظرية غودل ونظرية تشرش". مجلة المنطق الرمزي . 4 (2): 53-60 . doi : 10.2307/2269059 . JSTOR 2269059. S2CID 39499392 .
سيغ، ويلفريد (يونيو 1997). "خطوة بخطوة تكرارية: تحليل تشيرش للحساب الفعال". نشرة المنطق الرمزي . 3 (2): 154-180 . doi : 10.2307/421012 . JSTOR 421012 .
سيغ، ويلفريد؛ سومر، ريتشارد؛ تالكوت، كارولين، محرران. (2002). تأملات في أسس الرياضيات: مقالات تكريمًا لسولومون فيفرمان . سلسلة محاضرات في المنطق. المجلد 15. دار نشر إيه كيه بيترز المحدودة. رقم ISBN 978-1-56881-169-7.
سيروبولوس، أبوستولوس (2008). الحوسبة الفائقة: الحوسبة ما وراء حاجز تشيرش-تورينغ . سبرينغر. ISBN 978-0-387-30886-9.
تورينج، أ.م. (1937أ) [مُقدَّم إلى الجمعية في نوفمبر 1936]، "حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار" (ملف PDF) ، وقائع الجمعية الرياضية بلندن ، المجلد 42، العدد 2، الصفحات 230-265 ، رمز Bibcode : 1937PLMS...42..230T ، doi : 10.1112/plms/s2-42.1.230 ، S2CID 73712 وتورينج ، أ.م. (1938). "حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار: تصحيح". وقائع الجمعية الرياضية بلندن . 2. المجلد 43 (نُشر عام 1937). الصفحات 544-546 . doi : 10.1112/plms/s2-43.6.544 . (انظر أيضًا: ديفيس 1965 : 115 وما بعدها.)
تورينج، آلان ماثيسون (ديسمبر 1937ب). "قابلية الحوسبة وقابلية تعريف لامدا" ( ملف PDF) . مجلة المنطق الرمزي . 2 (4): 153-163 . doi : 10.2307/2268280 . JSTOR 2268280. S2CID 2317046. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 9 أغسطس 2020.

روابط خارجية

مدخل "أطروحة الكنيسة-تورينج"بقلم ب. جاك كوبلاند في موسوعة ستانفورد للفلسفة .
مدخل "الحوسبة في الأنظمة الفيزيائية"بقلم غوالتيرو بيتشينيني في موسوعة ستانفورد للفلسفة - معالجة فلسفية شاملة للقضايا ذات الصلة.
كازناتشيف، أرتيم (11-09-2014). "المثالية المتعالية وصيغة بوست لأطروحة تشيرش-تورينغ" . مجلة المنطق الرمزي . 1 (3): 103-105 .
تم تخصيص عدد خاص (المجلد 28، العدد 4، 1987) من مجلة نوتردام للمنطق الصوري لأطروحة تشيرش-تورينج.

[3] تُعرف أيضًا باسم أطروحة الحوسبة ،^{[ 1 ]} أطروحة تورينج-تشيرش ،^{[ 2 ]} تخمين تشيرش -تورينج ، أطروحة تشيرش ، تخمين تشيرش ، وأطروحة تورينج .

[1] سواري، روبرت آي. (2009-09-01). "آلات تورينج أوراكل، والحوسبة عبر الإنترنت، وثلاثة إزاحات في نظرية الحوسبة" . حوليات المنطق البحت والتطبيقي . الحوسبة والمنطق في العالم الحقيقي: CiE 2007. 160 (3): 368-399 . doi : 10.1016/j.apal.2009.01.008 . ISSN 0168-0072 .

[2] كونراد، مايكل (مايو 1985). "حول مبادئ تصميم الحاسوب الجزيئي". اتصالات رابطة آلات الحوسبة . 28 (5): 464-480 . doi : 10.1145/3532.3533 .

[4] شتاينرت-ثريلكيلد، شين. "حسابات لامدا" . موسوعة الإنترنت للفلسفة . تم الاسترجاع في 24-02-2026 .

[5] تشرش، ألونسو (مايو 1935). "مسألة غير قابلة للحل في نظرية الأعداد الأولية. تقرير أولي" (ملف PDF) . نشرة الجمعية الرياضية الأمريكية . 41 (5): 332-333 . تاريخ الاسترجاع : 24 فبراير 2026 .

[6] تشرش، ألونسو (يوليو 1935). "مسألة غير قابلة للحل في نظرية الأعداد الأولية (تقرير أولي)" (ملف PDF) . نشرة الجمعية الرياضية الأمريكية . 41 (7): 453. تاريخ الاسترجاع: 24 فبراير 2026 .

[7] تشرش، ألونسو (أبريل 1936). "مسألة غير قابلة للحل في نظرية الأعداد الأولية" . المجلة الأمريكية للرياضيات . 58 (2): 345-363 . doi : 10.2307/2371045 . تاريخ الاسترجاع : 24 فبراير 2026 .

[ChurchUnsolvProb-8] تم استلام ملخص ورقة تشيرش من قبل نشرة الجمعية الرياضية الأمريكية في 22 مارس 1935،^{[ 4 ]} وتم تقديمه إلى الجمعية الرياضية الأمريكية في 19 أبريل 1935،^{[ 5 ]} ونُشر في 15 أبريل 1936.^{[ 6 ]}

[TuringNewman-9] مراسلات بين ماكس نيومان وتشرش في أوراق ألونسو تشرش

[EssentialTuring-10] تورينج، آلان (2004). جوهر تورينج : كتابات رائدة في الحوسبة والمنطق والفلسفة والذكاء الاصطناعي والحياة الاصطناعية، بالإضافة إلى أسرار إنجما (ملف PDF) . أكسفورد: مطبعة كلارندون. ص 44. ISBN 9780198250791تم الاطلاع عليه بتاريخ 2021-12-06 .

[11] تورينج، أ.م. (1937). "حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار" . وقائع الجمعية الرياضية بلندن . s2-42 (1): 230–265 . doi : 10.1112/plms/s2-42.1.230 . تاريخ الاسترجاع : 24 فبراير 2026 .

[Soare-12] 1 2 سواري، روبرت آي. ( سبتمبر 1996). "قابلية الحوسبة والاستدعاء الذاتي". نشرة المنطق الرمزي . 2 (3): 284-321 . CiteSeerX 10.1.1.35.5803 . doi : 10.2307/420992 . JSTOR 420992. S2CID 5894394 .

[TuringLearn-13] شعر تورينج، الذي أحرز تقدمًا ملحوظًا في كتابة نتائجه، بخيبة أمل عندما علم بورقة تشرش بعد وقت قصير من نشرها.^{[ 8 ]}^{[ 9 ]} أنجز تورينج ورقته بسرعة وسارع بنشرها؛ حيث استلمتها وقائع الجمعية الرياضية بلندن في 28 مايو 1936، وقُرئت في 12 نوفمبر 1936، ونُشرت في السلسلة 2، المجلد 42 (1936-1937)^{[ 10 ]} ؛ وظهرت في قسمين: في الجزء 3 (الصفحات 230-240)، الصادر في 30 نوفمبر 1936، وفي الجزء 4 (الصفحات 241-265)، الصادر في 23 ديسمبر 1936؛ وأضاف تورينج تصحيحات في المجلد 43 (1937)، الصفحات 544-546.^{[ 11 ]}^{: 45}

[14] الكنيسة 1936أ

[15] كلين 1936

[16] تورينج 1937أ

[17] كلين 1936

[18] تورينج 1937ب . مخطط البرهان في الصفحة 153: $\lambda {\mbox{-definable}}$ ${\stackrel {triv}{\implies }}$ $\lambda {\mbox{-}}K{\mbox{-definable}}$ ${\stackrel {160}{\implies }}$ ${\mbox{قابلية تورينج الحسابية}}$ ${\stackrel {161}{\implies }}$ $\mu {\mbox{-recursive}}$ ${\stackrel {Kleene}{\implies }}$ ^{[ 16 ]} $\lambda {\mbox{-definable}}$

[19] روسر 1939 في ديفيس 1965 : 225 .

[20] "فعال". قاموس ميريام ويبستر الجامعي الجديد ( الطبعة التاسعة).

[21] انظر أيضًا "فعال". قاموس ميريام-ويبستر الإلكتروني ( الطبعة الحادية عشرة) . تم الاطلاع عليه بتاريخ 26-07-2014 . والذي يقدم أيضًا هذه التعريفات لكلمة "فعال" - الأول ["إحداث تأثير حاسم أو مرغوب فيه"] كتعريف للمعنى "1أ" لكلمة "فعال"، والثاني ["قادر على إحداث نتيجة"] كجزء من "مناقشة المرادفات لكلمة فعال" هناك، (في الجزء التمهيدي، حيث يلخص أوجه التشابه بين معاني الكلمات "فعال" و"فعال" و"كفؤ" و"ناجح").

[Turing_1938_thesis_p8-22] 1 2 تورينج، أ.م. (1938). أنظمة المنطق القائمة على الأعداد الترتيبية (ملف PDF) (أطروحة دكتوراه). جامعة برينستون. ص 8. مؤرشف من الأصل (ملف PDF) بتاريخ 23-10-2012 . تم الاطلاع عليه بتاريخ 23-06-2012 .

[23] يقول غاندي (1980 : 123) على هذا النحو: "ما يمكن حسابه فعليًا قابل للحساب". ويسمي هذا "أطروحة تشيرش".

[24] كوبلاند، ب. جاك (2024)، "أطروحة تشيرش-تورينغ" ، في زالتا، إدوارد ن.؛ نودلمان، أوري (محرران)، موسوعة ستانفورد للفلسفة (طبعة شتاء 2024 )، مختبر أبحاث الميتافيزيقا، جامعة ستانفورد ، تاريخ الاسترجاع 11 يونيو 2025

[25] هيلبرت، ديفيد. أكرمان، فيلهلم (1972) [الطبعة الأولى. 1928]. Grundzüge der theoretischen Logik [ أساسيات المنطق النظري ] (باللغة الألمانية) ( الطبعة السادسة). برلين، ألمانيا: سبرينغر. رقم ISBN 3-540-05843-5.نُشرت ترجمة إنجليزية بعنوان "مبادئ المنطق الرياضي" (1950). بروفيدنس، رود آيلاند، الولايات المتحدة الأمريكية: دار نشر تشيلسي التابعة لجمعية الرياضيات الأمريكية.

[26] تعليق ديفيس قبل تشيرش 1936 في ديفيس 1965 : 88. يستخدم تشيرش عبارة "قابلية الحساب الفعالة" في الصفحة 100 وما بعدها.

[27] في مراجعته لكتاب " أطروحة تشيرش بعد 70 عامًا" الذي حرره آدم أولسزوسكي وآخرون عام 2006، يقترح بيتر سميث ، في نقده لورقة بحثية لموراسكي وولينسكي، أربعة "خطوط" فيما يتعلق بوضع أطروحة تشيرش-تورينغ: (1) فرضية تجريبية، (2) بديهية أو نظرية، (3) تعريف، (4) شرح. لكن سميث يرى أن (4) لا يمكن تمييزه عن (3). سميث، بيتر (11 يوليو/تموز 2007). "أطروحة تشيرش بعد 70 عامًا" (ملف PDF) . مجلة "منطق مهم" .

[28] الحاشية 3 في Church 1936a مشكلة غير قابلة للحل في نظرية الأعداد الأولية ، في Davis 1965 :89 .

[29] داوسون 1997 : 99 .

[sieg160-30] 1 2 سيغ 1997 :160 .

[31] Sieg 1997 :160 ، نقلاً عن رسالة عام 1935 التي كتبها Church إلى Kleene ، الحاشية 3 في Gödel 1965 في Davis 1965 :44 .

[32] Church 1936 في Davis 1965 :105 وما بعدها.

[33] تعليق ديفيس قبل غودل 1965 في ديفيس 1965 : 40 .

[34] لمناقشة مفصلة حول تبني غودل لآلات تورينغ كنماذج للحوسبة، انظر: Shagrir, Oron (2006-06-15). "غودل حول تورينغ حول قابلية الحوسبة" (ملف PDF) . أطروحة تشرش بعد 70 عامًا . دي غرويتر. الصفحات 393-419 . doi : 10.1515/9783110325461.393 . ISBN 978-3-11-032494-5أُرشف من النسخة الأصلية (PDF) بتاريخ 17 ديسمبر 2015. تم الاطلاع عليه بتاريخ 8 فبراير 2016 .

[On_Computable-35] 1 2 تورينج 1937أ .

[36] حاشية المحرر لما بعد عام 1936 عملية التجميع المحدودة. الصياغة الأولى. في ديفيس 1965 : 289 .

[37] Post 1936 in Davis 1965 :291, footnote 8.

[38] ما بعد عام 1936 في ديفيس 1965 : 291 .

[39] سيج 1997 :171 و176–177 .

[40] تورينج 1936-1937 في ديفيس 1965 : 263 وما بعدها.

[41] الكنيسة 1937 .

[42] تورينج 1939 في ديفيس: 160.

[43] Church 1934 في Davis 1965 :100 ، وكذلك Turing 1939 في Davis 1965 :160 .

[44] روسر 1939 في ديفيس 1965 :226 (تمت إضافة الخط المائل).

[Davis274-45] Kleene 1943 ، ص. 60 في Davis 1965 :274 (تم حذف الحواشي).

[46] كلين 1952 : 300.

[Kleene_1952_p376-47] 1 2 كلين 1952 :376.

[48] كلين 1952 : 382، 536

[49] غاندي 1980 : 123 وما بعدها.

[50] غاندي 1980 : 135

[51] غاندي 1980 : 126

[52] سيج 1998-1999 في سيج، سومر وتالكوت 2002 :390ff. ; أيضا سيج 1997 :154 وما يليها.

[53] في حاشية، يقسم سيغ تصميم بوست لعام 1936 (ب) إلى (ب.1) و(ب.2)، و(ل) إلى (ل.1) و(ل.2)، ويصف (د) بشكل مختلف. وفيما يتعلق بآلة غاندي المقترحة ، يضيف لاحقًا LC.1 وLC.2 وGA.1 وGA.2. هذه التصاميم معقدة؛ انظر سيغ 1998-1999 في سيغ، سومر وتالكوت 2002 : 390 وما بعدها.

[54] يمكن الاطلاع على مجموعة من الأوراق البحثية في كتاب أولسزوسكي، وولينسكي ، ويانوش (2006) . كما يمكن الاطلاع على مراجعة لهذه المجموعة في: سميث، بيتر (11 يوليو/تموز 2007). "أطروحة الكنيسة بعد 70 عامًا" (ملف PDF) .

[55] انظر أيضًا: هودجز، أندرو (2005). "هل كان لدى تشرش وتورينج أطروحة حول الآلات؟" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 4 مارس 2016. تم الاطلاع عليه بتاريخ 27 يوليو 2014 .

[56] غودل، كورت (1995) [193؟]. "قضايا ديوفانتية غير قابلة للحسم" . في: فيفرمان، سولومون ( محرر). الأعمال الكاملة . المجلد 3. نيويورك: مطبعة جامعة أكسفورد . ص 168. ISBN 978-0-19-507255-6. OCLC 928791907 .

[57] كلين 1952:320

[58] غوريفيتش 1988:2

[59] ترجمة غودل (1936) بقلم ديفيس في كتاب "غير القابل للحسم" صفحة 83، وتختلف في استخدام كلمة "قابل للحساب" في الترجمة الواردة في كلين (1952) صفحة 321

[60] هورستين في Olszewski، Woleński & Janusz 2006 :256 .

[61] غاباي 2001 : 284

[62] بيتشينيني، غوالتيرو (يناير 2007). " الحوسبة، أطروحة تشيرش-تورينغ، ومغالطة تشيرش-تورينغ" . سينثيز . 154 (1): 97-120 . CiteSeerX 10.1.1.360.9796 . doi : 10.1007/s11229-005-0194-z . S2CID 494161. مؤرشف (PDF) من الأصل بتاريخ 24 أبريل 2008.

[63] أرورا، سانجيف؛ باراك، بواز (2009). نظرية التعقيد: منهج حديث . مطبعة جامعة كامبريدج . ISBN 978-0-521-42426-4.القسمان 1.4، "الآلات كأوتار وآلة تورينج العالمية" و 1.7، "إثبات النظرية 1.9".

[64] "الوصف الرسمي للمشكلة" (ملف PDF) . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 24-11-2005.

[kaye-65] 1 2 كاي، فيليب؛ لافلام، ريموند؛ موسكا، ميشيل (2007). مقدمة في الحوسبة الكمومية . مطبعة جامعة أكسفورد. ص 5-6 . ISBN 978-0-19-857049-3.

[66] فان إمده بواس، بيتر (1990). "نماذج ومحاكاة الآلات". دليل علوم الحاسوب النظرية أ . إلسيفير . ص 5.

[67] سلوت، سي.؛ فان إمده بواس، ب. (ديسمبر 1984). حول الشريط مقابل النواة: تطبيق دوال التجزئة المثالية ذات الكفاءة المكانية على ثبات المساحة . STOC .

[68] إيبرباخ وفيجنر 2003 ، ص. 287 .

[69] أبرامسون، دارين (2011). "فلسفة العقل هي (جزئيًا) فلسفة علوم الحاسوب" . العقول والآلات . 21 (2): 203-219 . doi : 10.1007/s11023-011-9236-0 . S2CID 32116031 .

[70] كوبلاند، ب. جاك (10 نوفمبر 2017). "أطروحة تشيرش-تورينغ" . في زالتا، إدوارد ن. (محرر). موسوعة ستانفورد للفلسفة . الرقم الدولي الموحد للدوريات 1095-5054 . رقم OCLC 429049174 .

[71] للاطلاع على مصادر جيدة للأوراق البحثية الأصلية، انظر: تشالمرز، ديفيد ج. ، محرر (2002). فلسفة العقل: قراءات كلاسيكية ومعاصرة . نيويورك: مطبعة جامعة أكسفورد. ISBN 978-0-19-514581-6. OCLC 610918145 .

[72] كوبلاند، ب. جاك (2004). "الحوسبة". في فلوريدي، لوتشيانو (محرر). دليل بلاكويل لفلسفة الحوسبة والمعلومات . وايلي-بلاكويل. ص 15. ISBN 978-0-631-22919-3.

[73] انظر: بنروز، روجر (1990). "الخوارزميات وآلات تورينج". عقل الإمبراطور الجديد: حول الحواسيب والعقول وقوانين الفيزياء . أكسفورد: مطبعة جامعة أكسفورد. ص 47-49 . ISBN 978-0-19-851973-7. OCLC 456785846 .

[74] انظر أيضًا وصف "الطبيعة غير الخوارزمية للبصيرة الرياضية"، بنروز، روجر (1990). "أين تكمن فيزياء العقل؟". عقل الإمبراطور الجديد: حول الحواسيب والعقول وقوانين الفيزياء . أكسفورد: مطبعة جامعة أكسفورد. الصفحات 416-418 . ISBN 978-0-19-851973-7. OCLC 456785846 .

[75] بييرجورجيو أوديفردي (1989). نظرية الاستدعاء الكلاسيكية . دراسات في المنطق وأسس الرياضيات. المجلد 125. أمستردام، هولندا: نورث هولاند.

[76] بورغين، مارك (2005). الخوارزميات فائقة التكرار . سلسلة دراسات في علوم الحاسوب. نيويورك: سبرينغر. ISBN 978-0-387-95569-8. OCLC 990755791 .

[ أ ]

ابتكر

[ 7 ]

[ ١٢ ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 17 ]

[

[

[

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ ٣٢ ]

[ ٣٣ ]

[

[

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ 42 ]

[ 43 ]

[ 44 ]

[ 45 ]

[ 46 ]

[ 47 ]

[ ٤٨ ]

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[ 54 ]

[ 55 ]

11

[

[

[ 58 ]

[ 59 ]

[ 60 ]

[ 61 ]

[ 62 ]

[ 63 ]،

[

[

[

[ 67 ]

[ 68 ]

[ 69 ]

[ 70 ]

[ 71 ]

[ 72 ]

[ 73 ]

[ 74 ]

[ 75 ]

[ 1 ]

[ 2 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 16 ]

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