Кіріспе

Есептеуге қабілеттілік теориясында, табиғи сандардың қосалқы жиынтығы, егер ол есептеу арқылы саналатын болса (яғни) және шексіз болса (яғни оның толықтығы шексіз), бірақ оның толықтығының әр шексіз қосалқы жиынтығы емес.

Посттың проблемасына қатысты

Қарапайым жиынтықтарды Эмил Леон Пост Тьюрингтік емес толық c. e. жиынтығын іздеу кезінде ойлап тапты. Мұндай жиынтықтардың бар-жоғы Пост проблемасы деп аталады. Пост өзінің нәтижесін алу үшін екі нәрсені дәлелдеу керек болды: қарапайым жиынтық A есептеуге жарамсыз және K, тоқтату мәселесі, Тьюрингті A-ға азайта алмайды. Ол бірінші бөлігінде (бұл анықтамасы бойынша айқын) сәтті болды, бірақ екінші бөлігінде ол тек бір редукцияны дәлелдеуге қол жеткізді. Посттың идеясын Фридберг пен Мучник 1950 жылдары басымдық әдісі деп аталатын жаңа техниканы қолдана отырып растады. Олар жинақтың қарапайым (осылайша есептелмейтін) құрылымын береді, бірақ тоқтату проблемасын есептей алмайды.

Ресми анықтамалар және кейбір қасиеттер

Келесі мақалада барлық стандартты біркелкі түрде тізімделген электронды пошта жиынтықтары көрсетіледі. Жинақ шексіз болса, иммун деп аталады, бірақ әрбір индекс үшін , бізде бар немесе баламалы түрде: c. e санның шексіз қосалқы жиынтығы жоқ. Жинақ c. e сан болса, және оның комплементі иммун болса, қарапайым деп аталады. Жинақ шексіз болса, тиімді иммун деп аталады, бірақ рекурсивті функция бар, сондықтан әрбір индекс үшін A жиынтығы тиімді қарапайым деп аталады, егер ол c. e. және оның комплементі тиімді иммунды болса. Әрбір тиімді қарапайым жиынтық қарапайым және Тьюрингтік толық. Жинақ шексіз болса, бірақ есептеуге болатын түрде үстем болмаса, онда мүшелерінің тізімі ретпен болса, гипериммун деп аталады. Жинақ гипер қарапайым деп аталады, егер ол қарапайым болса және оның комплементі гипериммунды болса.