Low (computability)
গণনাযোগ্যতা তত্ত্বে, একটি টুরিং ডিগ্রি [X] কম হয় যদি টুরিং লাফ [X′] 0′ হয়। একটি সেট কম হয় যদি এটির ডিগ্রি কম থাকে। যেহেতু প্রতিটি সেট তার লাফ থেকে গণনাযোগ্য, তাই যে কোনও নিম্ন সেট 0′-এ গণনাযোগ্য, তবে 0′-এ গণনাযোগ্য সেটগুলির লাফ 0′ (স্কোনফিল্ড জাম্প ইনভার্সন)-এ পুনরাবৃত্তিমূলকভাবে গণনাযোগ্য যে কোনও ডিগ্রি আবদ্ধ করতে পারে। এক্স কম হওয়ায় বলা হয় যে কোনও সেটের লাফ দেওয়ার জন্য টুরিং হ্রাসযোগ্যতার দিক থেকে এর লাফ এক্স '-এর সর্বনিম্ন সম্ভাব্য ডিগ্রি রয়েছে। নিম্ন মাত্রার সাথে সম্পর্কিত বিভিন্ন বৈশিষ্ট্য রয়েছেঃ একটি ডিগ্রি হ্রাস করা হয় যদি এর n 'তম লাফ 0 এর n' তম লাফ হয়। একটি সেট X-কে সাধারণীকরণ করা হয় নিম্ন যদি এটি X′ ষ্ণ TX + 0′-কে সন্তুষ্ট করে, অর্থাৎঃ যদি এর লাফ সম্ভব সর্বনিম্ন ডিগ্রি থাকে। একটি ডিগ্রি d কে সাধারণীকরণ করা হয় নিম্ন n যদি এর n 'তম লাফ হয় (n-1)' 0 'সহ d এর সংযোগের প্রথম লাফ। আরও সাধারণভাবে, সেটগুলির বৈশিষ্ট্যগুলি যা তাদের গণনামূলকভাবে দুর্বল বলে বর্ণনা করে (যখন টুরিং ওরাকল হিসাবে ব্যবহৃত হয়) ছত্রছায়াযুক্ত শব্দ লোনেস বৈশিষ্ট্যের অধীনে উল্লেখ করা হয়। জোকাসচ এবং সোয়ারের নিম্ন ভিত্তি উপপাদ্য অনুসারে, যে কোনও অ-খালি শ্রেণীতে নিম্ন মাত্রার একটি সেট থাকে। এর থেকে বোঝা যায় যে, যদিও নিম্ন সেটগুলি গণনার দিক থেকে দুর্বল, তবুও তারা পিয়ানো গাণিতিকের সমাপ্তি গণনা করার মতো কৃতিত্ব অর্জন করতে পারে। বাস্তবে, এটি পুনরাবৃত্তি তাত্ত্বিক নির্মাণের জন্য প্রয়োজনীয় বস্তুর গণনামূলক শক্তির উপর একটি সীমাবদ্ধতার অনুমতি দেয়ঃ উদাহরণস্বরূপ, রামসের উপপাদ্যের প্রমাণ-তাত্ত্বিক শক্তি বিশ্লেষণে ব্যবহৃত। আরও দেখুন উচ্চ (গণনাযোগ্যতা) নিম্ন ভিত্তি উপপাদ্য তথ্যসূত্র গণনাযোগ্যতা তত্ত্ব