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

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

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

فرض کنید ${\varphi _{1},}{\varphi _{2},}{\varphi _{3},}\ldots$ یک شماره گذاری از شماره‌های گودل برای توابع شمارش پذیر باشد. آنگاه تابع جزئی

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

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

${u(i,x)}$ ${:=}$ ${\varphi _{i}}$ ${(}$ ${x}$ ${)}$

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

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

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

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «utm theorem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۸ دی ۱۳۹۳.