Черк-Тюрингдин диссертациясы логика, математика жана информатикадагы эффективдүү, системалуу же механикалык ыкма түшүнүгүн билдирет. Ал эсептөө жөндөмдүүлүгүнүн интуитивдик концепциясынын сүрөттөлүшү катары формулировкаланган жана жалпы рекурсивдүү функцияларга карата көбүнчө Черчтин тезиси деп аталат. Ал ошондой эле компьютердик-эсептөө функцияларынын теориясын билдирет. Диссертация 1930-жылдары, компьютерлердин өзү али жок болгон кезде пайда болгон. Кийинчерээк ал америкалык математик Алонсо Черчтин жана анын британдык кесиптеши Алан Тюрингдин урматына аталган.
Натыйжага жетүү үчүн ыкманын эффективдүүлүгү
Заманбап компьютерге окшош биринчи түзүлүш англиялык математик Алан Тюринг тарабынан түзүлгөн Bombie машинасы болгон. Ал Экинчи дүйнөлүк согуш учурунда немис билдирүүлөрүн чечмелөө үчүн колдонулган. Бирок диссертациясы жана алгоритм түшүнүгүн формалдаштыруу үчүн ал кийинчерээк Тьюринг машиналары деп аталган абстракттуу машиналарды колдонгон. Диссертацияларматематиктерди да, программисттерди да кызыктырды, анткени бул идея биринчи компьютерлерди жаратуучуларды шыктандырган.
Эсептөө теориясында Черч-Тюринг тезиси эсептелүүчү функциялардын табияты жөнүндөгү божомол катары да белгилүү. Анда натурал сандардагы ар кандай алгоритмдик эсептелүүчү функциялар үчүн аны эсептөөгө жөндөмдүү Тьюринг машинасы бар экени айтылат. Же, башкача айтканда, ага ылайыктуу алгоритм бар. Бул ыкманын натыйжалуулугунун белгилүү мисалы - таутологияны текшерүү үчүн чындык таблицасы тести.
Каалаган каалаган натыйжага жетүү жолу "эффективдүү", "системалык" же "механикалык" деп аталат, эгерде:
- Метод так нускамалардын чектүү саны менен көрсөтүлөт, ар бир нускама чектүү сандагы символдордун жардамы менен туюнтулган.
- Ал катасыз иштейт, белгилүү бир катар кадамдар менен каалаган натыйжаны берет.
- Усулду кагаз жана карандаштан башка эч кандай жабдыктын жардамысыз адам аткарса болот
- Бул аракетти аткарып жаткан адамдан түшүнүктү, интуицияны же тапкычтыкты талап кылбайт
Мурда математикада "эффективдүү эсептелүүчү" формалдуу эмес термин карандаш жана кагаз менен эсептелүүчү функцияларга карата колдонулган. Бирок алгоритмдик эсептешүү түшүнүгү конкреттүү бардык нерсеге караганда интуитивдик болгон. Эми ал табигый аргументи бар функция менен мүнөздөлдү, ал үчүн эсептөө алгоритми бар. Алан Тюрингдин жетишкендиктеринин бири болгонформалдуу так предикатты чагылдыруу, анын жардамы менен методдун эффективдүү шарты колдонулса, формалдуу эмес предикатты алмаштырууга мүмкүн болмок. Чиркөө да ушундай эле ачылыш жасады.
Рекурсивдүү функциялардын негизги түшүнүктөрү
Тюрингдин предикаттарды өзгөртүүсү, бир караганда, кесиптеши сунуштагандан башкача көрүндү. Бирок натыйжада, алардын ар бири бирдей математикалык функциялардын жыйындысын тандайт деген мааниде эквиваленттүү болуп чыкты. Черч-Тюринг тезиси бул топтомдо эффективдүү шарттарды канааттандырган ыкма менен баалуулуктары алынышы мүмкүн болгон ар бир функция бар деген ырастоо саналат. Эки ачылыштын ортосунда дагы бир айырма бар эле. Тьюринг өз ишин интегралдык же реалдуу өзгөрмөлөр менен эсептелүүчү функцияларды камтыган деп сүрөттөгөн.
Жалпы рекурсивдүү функциялар
Чирконун баштапкы формуласында эсептөө λ-эсептөө аркылуу жүргүзүлүшү мүмкүн деп айтылат. Бул жалпы рекурсивдүү функцияларды колдонууга барабар. Черч-Тюринг диссертациясында болжолдонгондон да көп эсептөөлөр камтылган. Мисалы, уюлдук автоматтарга, комбайндарга, каттоо машиналарына жана алмаштыруу системаларына тиешелүү. 1933-жылы математиктер Курт Годель жана Жак Хербранд жалпы рекурсивдүү функциялар деп аталган класстын формалдуу аныктамасын түзүшкөн. Ал бирден ашык аргумент мүмкүн болгон функцияларды колдонот.
Метод түзүүλ-эсептөө
1936-жылы Алонсо Черч λ-эсептөө деп аталган аныктоо ыкмасын жараткан. Ал натурал сандар менен байланышкан. λ-эсептөөнүн ичинде окумуштуу алардын коддолушун аныктаган. Натыйжада, алар Чиркөө номерлери деп аталат. Натурал сандарга негизделген функция λ-эсептелүүчү деп аталды. Башка аныктама бар болчу. Черчтин тезисиндеги функция эки шартта λ-эсептелүүчү деп аталат. Биринчиси мындай угулду: эгерде ал чиркөөнүн элементтери боюнча эсептелсе, ал эми экинчи шарт λ-эсептөөнүн мүчөсү менен көрсөтүлүү мүмкүнчүлүгү болгон.
Ошондой эле 1936-жылы кесиптешинин ишин изилдегенге чейин Тьюринг азыр анын аты менен аталган абстракттуу машиналар үчүн теориялык моделди түзгөн. Алар лентадагы каармандарды манипуляциялоо менен эсептөөлөрдү жүргүзө алышкан. Бул теориялык информатикада табылган башка математикалык иш-аракеттерге да тиешелүү, мисалы, кванттык ыктымалдык эсептөө. Черчтин тезисиндеги функция кийинчерээк Тьюринг машинасынын жардамы менен далилденген. Башында алар λ-эсепке таянышкан.
Функциянын эсептелиши
Натурал сандар символдук ырааттуулук катары тийиштүү түрдө коддолгондо, эгерде абстракттуу машина керектүү алгоритмди таап, бул функцияны лентага басып чыгарса, натурал сандардагы функция Тьюринг-эсептөөчү функция деп айтылат. 1930-жылдары болбогон мындай түзүлүш келечекте компьютер деп эсептелмек. Абстракттуу Тьюринг машинасы жана Черчтин тезиси өнүгүү доорун жар салганэсептөө приборлору. Эки илимпоз формалдуу түрдө аныктаган функциялардын класстары дал келери далилденген. Ошондуктан, натыйжада эки билдирүү тең бириккен. Эсептөө функциялары жана Черчтин тезиси да эсептөө жөндөмдүүлүгү түшүнүгүнө күчтүү таасир эткен. Алар ошондой эле математикалык логика жана далилдөө теориясы үчүн маанилүү курал болуп калды.
Методдун негиздемеси жана көйгөйлөрү
Диссертация боюнча карама-каршы пикирлер бар. 1936-жылы Черч жана Тьюринг тарабынан сунушталган "жумушчу гипотеза" үчүн көптөгөн далилдер чогултулган. Бирок берилгендерден жаңы эффективдүү эсептелүүчү функцияларды ачуунун бардык белгилүү ыкмалары же операциялары ал кезде жок болгон машиналарды куруу ыкмалары менен байланышкан. Черч-Тюрингдин тезисти далилдөө үчүн, эсептөөнүн ар бир реалдуу модели эквиваленттүү экенинен башталат.
Ар түрдүү анализдердин ар түрдүүлүгүнөн улам, бул көбүнчө өзгөчө күчтүү далил катары каралат. Эффективдүү эсептелүүчү функциянын интуитивдик түшүнүгүн так аныктоого болгон бардык аракеттер эквиваленттүү болуп чыкты. Сунушталган ар бир талдоо бир эле функциялар классын, тактап айтканда Тьюринг машиналары тарабынан эсептелүүчү функцияларды бөлүп көрсөтүүнү далилдеди. Бирок кээ бир эсептөө моделдери ар кандай тапшырмалар үчүн убакыт жана эстутум пайдалануу жагынан натыйжалуураак болуп чыкты. Кийинчерээк рекурсивдүү функциялардын негизги түшүнүктөрү жана Черчтин тезисинин гипотетикалык экени белгиленген.
Дисертация М
Тьюрингдин тезисти менен эсептөөчү түзүлүш менен эсептеле турган нерселердин бардыгын анын машинасы менен эсептесе болот деген ырастоону айырмалоо маанилүү. Экинчи варианттын өзүнүн аныктамасы бар. Ганди экинчи сүйлөмдү "Тезис М" деп атайт. Бул мындай болот: "Аппарат менен эсептелген нерсени Тьюринг машинасы менен эсептесе болот." Диссертациянын тар маанисинде бул чындыктын баасы белгисиз эмпирикалык сунуш. Тьюрингдин тезиси менен «М тезиси» кээде чаташып кетет. Экинчи версия толугу менен туура эмес. Турингге эсептелбеген функцияларды эсептей турган ар кандай шарттуу машиналар сүрөттөлгөн. Белгилей кетчү нерсе, биринчи тезис экинчисин талап кылбайт, бирок анын жалгандыгына шайкеш келет.
Дисертациянын тескери мааниси
Эсептөө теориясында Черчтин тезиси жалпы рекурсивдүү функциялардын классы тарабынан эсептелүүчүлүк түшүнүгүнүн сүрөттөлүшү катары колдонулат. Америкалык Стивен Клин бир кыйла жалпы формуланы берди. Ал жарым-жартылай рекурсивдүү бардык жарым-жартылай функцияларды алгоритмдер менен эсептелген деп атады.
Тескери импликация адатта Чиркөөнүн тескери тезиси деп аталат. Бул оң бүтүн сандардын ар бир рекурсивдүү функциясы эффективдүү бааланганында. Тар мааниде, тезис мындай мүмкүнчүлүктү билдирет. Ал эми кененирээк мааниде бул шарттуу машина анда болушу мүмкүнбү деген суроодон абстракцияланат.
Кванттык компьютерлер
Эсептелуучу функциялар жана Черчтин тезисинин түшүнүктөрү математика, машина теориясы жана башка көптөгөн илимдер үчүн маанилүү ачылыш болуп калды. Бирок технология бир топ өзгөрдү жана жакшыртууну улантууда. Кванттык компьютерлер заманбап компьютерлерге караганда аз убакыт менен көптөгөн жалпы тапшырмаларды аткара алат деп болжолдонууда. Бирок токтоо маселеси өңдүү суроолор кала берүүдө. Кванттык компьютер ага жооп бере албайт. Жана, Черч-Тюринг тезисине ылайык, башка эсептөөчү аппарат да жок.
