توصيفات الخوارزمية

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

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

إن أكثر مخططات معالجة الأرقام شيوعًا - سواء في الرياضيات الرسمية أو في الحياة الروتينية - هي: (1) الدوال المتكررة التي يحسبها الشخص باستخدام الورقة والقلم، و(2) آلة تورينج أو ما يعادلها من آلات تورينج - نموذج آلة التسجيل البدائية أو نموذج "آلة العداد"، ونموذج آلة الوصول العشوائي ^{[ 1 ]} (RAM)، ونموذج آلة البرنامج المخزن ذي الوصول العشوائي (RASP) ومكافئها الوظيفي " الكمبيوتر ".

عندما نقوم بـ "الحساب"، فإننا في الواقع نحسب باستخدام "الدوال المتكررة" في الخوارزميات المختصرة التي تعلمناها في المدرسة الابتدائية، على سبيل المثال، الجمع والطرح.

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

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

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

هناك إجماع أكبر على "توصيف" مفهوم "الخوارزمية البسيطة".

يجب تحديد جميع الخوارزميات بلغة رسمية، وينشأ مفهوم "البساطة" من بساطة اللغة. يُعدّ تسلسل تشومسكي (1956) تسلسلاً هرمياً لاحتواء فئات القواعد النحوية الرسمية التي تُولّد لغات رسمية . ويُستخدم لتصنيف لغات البرمجة والآلات المجردة .

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

أمثلة: لغة الماكرو "للأغراض العامة"، مثل M4، غير مقيدة ( كاملة تورينج )، لكن لغة الماكرو للمعالج المسبق C ليست كذلك، لذا فإن أي خوارزمية معبر عنها في المعالج المسبق C هي "خوارزمية بسيطة".

انظر أيضًا العلاقات بين فئات التعقيد .

فيما يلي السمات المرغوبة لخوارزمية محددة جيدًا، كما نوقش في Scheider and Gersting (1995):

• عمليات واضحة لا لبس فيها: يجب أن تتضمن الخوارزمية خطوات محددة وواضحة. ينبغي أن تكون هذه الخطوات دقيقة بما يكفي لتحديد ما يجب فعله في كل خطوة بدقة.
• مُرتب جيدًا: يجب تحديد الترتيب الدقيق للعمليات التي يتم تنفيذها في الخوارزمية بشكل ملموس.
• الجدوى: يجب أن تكون جميع خطوات الخوارزمية ممكنة (والمعروفة أيضًا باسم قابلة للحساب بشكل فعال ).
• المدخلات: يجب أن تكون الخوارزمية قادرة على قبول مجموعة محددة جيدًا من المدخلات.
• الناتج: يجب أن تنتج الخوارزمية نتيجة ما كناتج، حتى يمكن التفكير في صحتها.
• محدودية التنفيذ: يجب أن تنتهي الخوارزمية بعد عدد محدود من التعليمات. ^{[ 2 ]}

تشمل خصائص الخوارزميات المحددة التي قد تكون مرغوبة كفاءة المساحة والوقت ، والعمومية (أي القدرة على التعامل مع العديد من المدخلات)، أو الحتمية .

في أوائل عام 1870، قدّم دبليو ستانلي جيفونز "آلة منطقية" (جيفونز 1880: 200) لتحليل القياس المنطقي أو أي شكل منطقي آخر ، كحجة مُختزلة إلى معادلة بولية . وبواسطة ما أسماه كوتورا (1914) "نوعًا من البيانو المنطقي "، تُعزف المتساويات التي تُمثل المقدمات على لوحة مفاتيح تُشبه لوحة مفاتيح الآلة الكاتبة. وعند الانتهاء من عزف جميع المقدمات، لا تُظهر اللوحة إلا المكونات التي يساوي مجموعها 1، أي الكل المنطقي. تتميز هذه الطريقة الميكانيكية عن طريقة فين الهندسية..." (كوتورا 1914: 75).

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

(1) "أولاً، هناك بيان لبياناتنا بلغة منطقية دقيقة".

(2) "ثم ثانياً، علينا أن نضع هذه العبارات في شكل مناسب لكي يعمل المحرك معها - في هذه الحالة اختزال كل اقتراح إلى نفيه الأساسي".

(3) "ثالثًا، هناك دمج أو معالجة إضافية لمبانينا بعد هذا التخفيض."

(4) "أخيرًا، يجب تفسير النتائج أو قراءتها. وهذا الأخير يتيح عادةً مجالًا واسعًا للمهارة والفطنة."

ويخلص إلى أنه "لا أستطيع أن أرى أن أي آلة يمكن أن تأمل في مساعدتنا إلا في الخطوة الثالثة من هذه الخطوات؛ لذلك يبدو من المشكوك فيه للغاية ما إذا كان أي شيء من هذا القبيل يستحق حقًا اسم محرك منطقي." (فين 1881: 119-121).

هذا القسم أطول وأكثر تفصيلاً من الأقسام الأخرى نظرًا لأهميته للموضوع: كان كلين أول من اقترح أن جميع الحسابات / العمليات الحسابية - من كل نوع، مجموعها - يمكن أن تكون (1) مكافئة باستخدام خمسة " عوامل تكرارية بدائية " بالإضافة إلى عامل خاص واحد يسمى عامل mu ، أو (2) مكافئة عن طريق أفعال آلة تورينج أو نموذج مكافئ.

علاوة على ذلك، رأى أن أياً من هذين الأمرين يمكن اعتباره تعريفاً للخوارزمية .

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

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

قدّم أندريه ماركوف الابن (1954) التعريف التالي للخوارزمية:

"1. في الرياضيات، يُفهم مصطلح "الخوارزمية" عادةً على أنه وصفة دقيقة، تحدد عملية حسابية، تؤدي من بيانات أولية مختلفة إلى النتيجة المرجوة...."

"الخصائص الثلاث التالية هي سمات مميزة للخوارزميات وتحدد دورها في الرياضيات:

"أ) دقة الوصفة الطبية، بحيث لا تترك مجالاً للتعسف، وقابليتها للفهم العالمي - وضوح الخوارزمية؛

"ب) إمكانية البدء ببيانات أولية، والتي قد تختلف ضمن حدود معينة - عمومية الخوارزمية؛

"ج) توجيه الخوارزمية نحو الحصول على نتيجة مرغوبة، والتي يتم الحصول عليها بالفعل في النهاية باستخدام البيانات الأولية المناسبة - مدى حسم الخوارزمية." (ص 1)

أقرّ بأن هذا التعريف "لا يدّعي الدقة الرياضية" (ص  1). وكانت دراسته المنشورة عام 1954 محاولته لتعريف الخوارزمية بدقة أكبر؛ إذ رأى أن تعريفه الناتج - خوارزميته "العادية" - "مكافئ لمفهوم الدالة التكرارية " (ص  3). وتضمن تعريفه أربعة مكونات رئيسية (الفصل الثاني، القسم 3، ص  63 وما بعدها):

"1. خطوات أولية منفصلة، ​​يتم تنفيذ كل منها وفقًا لإحدى قواعد [الاستبدال] ... [القواعد المذكورة في البداية]

"2. ... خطوات ذات طبيعة محلية ... [وبالتالي لن تقوم الخوارزمية بتغيير أكثر من عدد معين من الرموز إلى يسار أو يمين الكلمة/الرمز الملاحظ]

"3. قواعد صيغ الاستبدال ... [وقد أطلق على قائمة هذه القواعد اسم "مخطط" الخوارزمية]

4. ...وسيلة لتمييز "الاستبدال الختامي" [أي حالة أو حالات "نهائية/نهائية" قابلة للتمييز]

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

التمييز والموضعية : ظهر كلا المفهومين لأول مرة مع تورينج (1936-1937) --

«يجب أن تكون المربعات الجديدة المرصودة قابلة للتمييز فورًا بواسطة الحاسوب [ كذا : كان الحاسوب شخصًا في عام 1936]. أعتقد أنه من المعقول افتراض أنها لا يمكن أن تكون إلا مربعات لا تتجاوز المسافة بينها وبين أقرب مربع من المربعات المرصودة مباشرةً قيمة ثابتة معينة. لنفترض أن كل مربع من المربعات الجديدة المرصودة يقع ضمن L مربعًا من أحد المربعات المرصودة سابقًا.» (تورينغ (1936)، ص 136 في كتاب ديفيس، غير قابل للتقرير )

يبرز مفهوم المحلية بشكل واضح في أعمال غوريفيتش وغاندي (1980) (الذي يستشهد به غوريفيتش). ويُعرف مبدأ غاندي الرابع للآليات باسم "مبدأ السببية المحلية".

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

١٩٣٦ : وردت مقولة شهيرة لكورت غودل في "ملاحظة أضيفت إلى برهان النسخة الألمانية الأصلية" في بحثه "حول طول البراهين" الذي ترجمه مارتن ديفيس، والمنشور في الصفحتين  ٨٢-٨٣ من كتاب "غير القابل للحسم " . وقد اقتبس عدد من المؤلفين - مثل كلين، وغوريفيتش، وغاندي، وغيرهم - ما يلي:

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

١٩٦٣ : في "ملاحظة" مؤرخة في ٢٨ أغسطس ١٩٦٣، أُضيفت إلى بحثه الشهير " حول القضايا غير القابلة للتقرير رسميًا " (١٩٣١)، ذكر غودل (في حاشية) اعتقاده بأن " الأنظمة الصورية " تتميز "بخاصية أن الاستدلال فيها، من حيث المبدأ، يمكن استبداله تمامًا بأجهزة ميكانيكية" (ص  ٦١٦ في فان هيجينورت). "... بفضل عمل أ.م. تورينج، أصبح من الممكن الآن تقديم تعريف دقيق وكافٍ بلا شك للمفهوم العام للنظام الصوري، كما أصبح من الممكن الآن صياغة نسخة عامة تمامًا من النظريتين السادسة والحادية عشرة." (ص  ٦١٦). وفي ملاحظة أخرى عام ١٩٦٤ على عمل آخر، عبّر عن الرأي نفسه بقوة وتفصيل أكبر.

1964 : في ملحق مؤرخ في عام 1964، لورقة بحثية قُدمت إلى معهد الدراسات المتقدمة في ربيع عام 1934، عزز غودل قناعته بأن "الأنظمة الرسمية" هي تلك التي يمكن ميكنتها:

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

تشير علامة * إلى حاشية يستشهد فيها غودل بأوراق آلان تورينج (1937) وإميل بوست (1936)، ثم يمضي ليدلي بالتصريح المثير للاهتمام التالي:

"As for previous equivalent definitions of computability, which however, are much less suitable for our purpose, see Alonzo Church, Am. J. Math., vol. 58 (1936) [appearing in The Undecidable pp. 100-102]).

Church's definitions encompass so-called "recursion" and the "lambda calculus" (i.e. the λ-definable functions). His footnote 18 says that he discussed the relationship of "effective calculatibility" and "recursiveness" with Gödel but that he independently questioned "effectively calculability" and "λ-definability":

"We now define the notion . . . of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers¹⁸ (or of a λ-definable function of positive integers.

"It has already been pointed out that, for every function of positive integers which is effectively calculable in the sense just defined, there exists an algorithm for the calculation of its value.

"Conversely it is true . . ." (p. 100, The Undecidable).

It would appear from this, and the following, that far as Gödel was concerned, the Turing machine was sufficient and the lambda calculus was "much less suitable." He goes on to make the point that, with regards to limitations on human reason, the jury is still out:

("Note that the question of whether there exist finite non-mechanical procedures** not equivalent with any algorithm, has nothing whatsoever to do with the adequacy of the definition of "formal system" and of "mechanical procedure.") (p. 72, loc. cit.)

"(For theories and procedures in the more general sense indicated in footnote ** the situation may be different. Note that the results mentioned in the postscript do not establish any bounds for the powers of human reason, but rather for the potentialities of pure formalism in mathematics.) (p. 73 loc. cit.)

Footnote **: "I.e., such as involve the use of abstract terms on the basis of their meaning. See my paper in Dial. 12(1958), p. 280." (this footnote appears on p. 72, loc. cit).

Minsky (1967) baldly asserts that "an algorithm is "an effective procedure" and declines to use the word "algorithm" further in his text; in fact his index makes it clear what he feels about "Algorithm, synonym for Effective procedure"(p. 311):

"We will use the latter term [an effective procedure] in the sequel. The terms are roughly synonymous, but there are a number of shades of meaning used in different contexts, especially for 'algorithm'" (italics in original, p. 105)

Other writers (see Knuth below) use the word "effective procedure". This leads one to wonder: What is Minsky's notion of "an effective procedure"? He starts off with:

"...a set of rules which tell us, from moment to moment, precisely how to behave" (p. 106)

But he recognizes that this is subject to a criticism:

"... the criticism that the interpretation of the rules is left to depend on some person or agent" (p. 106)

His refinement? To "specify, along with the statement of the rules, the details of the mechanism that is to interpret them". To avoid the "cumbersome" process of "having to do this over again for each individual procedure" he hopes to identify a "reasonably uniform family of rule-obeying mechanisms". His "formulation":

"(1) a language in which sets of behavioral rules are to be expressed, and

"(2) a single machine which can interpret statements in the language and thus carry out the steps of each specified process." (italics in original, all quotes this para. p. 107)

In the end, though, he still worries that "there remains a subjective aspect to the matter. Different people may not agree on whether a certain procedure should be called effective" (p. 107)

But Minsky is undeterred. He immediately introduces "Turing's Analysis of Computation Process" (his chapter 5.2). He quotes what he calls "Turing's thesis"

"Any process which could naturally be called an effective procedure can be realized by a Turing machine" (p. 108. (Minsky comments that in a more general form this is called "Church's thesis").

After an analysis of "Turing's Argument" (his chapter 5.3) he observes that "equivalence of many intuitive formulations" of Turing, Church, Kleene, Post, and Smullyan "...leads us to suppose that there is really here an 'objective' or 'absolute' notion. As Rogers [1959] put it:

"In this sense, the notion of effectively computable function is one of the few 'absolute' concepts produced by modern work in the foundations of mathematics'" (Minsky p. 111 quoting Rogers, Hartley Jr (1959) The present theory of Turing machine computability, J. SIAM 7, 114-130.)

في كتابه "نظرية الدوال التكرارية والحوسبة الفعالة" الصادر عام ١٩٦٧، يُعرّف هارتلي روجرز "الخوارزمية" تقريبًا بأنها "إجراء روتيني (أي حتمي، محاسبي)... يُطبق على... مدخلات رمزية ، وينتج عنه في النهاية، لكل مدخل من هذه المدخلات، مخرج رمزي مطابق " (ص  ١). ثم يصف المفهوم "بعبارات تقريبية وبديهية" بأنه يتضمن ١٠ "خصائص"، يؤكد أن خمسًا منها "يتفق عليها جميع علماء الرياضيات تقريبًا" (ص  ٢). أما الخصائص الخمس المتبقية، فيؤكد أنها "أقل وضوحًا من الخصائص من ١ إلى ٥، وقد لا نجد حولها اتفاقًا عامًا" (ص  ٣).

الخمسة "الواضحة" هي:

• 1- الخوارزمية هي مجموعة من التعليمات ذات حجم محدود،
• 2- يوجد وكيل حاسوبي قادر،
• 3 "توجد مرافق لإنشاء وتخزين واسترجاع الخطوات في عملية حسابية"
• 4. بالنظر إلى المعادلتين رقم 1 ورقم 2، يقوم العامل بالحساب بطريقة "متقطعة تدريجية" دون استخدام طرق مستمرة أو أجهزة تناظرية.
• 5 يقوم عامل الحوسبة بتنفيذ الحساب "دون اللجوء إلى أساليب أو أجهزة عشوائية، مثل النرد" (في حاشية يتساءل روجرز عما إذا كان #4 و #5 متطابقين حقًا).

أما النقاط الخمس المتبقية التي يفتح باب النقاش بشأنها فهي:

• 6- لا يوجد حد ثابت لحجم المدخلات،
• 7. لا يوجد حد ثابت لحجم مجموعة التعليمات،
• 8. لا يوجد حد ثابت لمقدار مساحة التخزين المتاحة،
• 9- حد ثابت ومحدود على سعة أو قدرة عامل الحوسبة (يوضح روجرز ذلك بأمثلة لآليات بسيطة مشابهة لآلة بوست تورينج أو آلة العد )،
• 10. حدٌّ أقصى لطول الحساب - "هل ينبغي أن تكون لدينا فكرة مسبقة عن المدة التي سيستغرقها الحساب؟" (ص  5). يشترط روجرز "فقط أن ينتهي الحساب بعد عدد محدود من الخطوات؛ ولا نصر على القدرة المسبقة على تقدير هذا العدد." (ص  5).

قدم كنوت (1968، 1973) قائمة بخمس خصائص مقبولة على نطاق واسع كمتطلبات للخوارزمية:

1. التناهي : "يجب أن تنتهي الخوارزمية دائمًا بعد عدد محدود من الخطوات ... عدد محدود جدًا ، عدد معقول"
2. الوضوح : "يجب تحديد كل خطوة من خطوات الخوارزمية بدقة؛ ويجب تحديد الإجراءات التي يتعين تنفيذها بدقة وبشكل لا لبس فيه لكل حالة".
3. المدخلات : "...الكميات التي تُعطى لها مبدئيًا قبل بدء الخوارزمية. تُؤخذ هذه المدخلات من مجموعات محددة من الكائنات"
4. الناتج : "...الكميات التي لها علاقة محددة بالمدخلات"
5. الفعالية : "... يجب أن تكون جميع العمليات التي سيتم تنفيذها في الخوارزمية أساسية بما يكفي بحيث يمكن من حيث المبدأ تنفيذها بدقة وفي فترة زمنية محددة بواسطة شخص يستخدم الورقة والقلم الرصاص"

يقدم كنوت كمثال الخوارزمية الإقليدية لتحديد القاسم المشترك الأكبر لعددين طبيعيين (انظر كنوت المجلد 1 ص  2).

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

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

كان كل من ستون (1972) وكنوث (1968، 1973) أستاذين في جامعة ستانفورد في نفس الوقت، لذلك ليس من المستغرب وجود أوجه تشابه في تعريفاتهما (تمت إضافة الخط الغامق للتأكيد):

"باختصار ... نحن نعرف الخوارزمية بأنها مجموعة من القواعد التي تحدد بدقة تسلسل العمليات بحيث تكون كل قاعدة فعالة ومحددة، وبحيث ينتهي التسلسل في وقت محدود." (تمت إضافة الخط الغامق، ص 8)

يُعد ستون جديرًا بالملاحظة بسبب مناقشته المفصلة لما يشكل قاعدة "فعالة" - يجب أن يمتلك الروبوت الخاص به ، أو الشخص الذي يتصرف كروبوت، بعض المعلومات والقدرات بداخله ، وإذا لم يكن الأمر كذلك، فيجب توفير المعلومات والقدرة في "الخوارزمية":

"For people to follow the rules of an algorithm, the rules must be formulated so that they can be followed in a robot-like manner, that is, without the need for thought... however, if the instructions [to solve the quadratic equation, his example] are to be obeyed by someone who knows how to perform arithmetic operations but does not know how to extract a square root, then we must also provide a set of rules for extracting a square root in order to satisfy the definition of algorithm" (p. 4-5)

Furthermore, "...not all instructions are acceptable, because they may require the robot to have abilities beyond those that we consider reasonable.” He gives the example of a robot confronted with the question is “Henry VIII a King of England?” and to print 1 if yes and 0 if no, but the robot has not been previously provided with this information. And worse, if the robot is asked if Aristotle was a King of England and the robot only had been provided with five names, it would not know how to answer. Thus:

“an intuitive definition of an acceptable sequence of instructions is one in which each instruction is precisely defined so that the robot is guaranteed to be able to obey it” (p. 6)

After providing us with his definition, Stone introduces the Turing machine model and states that the set of five-tuples that are the machine's instructions are “an algorithm ... known as a Turing machine program” (p. 9). Immediately thereafter he goes on say that a “computation of a Turing machine is described by stating:

"1. The tape alphabet

"2. The form in which the [input] parameters are presented on the tape

"3. The initial state of the Turing machine

"4. The form in which answers [output] will be represented on the tape when the Turing machine halts

"5. The machine program" (italics added, p. 10)

This precise prescription of what is required for "a computation" is in the spirit of what will follow in the work of Blass and Gurevich.

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

أثناء دراسته في جامعة برينستون في منتصف الستينيات، كان ديفيد بيرلينسكي تلميذًا لألونزو تشيرش (انظر الصفحة  160). ويحتوي كتابه الصادر عام 2000 بعنوان " ظهور الخوارزمية: رحلة 300 عام من فكرة إلى حاسوب" على التعريف التالي للخوارزمية :

" بصوت المنطقي:

" الخوارزمية هي

إجراء محدود،

مكتوبة بمفردات رمزية ثابتة،

تخضع لتعليمات دقيقة،

التحرك بخطوات منفصلة، ​​1، 2، 3، ...

ولا يتطلب تنفيذها أي بصيرة أو ذكاء.

الحدس، أو الذكاء، أو الفطنة،

وهذا سينتهي عاجلاً أم آجلاً. (الخط العريض والمائل في الأصل، صفحة 18)

إن قراءة متأنية لكتاب غوريفيتش (2000) تقود إلى استنتاج (أو استدلال) مفاده أنه يعتقد أن "الخوارزمية" هي في الواقع "آلة تورينغ" أو " آلة مؤشر " تقوم بعملية حسابية. فالخوارزمية ليست مجرد جدول الرموز الذي يوجه سلوك الآلة، وليست مجرد حالة واحدة لآلة تقوم بعملية حسابية بناءً على مجموعة معينة من معلمات الإدخال، وليست آلة مبرمجة بشكل مناسب وهي مطفأة؛ بل هي الآلة التي تقوم فعليًا بأي عملية حسابية قادرة عليها . لم يصرح غوريفيتش بذلك صراحةً، لذا فإن هذا الاستنتاج (أو الاستدلال) كما ورد أعلاه قابل للنقاش.

"... يمكن محاكاة كل خوارزمية بواسطة آلة تورينج... يمكن محاكاة البرنامج وبالتالي إعطاؤه معنى دقيقًا بواسطة آلة تورينج." (ص 1)

" It is often thought that the problem of formalizing the notion of sequential algorithm was solved by Church [1936] and Turing [1936]. For example, according to Savage [1987], an algorithm is a computational process defined by a Turing machine. Church and Turing did not solve the problem of formalizing the notion of sequential algorithm. Instead they gave (different but equivalent) formalizations of the notion of computable function, and there is more to an algorithm than the function it computes. (italics added p. 3)

"Of course, the notions of algorithm and computable function are intimately related: by definition, a computable function is a function computable by an algorithm. . . . (p. 4)

In Blass and Gurevich 2002 the authors invoke a dialog between "Quisani" ("Q") and "Authors" (A), using Yiannis Moshovakis as a foil, where they come right out and flatly state:

"A: To localize the disagreement, let's first mention two points of agreement. First, there are some things that are obviously algorithms by anyone's definition -- Turing machines, sequential-time ASMs [Abstract State Machines], and the like. . . .Second, at the other extreme are specifications that would not be regarded as algorithms under anyone's definition, since they give no indication of how to compute anything . . . The issue is how detailed the information has to be in order to count as an algorithm. . . . Moshovakis allows some things that we would call only declarative specifications, and he would probably use the word "implementation" for things that we call algorithms." (paragraphs joined for ease of readability, 2002:22)

This use of the word "implementation" cuts straight to the heart of the question. Early in the paper, Q states his reading of Moshovakis:

"...[H]e would probably think that your practical work [Gurevich works for Microsoft] forces you to think of implementations more than of algorithms. He is quite willing to identify implementations with machines, but he says that algorithms are something more general. What it boils down to is that you say an algorithm is a machine and Moschovakis says it is not." (2002:3)

But the authors waffle here, saying "[L]et's stick to "algorithm" and "machine", and the reader is left, again, confused. We have to wait until Dershowitz and Gurevich 2007 to get the following footnote comment:

" . . . Nevertheless, if one accepts Moshovakis's point of view, then it is the "implementation" of algorithms that we have set out to characterize."(cf Footnote 9 2007:6)

يصف بلاس وغوريفيتش عملهما بأنه تطور من دراسة آلات تورينغ وآلات المؤشر ، وتحديداً آلات كولموغوروف-أوسبنسكي (آلات KU)، وآلات شونهاج لتعديل التخزين (SMM)، وآلات الربط الآلية كما حددها كنوت. كما يُوصف عمل غاندي وماركوف بأنه من الأعمال المؤثرة التي سبقت هذا المجال.

يقدم غوريفيتش تعريفًا "قويًا" للخوارزمية (تمت إضافة الخط الغامق):

"...حجة تورينج غير الرسمية المؤيدة لأطروحته تبرر أطروحة أقوى: يمكن محاكاة أي خوارزمية بواسطة آلة تورينج ... عمليًا، سيكون ذلك أمرًا سخيفًا... [ومع ذلك،] هل يمكن تعميم آلات تورينج بحيث يمكن نمذجة أي خوارزمية، مهما كانت مجردة، بواسطة آلة معممة؟... ولكن لنفترض وجود مثل هذه الآلات المعممة. كيف ستكون حالاتها؟... بنية من الدرجة الأولى ... مجموعة تعليمات صغيرة محددة تكفي في جميع الحالات... الحساب كتطور للحالة ... يمكن أن تكون غير حتمية... يمكنها التفاعل مع بيئتها... [يمكن أن تكون] متوازية ومتعددة العوامل... [يمكن أن يكون لها] دلالات ديناميكية ... [الركيزتان الأساسيتان لعملهم هما:] أطروحة تورينج... [و] مفهوم بنية (الدرجة الأولى) لـ[تارسكي 1933]" (غوريفيتش 2000، ص 1-2)

يختلف تعريف الحساب المذكور أعلاه، بوصفه تطورًا للحالة، اختلافًا كبيرًا عن تعريف كنوت وستون، الذي يُعرّف "الخوارزمية" بأنها برنامج آلة تورينج. بل يُطابق هذا التعريف ما أسماه تورينج التكوين الكامل (انظر تعريف تورينج في كتابه "غير قابل للتقرير"، صفحة  118)، ويشمل كلًا من التعليمات الحالية (الحالة) وحالة الشريط. [انظر كلين (1952)، صفحة  375، حيث يُقدّم مثالًا على شريط يحتوي على 6 رموز - جميع المربعات الأخرى فارغة - وكيفية حساب حالة الجدول والشريط معًا باستخدام طريقة غودل].

في أمثلة الخوارزميات نرى تطور الحالة بشكل مباشر.

يحلل الفيلسوف دانيال دينيت أهمية التطور كعملية خوارزمية في كتابه " فكرة داروين الخطيرة" الصادر عام 1995. ويحدد دينيت ثلاث سمات رئيسية للخوارزمية:

• حيادية الركيزة : تعتمد الخوارزمية على بنيتها المنطقية . لذا، فإن الشكل المحدد الذي تظهر به الخوارزمية ليس مهمًا (مثال دينيت هو القسمة المطولة: فهي تعمل بنفس الكفاءة على الورق، أو الرق، أو شاشة الكمبيوتر، أو باستخدام أضواء النيون، أو حتى في الكتابة في السماء). (ص  ٥١)
• Underlying mindlessness: no matter how complicated the end-product of the algorithmic process may be, each step in the algorithm is sufficiently simple to be performed by a non-sentient, mechanical device. The algorithm does not require a "brain" to maintain or operate it. "The standard textbook analogy notes that algorithms are recipes of sorts, designed to be followed by novice cooks."(p. 51)
• Guaranteed results: If the algorithm is executed correctly, it will always produce the same results. "An algorithm is a foolproof recipe." (p. 51)

It is on the basis of this analysis that Dennett concludes that "According to Darwin, evolution is an algorithmic process". (p. 60).

However, in the previous page he has gone out on a much-further limb. In the context of his chapter titled "Processes as Algorithms", he states:

"But then . . are there any limits at all on what may be considered an algorithmic process? I guess the answer is NO; if you wanted to, you can treat any process at the abstract level as an algorithmic process. . . If what strikes you as puzzling is the uniformity of the [ocean's] sand grains or the strength of the [tempered-steel] blade, an algorithmic explanation is what will satisfy your curiosity -- and it will be the truth. . . .

"No matter how impressive the products of an algorithm, the underlying process always consists of nothing but a set of individualy[sic] mindless steps succeeding each other without the help of any intelligent supervision; they are 'automatic' by definition: the workings of an automaton." (p. 59)

It is unclear from the above whether Dennett is stating that the physical world by itself and without observers is intrinsically algorithmic (computational) or whether a symbol-processing observer is what is adding "meaning" to the observations.

Daniel Dennett is a proponent of strong artificial intelligence: the idea that the logical structure of an algorithm is sufficient to explain mind. John Searle, the creator of the Chinese room thought experiment, claims that "syntax [that is, logical structure] is by itself not sufficient for semantic content [that is, meaning]" (Searle 2002, p. 16). In other words, the "meaning" of symbols is relative to the mind that is using them; an algorithm—a logical construct—by itself is insufficient for a mind.

يحذر سيرل أولئك الذين يدّعون أن العمليات الخوارزمية (الحسابية) متأصلة في الطبيعة (على سبيل المثال، علماء الكونيات، والفيزيائيون، والكيميائيون، وما إلى ذلك):

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

للاطلاع على أمثلة على طريقة التحديد هذه المطبقة على خوارزمية الجمع "m+n"، انظر أمثلة الخوارزمية .

يُظهر مثال في Boolos-Burgess-Jeffrey (2002) (الصفحات  31-32) الدقة المطلوبة في تحديد كامل للخوارزمية، في هذه الحالة لجمع عددين: m+n. وهو مشابه لمتطلبات Stone المذكورة أعلاه.

(أ) لقد ناقشوا دور "تنسيق الأرقام" في الحساب واختاروا "تدوين العد" لتمثيل الأرقام:

"بالتأكيد قد يكون الحساب أصعب عمليًا مع بعض الرموز مقارنة بغيرها ... ولكن ... من الممكن من حيث المبدأ القيام بذلك بأي رمز آخر، ببساطة عن طريق ترجمة البيانات ... لأغراض صياغة مفهوم محدد بدقة للحساب، من الملائم استخدام الرمز الأحادي أو رمز العد" (ص 25-26)

(ii) في بداية مثالهم، يحددون الآلة المستخدمة في الحساب على أنها آلة تورينج . وقد سبق أن ذكروا (صفحة  26) أن آلة تورينج ستكون من نوع الرباعيات، وليس الخماسيات. لمزيد من المعلومات حول هذا الاصطلاح، انظر آلة تورينج .

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

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

"(أ) [ تنسيق الأرقام الأولي: ] سيتم تمثيل الوسائط m ₁ ، ... m _k ، ... في تدوين أحادي [أحادي] بواسطة كتل من تلك الأرقام من الضربات ، كل كتلة مفصولة عن التالية بفراغ واحد ، على شريط فارغ بخلاف ذلك.

مثال: 3+2، 111B11

"(ب) [ موقع الرأس الأولي، الحالة الأولية: ] في البداية، ستقوم الآلة بمسح الرقم 1 الموجود في أقصى اليسار على الشريط، وستكون في حالتها الأولية، الحالة 1.

مثال: 3+2، 1 ₁ 111B11

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

مثال: 3+2، 11111

(د) [ حساب ناجح - موقع الرأس عند التوقف: ] في هذه الحالة [ج] ستتوقف الآلة عن مسح الرقم 1 الموجود في أقصى اليسار على الشريط...

مثال: 3+2، 1 _ن 1111

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

مثال: B _n 11111 أو B11 _n 111 أو B11111 _n

هذه المواصفات غير مكتملة: فهي تتطلب تحديد مكان وضع التعليمات وتنسيقها في الجهاز.

(رابعاً) في جدول آلة الحالة المحدودة ، أو في حالة آلة تورينج العالمية على الشريط، و

(خامساً) جدول التعليمات بتنسيق محدد

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

للاطلاع على أمثلة على طريقة التحديد هذه المطبقة على خوارزمية الجمع "m+n"، انظر أمثلة الخوارزمية .

يبدأ سيبر بتعريف "الخوارزمية" على النحو التالي:

"بشكل غير رسمي، الخوارزمية هي مجموعة من التعليمات البسيطة لتنفيذ مهمة ما. الخوارزميات شائعة في الحياة اليومية، وتسمى أحيانًا بالإجراءات أو الوصفات (مائل في الأصل، ص 154)

"...ينصب تركيزنا الحقيقي من الآن فصاعدًا على الخوارزميات. أي أن آلة تورينج لا تعدو كونها نموذجًا دقيقًا لتعريف الخوارزمية... كل ما نحتاجه هو أن نكون على دراية كافية بآلات تورينج لنعتقد أنها تشمل جميع الخوارزميات" (ص 156)

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

"لكن لاحظ أن الترميز الأحادي لترميز الأرقام (كما في الرقم 17 المرمز بالرقم الأحادي 11111111111111111) ليس معقولاً لأنه أكبر بشكل كبير من الترميزات المعقولة حقًا، مثل الترميز الأساسي k لأي k ≥ 2." (ص 259)

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

"... يكاد لا يوجد شيء اسمه امتداد "بريء" لنموذج ذاكرة الوصول العشوائي القياسي في مقاييس الوقت الموحدة؛ إما أن يكون لدينا فقط عمليات حسابية جمعية أو يمكننا تضمين جميع تعليمات الضرب و/أو التعليمات المنطقية الثنائية المعقولة على المعاملات الصغيرة." (فان إمدي بواس، 1990:26)

فيما يتعلق بـ"لغة وصف" للخوارزميات، يُكمل سيبر العمل الذي بدأه ستون وبولوس-بورغيس-جيفري (تمت إضافة التمييز). ويُقدم لنا ثلاثة مستويات لوصف خوارزميات آلة تورينج (ص  157):

وصف عالي المستوى : "حيث نستخدم ... النثر لوصف خوارزمية، متجاهلين تفاصيل التنفيذ. في هذا المستوى، لسنا بحاجة إلى ذكر كيفية إدارة الجهاز لشريطه أو رأسه."

وصف التنفيذ : "حيث نستخدم ... النثر لوصف الطريقة التي تحرك بها آلة تورينج رأسها والطريقة التي تخزن بها البيانات على شريطها. في هذا المستوى، لا نقدم تفاصيل عن الحالات أو دالة الانتقال."

الوصف الرسمي : "... أدنى مستوى من الوصف وأكثرها تفصيلاً ... الذي يوضح بالتفصيل حالات آلة تورينج ووظيفة الانتقال وما إلى ذلك."

في دراسة يانوفسكي (2011) ^{[ 3 ]} ، عُرِّفت الخوارزمية بأنها مجموعة البرامج التي تُنفِّذ تلك الخوارزمية: حيث قُسِّمت مجموعة جميع البرامج إلى فئات تكافؤ. ورغم أن مجموعة البرامج لا تُشكِّل فئةً مستقلة، فإن مجموعة الخوارزميات تُشكِّل فئةً ذات بنية إضافية. وتبين أن الشروط التي تُحدِّد متى يكون برنامجان متكافئين هي علاقات تماسك تُضفي هذه البنية الإضافية على فئة الخوارزميات.

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

• ديفيد بيرلينسكي (2000)، ظهور الخوارزمية: رحلة 300 عام من فكرة إلى حاسوب ، دار هاركورت للنشر، سان دييغو، رقم ISBN 0-15-601391-6(غلاف ورقي)
• جورج بولوس ، جون ب. بورغيس ، ريتشارد جيفري (2002)، الحوسبة والمنطق: الطبعة الرابعة ، مطبعة جامعة كامبريدج، كامبريدج، المملكة المتحدة. ISBN 0-521-00758-5(غلاف ورقي).
• أندرياس بلاس ويوري غوريفيتش (2003)، الخوارزميات: بحث عن تعريفات مطلقة ، نشرة الرابطة الأوروبية لعلوم الحاسوب النظرية 81، 2003. يتضمن قائمة مراجع ممتازة تضم 56 مرجعًا.
• بورغين، م. الخوارزميات فائقة التكرار ، سلسلة دراسات في علوم الحاسوب، سبرينغر، 2005. ISBN 0-387-95569-0
• ديفيس، مارتن (1958). قابلية الحساب وعدم قابلية الحل . نيويورك: شركة ماكجرو هيل للنشر.. مصدر للتعريفات المهمة وبعض الخوارزميات القائمة على آلة تورينج لعدد قليل من الدوال المتكررة.
• ديفيس، مارتن (1965). غير القابل للتقرير: أوراق أساسية حول القضايا غير القابلة للتقرير، والمسائل غير القابلة للحل، والدوال القابلة للحساب . نيويورك: دار رافين للنشر.يقدم ديفيس تعليقاً قبل كل مقال. وتشمل المقالات أعمالاً لكل من غودل ، وألونزو تشيرش ، وتورينج ، وروسر ، وكلين ، وإميل بوست .
• دينيت، دانيال (1995). فكرة داروين الخطيرة . نيويورك: تاتشستون/سايمون وشوستر.
• غاندي، روبن ، أطروحة تشرش ومبادئ الآليات ، في ج. باروايز ، هـ. ج. كيسلر وك . كونين، محررين ، ندوة كلين ، شركة نورث هولاند للنشر 1980) الصفحات  123-148. تتضمن "مبادئ غاندي الأربعة الشهيرة للآليات [الحاسوبية]" "المبدأ الرابع - مبدأ السببية المحلية".
• غوريفيتش، يوري ، آلات الحالة المجردة المتسلسلة تلتقط الخوارزميات المتسلسلة ، معاملات ACM في المنطق الحسابي، المجلد 1، العدد 1 (يوليو 2000)، الصفحات 77-111. يتضمن قائمة مراجع تضم 33 مصدراً.
• كلين، سي.، ستيفن (1943). "المسندات والمكممات التكرارية" . معاملات الجمعية الرياضية الأمريكية . 54 (1): 41-73 . doi : 10.2307/1990131 . JSTOR 1990131 . أعيد طبعه في كتاب The Undecidable ، ص  255 وما بعدها. قام كلين بتنقيح تعريفه لـ "التكرار العام" وشرع في الفصل "12. النظريات الخوارزمية" ليطرح "الأطروحة الأولى" (ص  274)؛ وسيكرر هذه الأطروحة لاحقًا (في كلين 1952:300) ويسميها "أطروحة الكنيسة" (كلين 1952:317) (أي أطروحة الكنيسة ).
• كلين، ستيفن سي. (1991) [1952]. مقدمة في ما وراء الرياضيات (  الطبعة العاشرة). شركة نورث هولاند للنشر.مصدر مرجعي ممتاز - سهل الوصول إليه، وقابل للقراءة - للأسس الرياضية.
• كنوت، دونالد إي. (1973) [1968]. فن برمجة الحاسوب، الطبعة الثانية، المجلد 1/الخوارزميات الأساسية (  الطبعة الثانية). شركة أديسون-ويسلي للنشر.النص الأول من سلسلة كنوت الشهيرة المكونة من ثلاثة نصوص.
• لويس، إتش آر وباباديميتريو ، سي إتش، عناصر نظرية الحوسبة ، برنتيس هول، أبر سادل ريفر، نيوجيرسي، 1998
• ماركوف (1954) نظرية الخوارزميات . [ترجمة جاك ج. شور-كون وفريق برنامج الترجمات العلمية] منشور في موسكو، أكاديمية العلوم في الاتحاد السوفيتي، 1954 [أي القدس، إسرائيل، برنامج الترجمات العلمية، 1961؛ متوفر من مكتب الخدمات الفنية، وزارة التجارة الأمريكية، واشنطن]. الوصف: 444 صفحة،  28  سم. أُضيفت صفحة العنوان باللغة الروسية. ترجمة أعمال المعهد الرياضي، أكاديمية العلوم في الاتحاد السوفيتي، المجلد 42. العنوان الأصلي: Teoriya algerifmov. [QA248.M2943 مكتبة كلية دارتموث. وزارة التجارة الأمريكية، مكتب الخدمات الفنية، رقم OTS 60–51085.]
• مينسكي، مارفن (1967). الحوسبة: الآلات المحدودة واللامحدودة (  الطبعة الأولى). برنتيس هول، إنجلوود كليفس، نيوجيرسي.يوسع مينسكي مفهومه "...الخوارزمية - إجراء فعال..." في الفصل 5.1 قابلية الحوسبة، والإجراءات الفعالة، والخوارزميات. الآلات اللانهائية.
• روجرز، هارتلي الابن ، (1967)، نظرية الدوال التكرارية والحوسبة الفعالة ، مطبعة معهد ماساتشوستس للتكنولوجيا (1987)، كامبريدج، ماساتشوستس، ISBN 0-262-68052-1(غلاف ورقي)
• سيرل، جون (2002). الوعي واللغة . كامبريدج، المملكة المتحدة: مطبعة جامعة كامبريدج. ISBN 0-521-59744-7.
• سيلر، توماس ، (2024)، المعلوماتية الرياضية ، أطروحة التأهيل، جامعة السوربون باريس نورد،.
• سيبسر، مايكل ، (2006)، مقدمة في نظرية الحوسبة: الطبعة الثانية ، قسم تكنولوجيا دورات تومسون التابع لشركة تومسون ليرنينج، بوسطن، ماساتشوستس. ISBN 978-0-534-95097-2.
• Soare, Robert , (1995 to appear in Proceedings of the 10th International Congress of Logic, Methodology, and Philosophy of Science , August 19–25, 1995, Florence Italy), Computability and Recursion ), on the web at  ??.
• إيان ستيوارت ، الخوارزمية ، موسوعة بريتانيكا 2006.
• ستون، هارولد س. مقدمة في تنظيم الحاسوب وهياكل البيانات (طبعة 1972  ). ماكجرو هيل، نيويورك.انظر على وجه الخصوص الفصل الأول بعنوان: الخوارزميات، وآلات تورينج، والبرامج . تعريفه الموجز غير الرسمي: "... أي سلسلة من التعليمات التي يمكن أن يتبعها الروبوت تسمى خوارزمية " (ص  4).
• فان إمده بواس، بيتر (1990)، "نماذج ومحاكاة الآلات"، الصفحات 3-66، منشورة في جان فان ليوين (1990)، دليل علوم الحاسوب النظرية. المجلد أ: الخوارزميات والتعقيد ، مطبعة معهد ماساتشوستس للتكنولوجيا/إلسيفير، 1990، رقم ISBN 0-444-88071-2(المجلد أ)