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

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

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

فرض کنید  یک شماره گذاری از شماره‌های گودل برای توابع شمارش پذیر باشد. آنگاه تابع جزئی 



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





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

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

 منابع 

رده:قضیه‌ها در نظریه محاسبات
رده:نظریه بازگشت
رده:نظریه محاسبات