Low basis theorem
নিম্ন ভিত্তি উপপাদ্যটি গণনাযোগ্যতা তত্ত্বের বেশ কয়েকটি ভিত্তি উপপাদ্যের মধ্যে একটি, যার প্রত্যেকটি দেখায় যে, বাইনারি ট্রি-র একটি অসীম উপ-ট্রি দেওয়া হলে, নির্দিষ্ট গণনাযোগ্যতার বৈশিষ্ট্য সহ গাছের মধ্য দিয়ে একটি অসীম পথ খুঁজে পাওয়া সম্ভব। লো বেসিস থিওরেম, বিশেষত, দেখায় যে অবশ্যই একটি পথ থাকতে হবে যা কম; অর্থাৎ, পথের টুরিং লাফটি টুরিং-এর থামার সমস্যার সমতুল্য। বিবৃতি এবং প্রমাণ নিম্ন ভিত্তি উপপাদ্য বলে যে প্রতিটি অ-খালি শ্রেণীতে (গাণিতিক শ্রেণিবিন্যাস দেখুন) নিম্ন মাত্রার একটি সেট থাকে (সোয়ার 1987:109)। সংজ্ঞা অনুসারে, এটি এই বিবৃতির সমতুল্য যে বাইনারি গাছের প্রতিটি অসীম গণনাযোগ্য সাবট্রির একটি নিম্ন মাত্রার অসীম পথ রয়েছে। প্রমাণটি ক্লাসের সাথে জোর করার পদ্ধতি ব্যবহার করে (কুপার 2004:330)। হাজেক এবং কুসেরা (1989) দেখিয়েছেন যে নিম্ন ভিত্তি হিসাবে পরিচিত গাণিতিক আনুষ্ঠানিক পদ্ধতিতে প্রমাণযোগ্য। জোরপূর্বক যুক্তিটিও নিম্নরূপ স্পষ্টভাবে প্রণয়ন করা যেতে পারে। একটি সেট X-ω-এর জন্য, ধরা যাক f (X) = σ {i} (X) ′2 − i, যেখানে {i} (X) ′ মানে হল যে টুরিং মেশিন i, X-এর উপর থেমে যায় (এই সমস্ত i-এর যোগফল সহ)। তারপর, প্রতিটি নন-এম্প্টি (লাইটফেস) এস 2 ω-এর জন্য, (অনন্য) এক্স ω এস মিনিমাইজিং এফ (এক্স)-এর একটি নিম্ন টুরিং ডিগ্রি থাকে। এটি দেখার জন্য, {i} (X) ω ω ω Y ω ω S ({i} (Y) ω ω J <i ({j} (Y) ω ω (X) ω)), যা i-এর উপর আনয়ন দ্বারা 0′ থেকে গণনা করা যেতে পারে; লক্ষ্য করুন যে β Y ω Sφ (Y) হল φ-এর জন্য। অন্য কথায়, একটি যন্ত্র X-এ থামে কিনা তা একটি সীমাবদ্ধ শর্ত দ্বারা বাধ্য করা হয়, যার জন্য X′ = 0′ অনুমতি দেয়। প্রয়োগ নিম্ন ভিত্তি উপপাদ্যের একটি প্রয়োগ হল কার্যকর তত্ত্বগুলির সম্পূর্ণতা তৈরি করা যাতে সম্পূর্ণতাগুলির টুরিং ডিগ্রি কম থাকে। উদাহরণস্বরূপ, নিম্ন ভিত্তি উপপাদ্যটি পিএ ডিগ্রির অস্তিত্বকে নির্দেশ করে যা কঠোরভাবে নীচে রয়েছে। রেফারেন্স। মূল প্রকাশনা, অতিরিক্ত স্পষ্ট গদ্য সহ। উপপাদ্য 1.8.37। গণনাযোগ্যতা তত্ত্ব