حساب کاربری
​
زمان تقریبی مطالعه: 1 دقیقه
لینک کوتاه

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

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

) و قضیه ماشین تورینگ جهانی فراهم می‌کند.

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

فرض کنید φ 1 , φ 2 , φ 3 , … {\displaystyle {\varphi _{1},}{\varphi _{2},}{\varphi _{3},}\ldots }

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

u : {\displaystyle {u:}}

N 2 {\displaystyle {\mathbb {N} ^{2}}}
⟶ {\displaystyle \longrightarrow }
N {\displaystyle \mathbb {N} }

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

u ( i , x ) {\displaystyle {u(i,x)}}

:= {\displaystyle {:=}}
φ i {\displaystyle {\varphi _{i}}}
( {\displaystyle {(}}
x {\displaystyle {x}}
) {\displaystyle {)}}

i , x {\displaystyle {i,x}}

∈ {\displaystyle \in }
N {\displaystyle \mathbb {N} }

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

تابع u {\displaystyle {u}}

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

منابع

    آخرین نظرات
    کلیه حقوق این تارنما متعلق به فرا دانشنامه ویکی بین است.