Computation in the limit
গণনাযোগ্যতা তত্ত্বে, একটি ফাংশনকে সীমা গণনাযোগ্য বলা হয় যদি এটি ফাংশনের অভিন্ন গণনাযোগ্য ক্রমের সীমা হয়। সীমাতে গণনাযোগ্য, সীমাবদ্ধ পুনরাবৃত্তিমূলক এবং পুনরাবৃত্তিমূলক আনুমানিক শব্দগুলিও ব্যবহার করা হয়। সীমিত গণনাযোগ্য ফাংশনগুলি তাদের প্রকৃত মূল্যে শেষ পর্যন্ত সঠিক গণনাযোগ্য অনুমান পদ্ধতি স্বীকার করে বলে মনে করা যেতে পারে। একটি সেট তখন সীমাবদ্ধ গণনাযোগ্য হয় যখন তার বৈশিষ্ট্যমূলক ফাংশন সীমাবদ্ধ গণনাযোগ্য হয়। যদি ক্রমটি ডি-এর তুলনায় সমানভাবে গণনাযোগ্য হয়, তবে ফাংশনটি ডি-তে সীমাবদ্ধ গণনাযোগ্য। আনুষ্ঠানিক সংজ্ঞা একটি মোট ফাংশন সীমিত গণনাযোগ্য যদি মোট গণনাযোগ্য ফাংশন থাকে যেমন ডি-তে গণনাযোগ্য মোট ফাংশনও সন্তোষজনক হয় তবে মোট ফাংশনটি ডি-তে সীমাবদ্ধ গণনাযোগ্য। প্রাকৃতিক সংখ্যার একটি সেট সীমাতে গণনাযোগ্য হিসাবে সংজ্ঞায়িত করা হয় যদি এবং শুধুমাত্র যদি তার বৈশিষ্ট্যমূলক ফাংশন সীমাতে গণনাযোগ্য হয়। বিপরীতে, সেটটি গণনাযোগ্য হয় যদি এবং শুধুমাত্র যদি এটি একটি ফাংশন দ্বারা সীমার মধ্যে গণনাযোগ্য হয় এবং একটি দ্বিতীয় গণনাযোগ্য ফাংশন থাকে যা ইনপুট i নেয় এবং স্থির হওয়ার মতো যথেষ্ট বড় t এর মান প্রদান করে। লিমিট লেম্মা বলে যে প্রাকৃতিক সংখ্যার একটি সেট সীমাবদ্ধ গণনাযোগ্য যদি সেটটি গণনাযোগ্য হয় (খালি সেটের টুরিং জাম্প)। আপেক্ষিক সীমা লেমা বলে যে একটি সেট যদি এবং শুধুমাত্র যদি থেকে গণনাযোগ্য হয় তবে সীমাবদ্ধ গণনাযোগ্য। উপরন্তু, সীমা লেম্মা (এবং এর আপেক্ষিকতা) সমানভাবে ধরে রাখে। এইভাবে ফাংশনটির জন্য একটি সূচক থেকে আপেক্ষিক জন্য একটি সূচকে যেতে পারে। কেউ কেউ একটি সূচক থেকে একটি সূচকের আপেক্ষিক হিসাবেও যেতে পারে যার সীমা রয়েছে। প্রমাণ যেহেতু একটি [গণনাযোগ্যভাবে গণনাযোগ্য] সেট, এটি অবশ্যই সীমার মধ্যেই গণনাযোগ্য হতে হবে কারণ গণনাযোগ্য ফাংশনকে সংজ্ঞায়িত করা যেতে পারে যার সীমা অসীমের বৈশিষ্ট্যমূলক ফাংশন। তাই এটা দেখানোর জন্য যথেষ্ট যে, টুরিং হ্রাসের মাধ্যমে যদি সীমাবদ্ধ গণনাযোগ্যতা বজায় রাখা হয়, কারণ এটি দেখাবে যে, গণনাযোগ্য সমস্ত সেটই সীমাবদ্ধ গণনাযোগ্য। সেটগুলি স্থির করুন যা তাদের বৈশিষ্ট্যমূলক ফাংশন এবং সীমা সহ একটি গণনাযোগ্য ফাংশন দিয়ে চিহ্নিত করা হয়। ধরুন যে কিছু টুরিং হ্রাসের জন্য এবং একটি গণনাযোগ্য ফাংশনকে নিম্নরূপ সংজ্ঞায়িত করুন। এখন সবার জন্য এমনটা বেছে নিন। যদি তারপর গণনা সর্বাধিক ধাপে একত্রিত হয়। অতএব এর একটি সীমা রয়েছে, তাই সীমা গণনাযোগ্য। যেহেতু সেটগুলি পোস্টের উপপাদ্য দ্বারা গণনাযোগ্য সেট, তাই সীমা লেমা এও বোঝায় যে সীমা গণনাযোগ্য সেটগুলি সেট। গণনাযোগ্য বাস্তব সংখ্যা সীমাবদ্ধ করুন একটি বাস্তব সংখ্যা x সীমাতে গণনাযোগ্য হয় যদি মূলদ সংখ্যার (বা, যা সমতুল্য, গণনাযোগ্য বাস্তব সংখ্যা) একটি গণনাযোগ্য ক্রম থাকে যা x-এ একত্রিত হয়। এর বিপরীতে, একটি বাস্তব সংখ্যা গণনাযোগ্য হয় যদি এবং শুধুমাত্র যদি সেখানে মূলদ সংখ্যার একটি ক্রম থাকে যা এটির সাথে একত্রিত হয় এবং যার গণনাযোগ্য মডুলাস থাকে। যখন একটি বাস্তব সংখ্যাকে বিটের ক্রম হিসাবে দেখা হয়, তখন নিম্নলিখিত সমতুল্য সংজ্ঞাটি ধারণ করে। বাইনারি সংখ্যার একটি অসীম ক্রম সীমাতে গণনাযোগ্য হয় যদি এবং শুধুমাত্র যদি সেটটিতে মান গ্রহণকারী মোট গণনাযোগ্য ফাংশন থাকে যাতে প্রতিটি i-এর জন্য সীমা বিদ্যমান এবং সমান হয়। সুতরাং প্রতিটি i-এর জন্য, t বাড়ার সাথে সাথে এর মান অবশেষে ধ্রুবক এবং সমান হয়ে যায়। গণনাযোগ্য বাস্তব সংখ্যার ক্ষেত্রে, সীমাবদ্ধ গণনাযোগ্য বাস্তবতার দুটি উপস্থাপনার মধ্যে কার্যকরভাবে সরানো সম্ভব নয়। উদাহরণ বাস্তব যার বাইনারি সম্প্রসারণ থামার সমস্যাকে এনকোড করে সীমাতে গণনাযোগ্য তবে গণনাযোগ্য নয়। বাস্তব যার বাইনারি সম্প্রসারণ প্রথম-ক্রম গাণিতিকের সত্য সেটকে এনকোড করে সীমাতে গণনাযোগ্য নয়। চৈতিনের ধ্রুবক। সেট-থিওরেটিক এক্সটেনশন-গাণিতিক শ্রেণিবিন্যাসে ফাংশনের মাধ্যমে α-পুনরাবৃত্তি তত্ত্বের জন্য সীমা লেমার একটি পরিবর্তিত সংস্করণ রয়েছে, যা কিছু গ্রহণযোগ্য অর্ডিনালের সাপেক্ষে সংজ্ঞায়িত একটি শ্রেণিবিন্যাস। একটি প্রদত্ত গ্রহণযোগ্য অর্ডিনালের জন্য,-গাণিতিক শ্রেণিবিন্যাসকে সংজ্ঞায়িত করুনঃ একটি সম্পর্ক যদি-পুনরাবৃত্তিমূলক হয়। যদি এটি একটি সম্পর্কের অভিক্ষেপ হয়। যদি এর পরিপূরক হয়। থেকে থেকে একটি আংশিক ফাংশন হতে দিন। নিম্নলিখিতগুলি সমতুল্যঃ (এর গ্রাফ) হল। দুর্বলভাবে-পুনরাবৃত্তিমূলক,-গণনাযোগ্য ফাংশনের সূচকগুলি ব্যবহার করার-লাফ। এমন একটি-পুনরাবৃত্তিমূলক ফাংশন রয়েছে যা আনুমানিক। বোঝায় যে হয় এবং উভয়ই অনির্ধারিত, অথবা তারা উভয়ই সংজ্ঞায়িত এবং সমান। আরও দেখুন স্পিকার সিকোয়েন্স রেফারেন্স জে শ্মিডহুবার, "সাধারণীকৃত কোলমোগোরভ জটিলতা এবং সীমাতে গণনাযোগ্য অগণিত সার্বজনীন পরিমাপের শ্রেণিবিন্যাস", ইন্টারন্যাশনাল জার্নাল অফ ফাউন্ডেশনস অফ কম্পিউটার সায়েন্স, 2002,। আর. সোয়ার। পুনরাবৃত্তিমূলকভাবে গণনাযোগ্য সেট এবং ডিগ্রি। স্প্রিংগার-ভার্লাগ 1987। ভি. ব্রাটকা। টুরিং লাফ এবং সীমার মধ্যে একটি গ্যালোইস সংযোগ। লগইন করুন। পদ্ধতি গণনা। বিজ্ঞান, 2018,। গণনাযোগ্যতা তত্ত্ব গণনার তত্ত্ব