ماشین‌های اندوختگانی (Register Machines)

منطق و نظریه رایانش (۱)

درآمد به منطق

وقتی حتی نمی‌دانید در مورد چه چیزی صحبت می‌کنید، دقیق بودن معنایی ندارد. __ جان فون نویمان

در یادداشت روند منطق با مفاهیم «الگوریتم» (و ویژگی‌های آن)، «رایانش ‌پذیری» و «مدل‌های رایانش» روبرو شدیم. در این یادداشت با یکی از این مدل‌ها موسوم به «ماشین‌های اندوختگانی» (ماشین‌های ثبات - Registers Machines)‌ آشنا و برنامه نویسی خواهیم کرد. اهمیت ماشین‌های اندوختگانی از جمله در سادگی و شهودی بودن آن‌ها در ارائه مدل از رایانش است. همان‌طور که خواهیم دید، گرچه در مدل جنریکِ ماشین‌‌های اندوختگانی، دامنه سخن (عالم سخن) آن‌ها مجموعه اعداد طبیعی است، اما هر زبان دیگر نیز می‌تواند دامنه سخن آن‌ها باشد.

نظریه رایانش - ماشین‌های اندوختگانی

^≡

۱- مقدمه و یادآوری	۶- قطعیت (Deterministic) در ماشین اندوختگانی
۲- ماشین‌های اندوختگانی (Register Machine)	۷- رایانش، رایانش‌پذیری و ماشین‌های اندوختگانی
۳- نمایش شماتیک ماشین‌های اندوختگاهی	۸- شمار‌گذاری گودل و ماشین‌های اندوختگانی
۴- برنامه نویسی ماشین‌های اندوختگانی	۹- مراجع و ارجاعی‌ها
۵- دنباله پیکربندی (Configuration) در ماشین اندوختگانی

■ مقدمه و یادآوری

اکنون که با مفاهیم «الگوریتم» (و ویژگی‌های آن)، «رایانش ‌پذیری» و «مدل‌های رایانش» آشنا هستیم، با یکی از این مدل‌ها موسوم به ماشین‌های اندوختگانی (ماشین‌های ثبات - Registers Machines)‌ از نزدیک روبرو می‌شویم.

برای یادآوری، یک مدل رایانش مدلی است که نحوه محاسبه خروجی یک تابع را با توجه به ورودی آن و نیز نحوه سازماندهی واحدهای رایانشی، حافظه‌ها و نیز ارتباط بین آتها را توصیف می‌کند↦. استفاده از مدل این امکان را فراهم می کند که درجه پیچیدگی حل یک مسئله، حل نشدنی بودن آن و درجه حل نشدن آن را اندازه گیری کرد. و همه اینها مستقل از تغییراتی است که مخصوص پیاده سازی‌ها و فناوری‌های خاص است.

پیش از ماشین‌های اندوختگانی، فهرستی از برخی مدل‌های نظری رایانش را همراه با توضیح کوتاه مرور می‌کنیم.

■ مدل‌های نظری و ماشین‌های انتزاعی

۱- نظریه توابع بازگشتی (Theory of recursive functions):

نظریه توابع بازگشتی توسط چندین منطق‌دان در دهه ۱۹۳۰ گسترش یافت. در این دهه توصیف‌های (مدل‌های) متفاوتی از رایانش (محاسبه‌پذیری کارآمد - Effective calculability - Mechanical Processes) ارائه گردید. از جمله آلونزو چرچ در سال ۱۹۳۳، کورت گودل در سال ۱۹۳۴، استفان کول کلین و آلن تورینگ در سال ۱۹۳۶، امیل پست در سال ۱۹۴۴ (که البته مدت ها قبل از انتشار کامل شده بود)).^↧ ما در یادداشت‌های بعدی نظریه توابع بازگشتی را به‌طور گسترده مرور خواهیم کرد.

1- Church, A. The Calculi of Lambda-conversion. Princeton University Press, 1985.
2- Alonzo Church (Stanford Encyclopedia of Philosophy). (2022, February 24). https://plato.stanford.edu/entries/church/
3- Adams, R. An Early History of Recursive Functions and Computability: From Gödel to Turing. Docent Press, 2011.
3- Rozsa Peter: Founder of Recursive Function Theory. (n.d.). https://www.sdsc.edu/ScienceWomen/peter.html

۲- حساب لامبدا (λ-calculus):

حساب لامبدا گونه‌ای نمادسازی برای توصیف توابع و کاربستن آنها است که توسط آلونزو چرچ در دهه ۱۹۳۰ گسترش یافت. ایده اصلی در حساب لامبدا تعریف انتزاعی تابع و کارزدن آن بر متغیرهای ورودی (آرگومان) آن است. حاصل این ایده سینتاکس (نحو زبان) کم حجم و متمرکز بر نمایاندن توابع است. برای مثال، در حساب لامبدا توابع و متغیرهای ورودی آنها در یک تراز هستند.^↧

Church, A. The Calculi of Lambda-conversion. Princeton University Press, 1985.

برای توضیح بیشتر باید اندک اشاره‌ای به تفاوت نظریه‌های گسترشی (Extensional theories) و نظریه‌های ناگسترشی↜ (Non-extensional theories) داشته باشیم. چراکه حساب لامبدا، در واقع، یک نظریه نا-گسترشی همچون قواعد رایانش است. این در مقابل با نظریه گسترشی توابع به عنوان مجموعه‌ دوتایی‌هایی مرتب است.

برای توضیح بیشتر، در منطق، گسترشی (مصداقی - Extensional) به اصولی اطلاق می‌شود که اشیا را در صورتی که دارای ویژگی‌های برونی یکسانی باشند، برابر می‌دانند (معنی مصداقی و تعریف مصداقی را ببینید). برای مثال اصل موضوع گسترش در نظریه مجموعه‌ها دو مجموعه را، به جای هر تعریف یا ساختار داخلی که ممکن است داشته باشند، بر اساس ویژگی‌های برونی آنها (اعضای آنها) برابر می‌شمارد. این در مقابل انگاره مفهومیت (Intensionality)^↧ است که به یکسانی معنی مفهومی (دلالت مفهومی) اشیا توجه دارد. برای مثال در نظریه مجموعه‌ها اعداد طبیعی بگونه زیر نمایانده می‌شوند↦:

1- Priest, G. (2016). Towards Non-being: The Logic and Metaphysics of Intentionality. Oxford University Press.
2- Intentionality (Stanford Encyclopedia of Philosophy). (2023, February 7). https://plato.stanford.edu/entries/intentionality/

۰	{}=ø
۱	{ø}
۲	{ø, {ø}}
۳	{ø, {ø},{ø,{ø}}}
..	...

و در دستگاه حساب-λ بگونه زیر نمادین می‌شوند.

۰	λfx.x
۱	λfx.f x
۲	λfx.f (f x)
۳	λfx.f (f (f x))
..	...

حساب-λ در واقع یک دستگاه منطقی - ریاضی است که عبارت‌های‌ خوش-ساخت در آن به عبارت-λ موسوم‌اند↜. می‌توان نشان داد که هر عبارت-λ در حساب-λ یک قضیه نیست و بدین معنا این دستگاه صوری سازگار است↜. بعلاوه می‌توان نشان داد: توابع رایانش‌پذیر در حساب-λ قابل بازنمایی هستند↜. [↧]

Alonzo Church, An Unsolvable Problem of Elementary Number Theory, American Journal of Mathematics, Vol. 58, No. 2. (Apr., 1936), pp. 345-363

زبان (برنامه نویسی) تابعی:

از ابتدای پیدایش برنامه نویسی، زبان‌های (برنامه نویسی) موسوم به زبان‌های تابعی (Functional Programming) ایجاد شده‌اند. چهار چوب و بنیاد آن‌ها، یعنی زبان‌های تابعی، حساب-λ است. در واقع، در برنامه نویسی تابعی تکیه بر چه باید حل شود، یعنی بیان مسئله مورد حل با عبارات‌ خوش-ساخت حساب-λ، است. این برخلاف زبان‌های برنامه نویسی بیشتر رایج دستوری (Imperative languages) است که در آن‌ها باید مسئله را بر حسب چگونگی حل آن بیان کرد. به عبارت دیگر، در برنامه نویسی تابعی، ماشین (یعنی مجری) به برنامه، یعنی به عبارات‌ خوش-ساخت حساب-λ، مقدار معنایی (semantic value) اجرایی نظیر و آن را اجرا می‌کند (به طور اجرایی آن را تعبیر می‌کند). ما در یادداشت‌های بعد حساب لامبدا را بیشتر بررسی خواهیم کرد.

۳- ماشین‌های تورینگ (Turing Machines):

در سال ۱۹۳۶، آلن تورینگ مقاله‌ای منتشر کرد که اکنون به عنوان پایه علم کامپیوتر شناخته می‌شود. در این مقاله^↦ تورینگ به تحلیل معنای دقیق الگوریتم (پی‌گیری یک روند معین برای انجام کار معین به وسیله انسان) پرداخت. برای این منظور وی انگاره «ماشین جهانی - Universal machine» و توصیف نظری آن را، آنگونه که بتواند مجموعه دستوها را رمزگشایی و اجرا کند، گستراند. [یادداشت کوتاه در باره لایب‌نیتس و «زبان جهانی» مورد نظر وی را ببینید.] ما در یک یادداشت ماشین‌های تورینگ را به تفصیل واکاوی خواهیم کرد.

Turing A. M., On Computable Numbers, With An Application To The Entscheidungsproblem , 1936.

۴- ماشین‌های اندوختگانی (Register machines):

ماشین‌های اندوختگانی در تعبیر، زیرکلاسی از کلاس مدل‌های نظری رایانش (ماشین‌های انتزاعی) هستند. پژوهشگران آغازین این ماشین‌ها شپردسون و استورگیس^↦ (J.C Shepherdson, H.E. Sturgis - ۱۹۶۳) و مینسکی^↦ (M. Minsky - ۱۹۶۱)بودند.

J. C. Shepherdson und H. E. Sturgis. Computability of recursive functions. Journal of the Association for Computing Machinery, Bd. 10 (1963), S. 217–255.

Minsky, Marvin. Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines, Annals of Mathematics. (1961) 74 (3): 437–455..

اهمیت ماشین‌های اندوختگانی از جمله در سادگی و شهودی بودن آن‌ها در ارائه مدلی از رایانش هم‌ارز ماشین‌های تورینگ است. یعنی، هر آنچه توسط ماشین تورینگ انجام شود می‌تواند با ماشین ماشین‌های اندوختگانی نیز انجام شود. درک و برنامه‌نویسی ماشین‌های ماشین‌های اندوختگانی نسبت به ماشین‌های تورینگ بسی آسانتر است که این آنها را به ابزاری مفید برای آموزش و واکاوی نظریه رایانش تبدیل می‌کند. از همین جهت است که ما بحث منطق رایانشی را با آنها آغاز می‌کنیم.

☚ در ادامه این یادداشت f را یک تابع جزئی با طرح‌واره زیر در نظر می‌گیریم:

f : ℕⁿ → ℕ

برای مثال:

f : ℕ → ℕ; f(x) = x +۱,

یا

f : ℕ^۲ → ℕ; f(x, y) = x +y.

■ ماشین‌های اندوختگانی (Register Machine)

ماشین‌های اندوختگانی یک مدل‌ نظری رایانش⇿ (ماشین انتزاعی) هستند. این ماشین‌ها از دو واحد به قرار زیر تشکیل شده‌اند:

۱- سخت‌افزار (Hardware)،

۲- نرم‌افزار (Software).

یک ماشین اندوختگانی دارای سخت‌افزار و نرم‌افزار (برنامه) ویژه خود است. به عبارت دیگر، یک ماشین اندوختگانی با سخت‌افزار و هم نرم‌افزار خود تعریف می‌شود. در ادامه این یادداشت به توصیف هر کدام (سخت‌افزار و نرم‌افزار) و نحوه ارتباط آنها را با یکدیگر خواهیم پرداخت.

• سخت افزار:

سخت‌افزار ماشین اندوختگانی شامل تعداد (متناهی یا نامتناهی) انباره (رجیستر - Register) است. در هر رجیستر می‌توان یک عدد طبیعی، یعنی یکی از اعضای مجموعه زیر:

ℕ= {۰, ۱, ۲, ۳, . . .}

ذخیره شود. رجیسترها در یک ماشین اندوختگانی با n رجیستر را به‌صورت:

R_۰, R_۱, R_۲ ,. . ., R_n

نشان می‌دهیم که در آن اندیس i شماره رجیستر است. ما همچنین مقدار محتوای رجیستر R_i را به صورت r_i نشان می‌دهیم و فرض می‌کنیم که مقدار هر رجیستر به‌طور پیش‌فرض صفر است. در شکل زیر سه رجیستر به نمایش درآمده است.

رجیستر در ماشین اندوختگانی — نمایشی از سخت‌افرار (۳ رجیستر) در یک وضعیت از یک ماشین اندوختگانی.

از یک ماشین اندوختگانی با تعداد محدود رجیستر (Limited registered machine) با کوته نام‌های RM و تعداد نامحدود رجیستر (Unlimited registered machine) با URM یاد می‌کنیم.

• برنامه (نرم‌افزار)

یک برنامه برای یک ماشین اندوختگانی با n رجیستر شامل تعداد محدود دستورالعمل (instruction) است. هر دستور از دو بخش برچسب و بدنه مطابق زیر تشکیل شده است:

label : body,

به قسمی که:

• i+۱ امین دستور دارای برچسب L_i باشد (یعنی برچسب اولین دستور L₀ باشد).

• بدنه هر دستور العمل به یکی از صورت‌های زیر باشد:

صورت دستور (instruction) در ماشین‌های اندوختگانی. در ادامه و در مثال‌هایی که خواهد آمد روش کارزدن آنها (نوشتن برنامه) آشکار خواهد شد.
به محتوای رجیستر R عدد ۱ افزوده شود و اجرا به دستور L_k پرش نماید. (اگر در فهرست برنامه دستوری یا برچسب L_k نباشد اجرای برنامه به‌طور خطا پایان می‌یابد).	R⁺→L_k	I
اگر محتوای R بزرگنر از 0 است عدد ۱ از آن کسر و اجرا به دستور L_k پرش نماید، وگرنه اجرا به دستور L_j پرش نماید.	R^-→L_k, L_j	II
اجرای برنامه پایان یابد.	HALT	III

یک ماشین اندوختگانی در دو حالت (بد / خوب) متوقف می‌شود:

۱- توقف نابجا (توقف بد): هنگامی که دستور جاری (در حال اجرا) به برچسبی برای پرش اشاره کند که در لیست برنامه نیست.

۲- توقف بجا (توقف خوب): هنگامی که دستور جاری HALT است یا پس از اجرای دستور جاری دستور بعدی وجود نداشته باشد.

■ نمایش شماتیک ماشین‌های اندوختگاهی

کاردستور‌های ماشین‌های اندوختگانی را می‌توان به‌صورت شماتیک، به شیوه‌ای که در پی می‌آید، نمایش داد. به این صورت که رجیسترها را با دایره‌هایی (گره‌ها nodes) که نام رجیستر درون آن آمده است نشان می‌دهیم و با پیکان‌ها نحوه اجرای برنامه موردنظر (هدایت ماشین برای اجرای برنامه) را مشخص می‌کنیم. به این شیوه می‌توان یک ماشین اندوختگانی را به‌صورت شماتیک نشان داد. در زیر شمای کاردستور‌ها همراه شرح آن آمده است.

یک واحد به مقدار رجیستر R افزوده ‌می‌شود و کنترل اجرای برنامه به گره‌ای که با پیکان سیاه (→) اشاره شده است منتقل می‌گردد.	R⁺→L_k	I
در صورت امکان یعنی، مقدار R بزرگتر از صفر باشد، یک واحد از مقدار رجیستر R کاسته می‌شود و کنترل اجرای برنامه به گره‌ای که با پیکان سیاه (→) اشاره شده است منتقل می‌گردد. در غیر این صورت کنترل اجرای برنامه به گره‌ای که با پیکان سبز (→) اشاره شده می‌گردد.	R^-→ L_k,L_j	II
پایان اجرای کار ماشین.	HALT	III
این شمایل به گره آغازین اجرای ماشین اشاره می‌کند. گرچه این دستور در جدول بالا (دستورهای برنامه‌ای) گنجانده نشده است، اما همانطور که خواهیم دید این شمایل در نمایش شماتیک ماشین مورد نیاز است.		•

■ برنامه نویسی ماشین‌های اندوختگانی

• مثال ۱

برنامه زیر عدد ۱ را به محتوای جاری R₀ می‌افزاید، سپس اجرای برنامه به دستور با برچسب L₁ منتقل می‌شود. دستور با برچسب L₁ فرمان پایان کار ماشین است. بنابراین ماشین متوقف می‌شود.

L₀: R₀⁺ → L₁
L₁: HALT

این برنامه را می‌توان به‌صورت شماتیک در زیر نشان داد:

ماشین اندوختگانی — در این شِما، ماشین بعد از افزودن یک واحد (نشان "+" بالای پیکان) به مقدار محتوی R₀ متوقف می‌شود.

• مثال ۲

برنامه زیر عدد ۱ را در صورت امکان، یعنی وقتی r₀>۰، از محتوای جاری R₀ کاسته و سپس ماشین به دستور با برچسب L₁ منتقل می‌شود و اجرای برنامه پایان می‌یابد. در غیر این‌صورت نیز به دستور با برچسب L₁ منتقل می‌شود و برنامه پایان می‌یابد.

Start
L₀: R₀^- → L₁, L₁
L₁: HALT

این برنامه را می‌توان به‌صورت شماتیک در زیر نشان داد:

• مثال ۳

برنامه این مثال رجیستر R₀ را خالی می‌کند، سپس ماشین به دستور با برچسب L₁ منتقل می‌شود و برنامه پایان می‌یابد. بعبارت دیگر، این برنامه رجیستر R₀ را در صورت خالی نبودن خالی می‌کند (r₀=۰).

L₀: R₀^- → L₀, L₁
L₁: HALT

فرض می‌کنیم در پیکربندی آغازین r₀=2. این برنامه را می‌توان به‌صورت شماتیک در زیر نشان داد:

ماشین اندوختگانی (Register machine in computer science) و برنامه آن — در این شِما، ماشین بعد از تکرار متناهی (چرخه کراندار) دستور L₀ (کاهش) رجیستر R₀ خالی شده و ماشین متوقف می‌شود.

■ دنباله پیکربندی (Configuration) در ماشین اندوختگانی

فرض کنید یک ماشین اندوختگانی دارای n+۱ رجیستر باشد است. به دنباله C_l در زیر،

C_l = (l, r_۰, r_۱, . . . r_i . . ., r_n)

که در آن l برچسب دستور العمل و r_i محتوی جاری رجیستر R_i است یک پیکربندی ماشین اندوختگانی (configuration) گفته می‌شود. برای نمونه، دنباله پیکربندی‌ ماشین مثال ۳ در بالا به قرار زیر است.

C_۰ = (0, ۲),
C_۱ = (0, ۱),
C_۲ = (0, ۰),
C_۳ = (1, ۰)

■ قطعیت (Deterministic) در ماشین اندوختگانی

ماشین‌های اندوختگانی قطعی (Deterministic) هستند⇿، یعنی در هر پیکربندی، جز از پیکربندی توقف، پیکربندی بعد به‌طور یگانه (قطعی) بوسیله برنامه معین می‌گردد.

• مثال ۴ (ماشین ابدی)

ماشین اندوختگانی این مثال که در زیر آمده است هرگز از کار بازنمی‌ایستد (.مسئله توقف را ببینید.)

L₀: R₀⁺ → L₁
L₁: R₀^- → L₀, L₂
L₂: HALT

• مثال ۵ - ماشین واریز

• مثال ۶ - ماشین جمع

ماشین این مثال دارای سه رجیستر R₁، R₀ و R₂ است. این ماشین حاصل جمع مقادیر آغازین موجود در رجسیترهای R₁ و R₂ را در R₀ ذخیره می‌کند. به عبارت دیگر، این ماشین هم‌ارز تابع f بقرار زیر است:

f : ℕ^۲ → ℕ; f(x, y) = x + y.

• مثال ۷ - ماشین ضرب صحیح

فرض کنید تابع f به قرار زیر باشد:

f : ℕ^۲ → ℕ; f(x, y) = x × y.

ماشین این مثال مقدار تابع f را برای مقادیر ورودی‌های (مقدار متغیرها) آن، یعنی x و y، در رجیستر R₀ برمی‌گرداند

در این ماشین:

۱- در پیکربندی آغازین ورودی‌های تابع، یعنی x و y، بترتیب در R₁ و R₂ ذخیره شده‌اند و مقدار R₀ و نیز R₃ صفر فرض شده است.

۲- ماشین تابع f، یعنی ضرب x در y، را در دو چرخه تکرار (چرخه بیرونی و چرخه درونی) محاسبه می‌کند. این محاسبه با کاهش ضرب به جمع یعنی:

انجام می‌شود.

۳- چرخه بیرونی: در هر دور این چرخه‌ی تکرار یک واحد از R₁، که مقدار آغازین آن x است تا زمانی که مقدار آن صفر نشده کاسته می‌شود.

۴- چرخه درونی: در هر دور این چرخه‌ی تکرار، به ازای هر دور چرخه بیرونی یک واحد از R₁ تازمانی که صفر نشده کاسته شده و یک واحد به R₀ و R₃ افزوده می‌شود.

۴- در پایان دور اول این چرخه به مقدار R₀ (که در پایان دور اول y است) مقدار y افزوده شده و R₃ دارای مقدار y می‌گردد (مقدار y برای دور بعدی در R₃ ذخیره می‌شود).

۵- در خروج از چرخه درونی مقدار R₃ که y است در R₂ که اکنون صفر است واریز و R₃ صفر می‌شود.

• مثال ۸ - ماشین تفریق کوتاه شده

ماشین این مثال تابع زیر است:

در پایان اجرای برنامه مقدار تابع به ازای مقادیر ورودی‌های آن (مقدار متغیرها)، یعنی x و y، در رجیستر R₀ ذخیره می‌شود.

• مثال ۹ - ماشین تقسیم صحیح (تابع کامل)

ماشین این مثال تابع (کامل) زیر است:

قطعه کد زیر برنامه ماشین این مثال، یعنی تقسیم صحیح، است.

L0: if (r[2]> 0) { r[2]--; goto L1; } else goto L2;
L1: if (r[1] > 0) { r[1]--; goto L0; } else goto HALT;
L2: if (r[1] > 0) { r[1]--; goto L3; } else goto HALT;
L3: r[0]++; goto L1;
HALT:

• مثال ۹.۱ - ماشین تقسیم صحیح (تابع جزئی)

ماشین این مثال تابع جزئی زیر است:

• مثال ۱۰ - ماشین افکنش (تصویر) - projection function

ماشین این مثال تابع زیر است:

در پایان اجرای برنامه مقدار تابع به ازای مقادیر ورودی‌های آن (مقدار متغیرها)، یعنی n و z ،y در رجیستر R₀ ذخیره می‌شود.

■ رایانش، رایانش‌پذیری و ماشین‌های اندوختگانی

باتوجه به آنچه تا اینجا آمده است اکنون می‌گوییم:

یک رایانش (Computing) در ماشین اندوختگانی عبارت است از یک دنباله متناهی (یا نامتناهی) به قرار:

C₀, C₁, C₂ , . . .

که عناصر این دنباله عبارت‌اند از:

C₀ = (0, r₀, r₁, r₂ ,. . ., r_n)

. . .
. . .

C_l = (l, r₀, r₁, r₂ ,. . ., r_n)

. . .
. . .

به قسمی که در آن، C₀ پیکربندی آغازین و هر عضو دنباله مانند C_l تعیین کننده پیکربندی بعدی (در صورت وجود) توسط اجرای دستور L_l با مقادیر

r₀, r₁, r₂ ,. . ., r_n

باشد.

در یک رایانش متناهی داریم:

C₀, C₁, C₂ , . . ., C_m.

در این صورت آخرین پیکربندی، یعنی C_m یک پیکربندی توقف خواهد بود.

در صورت نامتناهی بودن دنباله پیکربندی یعنی:

C₀, C₁, C₂ , . . .

ماشین اندوختگانی متوفف شدنی نیست.

ماشین اندوختگانی و تابع

رابطه بین محتوای رجیستر‌ها در پیکربندی آغازین و پیکربندی پایانی یک تابع جزئی از ℕⁿ در ℕ است. برای نمونه، رابطه‌های بین محتوای رجیستر‌ها در پیکربندی آغازین ماشن‌های جمع (مثال ۶)، ضرب (مثال ۷)، تفریق کوتاه شده (مثال ۸)، تقسیم صحیح (مثال ۹) و افکنش (۱۰) هر یک تابع هستند.

اکنون می‌توان گفت توابع جمع (مثال ۶)، ضرب (مثال ۷)، تفریق کوتاه شده (مثال ۸)، تقسیم صحیح (مثال ۹) و افکنش (۱۰) هر یک رایانش‌پذیر هستند.

☚ نکته مورد توجه این است که ماشین‌های اندوختگانی متفاوتی می‌توانند باشند که همگی یک تابع جزئی یکسانی را محاسبه کنند.

رایانش‌پذیری (Computability)

تابع f : ℕⁿ → ℕ را رایانش‌پذیر (تابع رایانش‌پذیر) گوییم اگر ماشین اندوختگانی RM با حداقل n+۱ (یا بیشتر) رجیستر از قرار:

R₀, R₁, . . ., R_n

وجود داشته باشد به قسمی که رایانش ماشین RM برای هر

(x_۰, . . ., x_n) ∈ ℕⁿ

و با پیکربندی آغازین:

R₀ ← 0, R₁ ← x₁, . . . , R_n ← x_n

با R₀ ← y (و مقدار صفر برای بقیه رجیسترها) پایان یابد؛ به قسمی که اگر و فقط اگر داشته باشیم:

f (x₁, . . . ,x_n) = y.

الگوریتم و ماشین اندوختگانی

از آنجاکه ماشین‌های اندوختگانی ویژگی‌های بنیادین الگوریتم را برمی‌آ‌‌ورد.↝، الگوریتم‌های پیاده سازی شده توسط زبان‌های برنامه نویسی (مانند C، Java، پایتون و مانند آن‌ها) قابل برگردان به برنامه‌های ماشین‌های اندوختگانی هستند. به عبارت دیگر، هرآنچه توسط ماشین‌های اندوختگانی رایانش‌پذیر باشد، توسط زبان‌های برنامه نویسی قابل پیاده سازی است و نیز وارون آن هم چنین است.

زبان‌های برنامه‌نویسی مانند Dlvik و Lua وجود دارند که بر روی ماشین‌های اندوختگانی به عنوان ماشین مجازی طراحی شده‌اند و کاربردهای عملی خود را نیز یافته‌اند. نرم افزار این زبان‌ها به عنوان ماشین‌های مجازی روی سیستم‌عامل‌ها قابل نصب و استفاده هستند.

■ شمار‌گذاری گودل و ماشین‌های اندوختگانی

شمار‌گذاری گودل روشی است برای نسبت دادن اعداد طبیعی به نمادها و عبارت‌های یک زبان که کورت گودل برای اثبات (فرا)قضیه‌های تمامیت و ناتمامیت آن را گستراند. ما در یادداشت «نگارش (نحو) صورت و الگوریتم آن در منطق» برای نشان دادن شمارش‌پذیر بودن مجموعه فرمول‌های-خوش ساخت در منطق از شمارگذاری گودل استفاده کردیم. در یادداشت نظریه توابع بازگشتی نشان می‌دهیم که تابعی رایانش‌پذیری (برنامه - الگوریتمی) هست که می‌تواند به هر الفبا و در نتیجه عبارت‌های یک زبان یک عدد طبیعی یکتا نظیر کند (تابع جفت سازی را ببینید).

دو نتیجه از شمار‌گذاری گودل می‌توان گرفت:

۱- در یک شمارگذاری معین می‌توان به هر ماشین اندوختگانی (برنامه آن) عدد طبیعی یکتا را نظیر کرد. بنابراین، دنباله زیر را می‌توان دنباله همه‌ی ماشین‌های اندوختگانی انگاشت، یعنی می‌توانیم بنویسیم:

<RM_۰, RM_۱, . . ., RM_j, . . .>.

نیز:

{RM_۰, RM_۱, . . ., RM_j, . . .}.

در مجموعه بالا RM_l و RM_k وقتی k≠l دو ماشین متفاوت هستند که می‌توانند هر دو اجرا کننده دو تابع هم‌ارز باشند. بنابراین دوتایی مرتب زیر را داریم:

RM<i, X>; X = (x_۰, . . ., x_j . . , x_n); x_j ∈ ℕ

نیز

URM<i, X>;X = (x_۰,. . ., x_j . . , x_n);x_j ∈ ℕ

که در آن i∈ℕ نماینده کلاس هم‌ارزی همه توابعی است که ماشین RM_i برای ورودی X آن را رایانش می‌کند.

۲- گرچه ماشین‌های اندوختگانی با اعداد طبیعی کار می‌کنند، اما شمار‌گذاری گودل امکان استفاده از هر زبانی را برای این ماشین‌ها فراهم می‌کند.

بنابراین، برای توابع بنیادی زبان، یعنی پاره‌ آغازی، پاره پایانی، الحاق و طول را که در یادداشت زبان دیدیم، می‌توان ماشین‌های نظیر را ساخت.

■ معرفی کوتاه ماشین‌های تورینگ (Turing's Machines)

در بالا↝ چند خط درباره ماشین‌های تورینگ به عنوان مدل رایانش توضیح داده شده است. از آنجایی که در قسمت‌های بعدی، یعنی پیش از اینکه به تفصیل به ماشین‌های تورینگ بپردازیم، چند جا به ماشین‌های تورینگ اشاره خواهد شد، در این بند کمی بیشتر ولی بازهم چند خط درباره آنها توضیح بیشتر می‌دهیم.

در واقع ماشین‌های تورینگ بسیار شبیه کامپیوترهای امروزی هستند. برای مثال، یک ماشین تورینگ دارای یک نوار است که می‌توان روی آن ورودی را نوشت و خروجی را نیز چاپ کرد. برای سادگی، یک ماشین تورینگ را می‌توان یک کامپیوتر تک منظوره برای برنامه‌ای که در آن حک (embedded) شده است در نظر گرفت. اما نکته اصلی ما در اینجا این است که ماشین‌های تورینگ و ماشین‌های اندوختگانی هم‌ارز هستند. یعنی، به ازای هر ماشین اندوختگانی یک ماشین تورینگ با همان کارکرد داریم و نیز وارون آن. پس می‌توان از دنباله ماشین‌های تورینگ، نام برد، یعنی:

<T> = T_۰, T_۱, . . ., T_i, . . .

که در آن T_i ماشین تورینگی است که برنامه آن تابع f_i است. در زیر شمای کلی از نحوه کار یک ماشین تورینگ آمده است.

در این حالت ماشین متوقف می‌شود (ماشین پایان دار است).	f(x).	آنگاه	f(x)↓	اگر:		⇚	خروجی ماشین T_i با ورودی x <i, x>
در این حالت ماشین برای همیشه در حالت اجرا خواهد ماند (ماشین متوقف نمی‌شود / ماشین بی‌پایان است).	.	آنگاه	f(x)↑	اگر:		⇚	خروجی ماشین T_i با ورودی x <i, x>

و همین‌طور می‌توان از دوتایی

T<i, x>

نام برد، که در آن i شناسه ماشین تورینگ و x ورودی (یا ورودی‌های) آن برای رایانش برنامه است و نیز نوشت:

RM<i, r> ≡ T<i, x> ; r = x

[فون نویمان معمار منطقی کامپیوترهای رایح را ببینید و نیز در اینجا در باره Z1 اولین کامپیوتر قابل برنامه نویسی بخوانید).

منابع و ارجاعات

1- Deutsch, Harry and Oliver Marshall, "Alonzo Church", The Stanford Encyclopedia of Philosophy (Summer 2022 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/sum2022/entries/church/>.

3- Church, A. (1985a). The Calculi of Lambda Conversion. (AM-6) (Annals of Mathematics Studies). In Princeton University Press eBooks. Princeton University Press. http://dl.acm.org/citation.cfm?id=1096495

4- Adams, R. J. L. (2011). An Early History of Recursive Functions and Computability from Godel to Turing.

5- Priest, G. (2016). Towards Non-being: The Logic and Metaphysics of Intentionality. Oxford University Press.

6- Intentionality (Stanford Encyclopedia of Philosophy). (2023, February 7). https://plato.stanford.edu/entries/intentionality/

7- Alonzo Church (Apr., 1936). An Unsolvable Problem of Elementary Number Theory, American Journal of Mathematics, Vol. 58, No. 2.

8- https://mathshistory.st-andrews.ac.uk/Biographies/Post/. URL = <https://mathshistory.st-andrews.ac.uk/Biographies/Post/>

9- Rózsa Péter The Founder of Recursive Function Theory. URL = <https://www.sdsc.edu/ScienceWomen/peter.html>

10- Alama, Jesse and Johannes Korbmacher, "The Lambda Calculus", The Stanford Encyclopedia of Philosophy (Summer 2021 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/sum2021/entries/lambda-calculus/>.

11- Jacob, Pierre, "Intentionality", The Stanford Encyclopedia of Philosophy (Spring 2023 Edition), Edward N. Zalta & Uri Nodelman (eds.), URL = <https://plato.stanford.edu/archives/spr2023/entries/intentionality/>.

12- J. C. Shepherdson und H. E. Sturgis. (1963). Computability of recursive functions. Journal of the Association for Computing Machinery, Bd. 10 , S. 217–255.

13-Minsky, Marvin. (1961). Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines, Annals of Mathematics. 74 (3): 437–455.

14- Jeffrey, R. C. (2006). Formal Logic: Its Scope and Limits. Hackett Publishing Company, Inc.; Fourth Edition.

15- Robic, B. (2015). The Foundations of Computability Theory. In Springer eBooks. Springer Nature.

16- Theory of Recursive Functions and Effective Computability. Journal article·1969·Feferman, Rogers·Mathematical Association of America.