Low basis theorem
کم بنیاد تھیوریم کمپیوٹیبلٹی تھیوری میں کئی بنیادی تھیوریمز میں سے ایک ہے، جن میں سے ہر ایک یہ ظاہر کرتا ہے کہ، بائنری ٹری کی ایک لامحدود ذیلی ٹری کو دیکھتے ہوئے، مخصوص کمپیوٹیبلٹی خصوصیات کے ساتھ ٹری کے ذریعے ایک لامحدود راستہ تلاش کرنا ممکن ہے۔ لو بیس تھیوریم، خاص طور پر، یہ ظاہر کرتا ہے کہ ایک ایسا راستہ ہونا چاہیے جو کم ہو ؛ یعنی، راستے کی ٹورنگ جمپ ٹورنگ کو روکنے کے مسئلے کے مساوی ہے۔ بیان اور ثبوت کم بنیاد تھیوریم میں کہا گیا ہے کہ (ریاضیاتی درجہ بندی دیکھیں) میں ہر غیر خالی کلاس کم ڈگری (Soare 1987:109) کا ایک مجموعہ پر مشتمل ہے۔ یہ تعریف کے لحاظ سے اس بیان کے مساوی ہے کہ بائنری ٹری کے ہر لامحدود کمپیوٹیبل سبٹری کا کم ڈگری کا لامحدود راستہ ہوتا ہے۔ ثبوت کلاسوں کے ساتھ مجبور کرنے کا طریقہ استعمال کرتا ہے (کوپر 2004:330)۔ ہجک اور کوسیرا (1989) نے دکھایا کہ کم بنیاد ریاضی کے رسمی نظام میں قابل ثبوت ہے جسے کے نام سے جانا جاتا ہے۔ مجبور کرنے والی دلیل کو بھی واضح طور پر اس طرح وضع کیا جا سکتا ہے: کسی سیٹ X ω کے لیے، فرض کریں کہ f (X) = σ {i} (X) ω2 − i، جہاں {i} (X) ω کا مطلب ہے کہ ٹورنگ مشین i X پر رکتی ہے (اس طرح کے تمام i پر جمع ہونے کے ساتھ)۔ پھر، ہر نان ایمپٹی (لائٹ فیس) S2ω کے لیے، کم سے کم f (X) کرنے والے (منفرد) XωS میں کم ٹورنگ ڈگری ہوتی ہے۔ اسے دیکھنے کے لیے، جس کا حساب 0′ سے i پر انڈکشن کے ذریعے لگایا جا سکتا ہے، {i} (X) ′ ′ ′ ′ Y ω ω ω ω ω (X) ω) φ کے لیے ہے۔ دوسرے لفظوں میں، آیا کوئی مشین X پر رکتی ہے، اسے ایک محدود شرط کے ذریعے مجبور کیا جاتا ہے، جس میں X′ = 0′ کی اجازت ہوتی ہے۔ لو بیس تھیوریم کا ایک اطلاق موثر نظریات کی تکمیل کی تعمیر کرنا ہے تاکہ تکمیل میں کم ٹورنگ ڈگری ہو۔ مثال کے طور پر، کم بنیاد تھیوریم پی اے ڈگریوں کے وجود کو سختی سے نیچے ظاہر کرتا ہے۔ حوالہ جات۔ اصل اشاعت، بشمول اضافی وضاحتی عبارت۔ نظریہ 1.8.37۔ کمپیوٹیبلٹی نظریہ