Computation in the limit
کمپیوٹیبلٹی تھیوری میں، کسی فنکشن کو لمٹ کمپیوٹیبل کہا جاتا ہے اگر یہ افعال کی یکساں طور پر کمپیوٹیبل ترتیب کی حد ہو۔ حد میں قابل حساب اصطلاحات، حد تکراری اور تکراری اندازے کے مطابق بھی استعمال کی جاتی ہیں۔ کوئی بھی محدود کمپیوٹیبل افعال کے بارے میں سوچ سکتا ہے جو بالآخر درست کمپیوٹیبل اندازے کے طریقہ کار کو ان کی حقیقی قیمت پر تسلیم کرتے ہیں۔ ایک سیٹ لمٹ کمپیوٹیبل صرف اس وقت ہوتا ہے جب اس کی خصوصیت فنکشن لمٹ کمپیوٹیبل ہوتی ہے۔ اگر ترتیب D کے مقابلے میں یکساں طور پر کمپیوٹیبل ہے، تو فنکشن D میں لمٹ کمپیوٹیبل ہے۔ رسمی تعریف ایک کل فنکشن لمٹ کمپیوٹیبل ہے اگر کل کمپیوٹیبل فنکشن ایسا ہے کہ D میں کل فنکشن لمٹ کمپیوٹیبل ہے اگر D میں بھی قابل حساب کل فنکشن ہے جو مطمئن کرتا ہے۔ قدرتی اعداد کے ایک سیٹ کو حد میں کمپیوٹیبل قرار دیا جاتا ہے اگر اور صرف اس صورت میں جب اس کی خصوصیت فنکشن حد میں کمپیوٹیبل ہو۔ اس کے برعکس، سیٹ کمپیوٹیبل ہے اگر اور صرف اس صورت میں جب یہ کسی فنکشن کے ذریعہ حد میں کمپیوٹیبل ہو اور ایک دوسرا کمپیوٹیبل فنکشن ہو جو ان پٹ i لیتا ہے اور t کی اتنی بڑی قیمت واپس کرتا ہے کہ مستحکم ہو گیا ہو۔ لمٹ لیما لمٹ لیما میں کہا گیا ہے کہ قدرتی اعداد کا ایک سیٹ لمٹ کمپیوٹیبل ہے اگر اور صرف اس صورت میں جب سیٹ (خالی سیٹ کی ٹورنگ جمپ) سے کمپیوٹیبل ہو۔ رشتہ دار حد لیما میں کہا گیا ہے کہ ایک سیٹ محدود کمپیوٹیبل ہے اگر اور صرف اس صورت میں جب اس سے کمپیوٹیبل ہو۔ مزید برآں، لمٹ لیما (اور اس کا رشتہ داری) یکساں طور پر برقرار رہتا ہے۔ اس طرح کوئی فنکشن کے لیے انڈیکس سے متعلقہ کے لیے انڈیکس میں جا سکتا ہے۔ کوئی بھی انڈیکس سے کسی انڈیکس سے متعلق کچھ کے لیے بھی جا سکتا ہے جس کی حد ہوتی ہے۔ ثبوت جیسا کہ ایک [کمپیوٹیبل طور پر قابل شمار] سیٹ ہے، اسے حد میں ہی کمپیوٹیبل ہونا چاہیے کیونکہ کمپیوٹیبل فنکشن کی وضاحت کی جا سکتی ہے جس کی حد جیسا کہ انفینیٹی تک جاتی ہے اس کی خصوصیت فنکشن ہے۔ لہذا یہ ظاہر کرنا کافی ہے کہ اگر ٹورنگ کی کمی کے ذریعے محدود کمپیوٹیبلٹی کو محفوظ رکھا جائے، کیونکہ اس سے پتہ چلے گا کہ تمام سیٹ جن سے کمپیوٹیبل ہیں وہ محدود کمپیوٹیبل ہیں۔ ان سیٹوں کو ٹھیک کریں جن کی شناخت ان کے خصوصیت والے افعال اور حد کے ساتھ ایک کمپیوٹیبل فنکشن کے ساتھ کی جاتی ہے۔ فرض کریں کہ کچھ ٹورنگ کی کمی کے لیے اور ایک کمپیوٹیبل فنکشن کی وضاحت اس طرح کریں: اب فرض کریں کہ کمپیوٹیشن مراحل میں یکجا ہوتا ہے اور صرف اس کے پہلے ٹکڑوں کو دیکھتا ہے۔ اب ایسا انتخاب کریں جو سب کے لیے ہو۔ اگر تب حساب زیادہ سے زیادہ مراحل میں یکجا ہوتا ہے۔ اس لیے اس کی ایک حد ہے، اسی طرح حد قابل حساب ہے۔ چونکہ سیٹ صرف پوسٹ کے تھیوریم کے حساب سے قابل حساب سیٹ ہیں، اس لیے لمٹ لیما میں یہ بھی شامل ہے کہ لمٹ کمپیوٹیبل سیٹ سیٹ ہیں۔ قابل حساب حقیقی اعداد کو محدود کریں ایک حقیقی عدد x حد میں قابل حساب ہے اگر عقلی اعداد (یا، جو مساوی، قابل حساب حقیقی اعداد ہیں) کی ایک قابل حساب ترتیب ہے جو x میں ضم ہو جاتی ہے۔ اس کے برعکس، ایک حقیقی عدد تب اور صرف اس صورت میں قابل حساب ہوتا ہے جب عقلی اعداد کا ایک سلسلہ ہو جو اس میں ضم ہوتا ہے اور جس میں ارتکاز کا کمپیوٹیبل ماڈیولس ہوتا ہے۔ جب کسی حقیقی عدد کو بٹس کی ترتیب کے طور پر دیکھا جاتا ہے، تو درج ذیل مساوی تعریف برقرار رہتی ہے۔ بائنری ہندسوں کی ایک لامحدود ترتیب حد میں کمپیوٹیبل ہے اگر اور صرف اس صورت میں جب سیٹ میں ویلیو لینے والا کل کمپیوٹیبل فنکشن ہو تاکہ ہر i کے لیے حد موجود ہو اور برابر ہو۔ اس طرح ہر ایک i کے لیے، جیسے جیسے t بڑھتا ہے آخر کار کی قدر مستقل اور برابر ہو جاتی ہے۔ جیسا کہ کمپیوٹیبل حقیقی اعداد کے معاملے میں ہوتا ہے، حد کمپیوٹیبل حقیقی کی دو نمائندگی کے درمیان مؤثر طریقے سے حرکت کرنا ممکن نہیں ہے۔ مثالیں حقیقی جس کی بائنری توسیع رکنے کے مسئلے کو انکوڈ کرتی ہے وہ حد میں قابل حساب ہے لیکن قابل حساب نہیں ہے۔ حقیقی جس کی بائنری توسیع فرسٹ آرڈر ریاضی کے سچائی سیٹ کو انکوڈ کرتی ہے وہ حد میں قابل حساب نہیں ہے۔ چیتین کا مستقل۔ سیٹ تھیوریٹک ایکسٹینشن-ریاضیاتی درجہ بندی میں افعال کے ذریعے α-ریکرشن تھیوری کے لیے لمٹ لیما کا ایک ترمیم شدہ ورژن ہے، جو کہ کچھ قابل قبول آرڈینل کے سلسلے میں بیان کردہ درجہ بندی ہے۔ کسی دیئے گئے قابل قبول آرڈینل کے لیے،-ریاضیاتی درجہ بندی کی وضاحت کریں: ایک رشتہ آن ہے اگر یہ-تکراری ہے۔ اگر یہ کسی رشتے کا پروجیکشن ہے۔ ہے اگر اس کی تکمیل ہے۔ سے ایک جزوی فنکشن ہونے دیں۔ مندرجہ ذیل مساوی ہیں: (کا گراف) ہے۔ کمزور-تکرار میں ہے،-کمپیوٹیبل افعال کے اشارے استعمال کرنے کی-چھلانگ۔ ایک-ریکرسو فنکشن ہے جس کا تخمینہ لگ بھگ ہے۔ اس کی نشاندہی کرتا ہے کہ یا تو اور دونوں غیر متعین ہیں، یا وہ دونوں متعین اور برابر ہیں۔ سپیکر سیکوینس حوالہ جات جے شمڈہوبر، "عام کولموگوروف پیچیدگیوں کی درجہ بندی اور حد میں قابل گنتی ناقابل شمار عالمگیر اقدامات"، انٹرنیشنل جرنل آف فاؤنڈیشنز آف کمپیوٹر سائنس، 2002، بھی دیکھیں۔ آر۔ سوارے۔ بار بار قابل شمار سیٹ اور ڈگریاں۔ سپرنگر-ورلاگ 1987۔ وی۔ براٹکا۔ ٹورنگ چھلانگ اور حدود کے درمیان گالوئس تعلق۔ لاگ ان کریں۔ طریقوں کا حساب۔ سائنس۔، 2018، کمپیوٹیبلٹی تھیوری آف کمپیوٹیشن