Составители:
28
 ñèëó òåçèñà Òüþðèíãà çàäà÷ó î òîì, ïðèâåäåò ëè ðåàëèçàöèÿ àëãî-
ðèòìà À ïðè èñõîäíûõ äàííûõ α ê ðåçóëüòàòó èëè íåò, ìîæíî ñôîðìóëè-
ðîâàòü êàê çàäà÷ó ïîñòðîåíèÿ ìàøèíû Òüþðèíãà ñëåäóþùèì îáðàçîì
[1].
Ïîñòðîèòü ìàøèíó Òüþðèíãà Ò
0
òàêóþ (ñ òàêîé ñèñòåìîé êîìàíä),
÷òî äëÿ ëþáîé ìàøèíû Òüþðèíãà Ò ñ ñèñòåìîé êîìàíä ∑
ò
è ëþáûõ
èñõîäíûõ äàííûõ a äëÿ ìàøèíû Ò Ò
0
(∑
ò
, α) = èñòèíà, åñëè Ò(α) îñòà-
íàâëèâàåòñÿ è Ò
0
(∑
ò
, α) = ëîæü, åñëè Ò(α) íå îñòàíàâëèâàåòñÿ (ïðîèñõî-
äèò çàöèêëèâàíèå).
Ýòà çàäà÷à íàçûâàåòñÿ ïðîáëåìîé îñòàíîâêè, è åñëè îñòàíîâêà íå-
âîçìîæíà, ò. å. ðåøàåìàÿ ïðîáëåìà ÿâëÿåòñÿ àëãîðèòìè÷åñêè íåðàçðå-
øèìîé, íèêàêîå êîäèðîâàíèå ñèñòåìû êîìàíä ∑
ò
è a â àëôàâèòå ìàøè-
íû Ò
0
íå ïðèâîäèò ê óñïåõó.
Íî, òåì íå ìåíåå, åñëè óäàñòñÿ ðàçáèòü ïðîáëåìó íà îòäåëüíûå ÷à-
ñòíûå ñëó÷àè, åå îêàçûâàåòñÿ âîçìîæíûì ðåøèòü, ïîëüçóÿñü ðàçíûìè
ñðåäñòâàìè. Ïîýòîìó íåðàçðåøèìîñòü îáùåé ïðîáëåìû îñòàíîâêè âîâñå
íå ñíèìàåò íåîáõîäèìîñòü äîêàçûâàòü ñõîäèìîñòü ïðåäëàãàåìûõ àë-
ãîðèòìîâ, à ëèøü äîêàçûâàåò, ÷òî ïîòîê òàêèõ äîêàçàòåëüñòâ íåëüçÿ
ïîëíîñòüþ àâòîìàòèçèðîâàòü.
Ìàøèíà Òüþðèíãà ÿâëÿåòñÿ ïðîîáðàçîì ëþáîé âû÷èñëèòåëüíîé ìà-
øèíû, òàê êàê êàæäàÿ ôèçè÷åñêè îñóùåñòâèìàÿ âû÷èñëèòåëüíàÿ ìà-
øèíà ìîæåò áûòü ðàññìîòðåíà ëèøü êàê íåêîòîðàÿ ïðèáëèæåííàÿ ìî-
äåëü ìàøèíû Òüþðèíãà. Èìåííî â ðåàëüíûõ ìàøèíàõ îáúåì âíåøíåé
ïàìÿòè îãðàíè÷åí, â òî âðåìÿ êàê â ìàøèíå Òüþðèíãà ôèãóðèðóåò áåñ-
êîíå÷íàÿ ëåíòà. Ðàçóìååòñÿ, òåõíè÷åñêîå îñóùåñòâëåíèå íåîãðàíè÷åí-
íîé ïàìÿòè íåâîçìîæíî, íî î÷åâèäíà è ñîâðåìåííàÿ, è ïðîøëàÿ òåíäåí-
öèè ê ïîñòîÿííîìó óâåëè÷åíèþ îáúåìà ïàìÿòè è ñêîðîñòè âû÷èñëåíèé
ïî ñðàâíåíèþ ñ óæå äîñòèãíóòûì óðîâíåì.
Страницы
- « первая
- ‹ предыдущая
- …
- 26
- 27
- 28
- 29
- 30
- …
- следующая ›
- последняя »
