قضیه ماشین تورینگ جهانی

قضیهٔ ماشین تورینگ جهانی در نظریه محاسبات یک نتیجهٔ پایه ای از شماره گذاری های گودل برای مجموعه توابع شمارش پذیر می‌باشد . این قضیه وجود یک تابع شمارش پذیر جهانی را اثبات می‌کند که قادر به محاسبهٔ هر تابع شمارش پذیر دیگر می‌باشد . این تابع جهانی یک نسخهٔ انتزاعی از ماشین تورینگ جهانی است و به همین دلیل اسم آن را بر روی این قضیه گذاشته‌اند. قضیه ی هم ارزی راجرز یک مشخص سازی از شماره گذاری گودل برای توابع شمارش پذیر را ازنظر قضیه پارامترسازی ( $S_{m}n$) و قضیه ماشین تورینگ جهانی فراهم می‌کند.

قضیه ی ماشین تورینگ جهانی

فرض کنید ${\phi }_1,{\phi }_2,{\phi }_3,\dots$ یک شماره گذاری از شماره‌های گودل برای توابع شمارش پذیر باشد. آنگاه تابع جزئی

$u:$ ${\mathbb{N}}^2$ $⟶$ $\mathbb{N}$

که به صورت زیر تعریف می‌شود

$u(i,x)$ $:=$ ${\phi }_i$ $($ $x$ $)$

$i,x$ $\in$$\mathbb{N}$

قابل شمارش می‌باشد .

تابع $u$ را تابع جهانی می نامند.

منابع

• الگو:یادکرد ویکی