Теория автоматов. Лупал А.М. - 27 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

27
3.6. Òåçèñ Òüþðèíãà
Ïðè ðåàëèçàöèè àëãîðèòìîâ íà ìàøèíå Òüþðèíãà ìîæåò âîçíèêíóòü
âîïðîñ äëÿ âñåõ ëè êîíñòðóêòèâíûõ ïðîöåäóð, ò. å. äëÿ òåõ ïðîöåäóð,
äëÿ êîòîðûõ ìîæíî ïîñòðîèòü àëãîðèòì, ìîæíî ðàçðàáîòàòü ðåàëèçóþ-
ùèå èõ ìàøèíû Òüþðèíãà. Â òåçèñå Òüþðèíãà, êîòîðûé ÿâëÿåòñÿ îñíîâ-
íîé ãèïîòåçîé òåîðèè àëãîðèòìîâ, ñîäåðæèòñÿ óòâåðäèòåëüíûé îòâåò
íà ýòîò âîïðîñ.
Òåçèñ ôîðìóëèðóåòñÿ ñëåäóþùèì îáðàçîì: âñÿêèé àëãîðèòì ìîæåò
áûòü çàäàí ïîñðåäñòâîì Òüþðèíãîâîé ôóíêöèîíàëüíîé ñõåìû è ðåàëè-
çîâàí â ñîîòâåòñòâóþùåé ìàøèíå Òüþðèíãà. Äîêàçàòü òåçèñ Òüþðèíãà
íåëüçÿ, òàê êàê ñàìî ïîíÿòèå àëãîðèòìà ÿâëÿåòñÿ íåòî÷íûì.  ôîðìó-
ëèðîâêå òåçèñà Òüþðèíãà èäåò ðå÷ü, ñ îäíîé ñòîðîíû, î âñÿêîì àëãîðèò-
ìå, ò. å. îá îáùåì ïîíÿòèè àëãîðèòìà, êîòîðîå íå ÿâëÿåòñÿ òî÷íûì ìà-
òåìàòè÷åñêèì ïîíÿòèåì; à ñ äðóãîé ñòîðîíû, â ýòîé æå ôîðìóëèðîâêå
ðå÷ü èäåò î òî÷íîì ìàòåìàòè÷åñêîì ïîíÿòèè î Òüþðèíãîâîé ôóíêöè-
îíàëüíîé ñõåìå.
Çíà÷åíèå ãèïîòåçû êàê ðàç è çàêëþ÷àåòñÿ â òîì, ÷òî îíà óòî÷íÿåò
îáùåå, íî ðàñïëûâ÷àòîå ïîíÿòèå âñÿêîãî àëãîðèòìà  ÷åðåç áîëåå ñïå-
öèàëüíîå, íî óæå ñîâåðøåííî òî÷íîå ìàòåìàòè÷åñêîå ïîíÿòèå Òüþ-
ðèíãîâîé ôóíêöèîíàëüíîé ñõåìû (è åå ðåàëèçàöèè â ìàøèíå Òüþðèí-
ãà), ò. å. îáùåå ðàñïëûâ÷àòîå ïîíÿòèå àëãîðèòìà îòîæäåñòâëÿåòñÿ ñ
òî÷íûì ïîíÿòèåì ôóíêöèîíàëüíîé ñõåìû ìàøèíû Òüþðèíãà.
Óâåðåííîñòü â ñïðàâåäëèâîñòè òåçèñà Òüþðèíãà îñíîâàíà ãëàâíûì
îáðàçîì íà îïûòå. Âñå èçâåñòíûå àëãîðèòìû, êîòîðûå áûëè ïðèäóìà-
íû â òå÷åíèå ìíîãèõ âåêîâ èñòîðèè ìàòåìàòèêè, ìîãóò áûòü çàäàíû
ïîñðåäñòâîì Òüþðèíãîâûõ ôóíêöèîíàëüíûõ ñõåì. Ïî ñâîåìó õàðàêòå-
ðó òåçèñ Òüþðèíãà íàïîìèíàåò îá àäåêâàòíîñòè ìàòåìàòè÷åñêèõ ìî-
äåëåé ôèçè÷åñêèì ÿâëåíèÿì è ïðîöåññàì.
Èñõîäÿ èç òåçèñà Òüþðèíãà, íåâîçìîæíîñòü ïîñòðîåíèÿ ìàøèíû Òüþ-
ðèíãà îçíà÷àåò îòñóòñòâèå àëãîðèòìà ðåøåíèÿ äàííîé ïðîáëåìû. Ðàñ-
øèôðóåì ýòî ïîëîæåíèå.  ÷èñëå îáùèõ òðåáîâàíèé, ïðåäúÿâëÿåìûõ ê
àëãîðèòìàì, óïîìèíàåòñÿ òðåáîâàíèå ðåçóëüòàòèâíîñòè. Íàèáîëåå ðà-
äèêàëüíîé ôîðìóëèðîâêîé çäåñü áûëî áû òðåáîâàíèå, ÷òîáû ïî ëþáî-
ìó àëãîðèòìó À è äàííûì α ìîæíî áûëî áû îïðåäåëèòü, ïðèâåäåò ëè
ðàáîòà À ïðè èñõîäíûõ äàííûõ α ê ðåçóëüòàòó èëè íåò. Èíà÷å ãîâîðÿ
íóæíî ïîñòðîèòü àëãîðèòì Â, òàêîé ÷òî Â(À,α) = èñòèíà, åñëè À(α)
äàåò ðåçóëüòàò, è Â(À,α) = ëîæü, åñëè À(α) íå äàåò ðåçóëüòàòà.

Страницы