Stroj koji uvijek staje: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
m Bot: brisanje 5 međuwiki poveznica premještenih u stranicu d:q2518389 na Wikidati |
m →Odnosi sa parcijalnim Turingovim strojevima: pravopis |
||
Redak 18:
Odgovor na oba pitanja je negativan.
Sljedeći teorem pokazuje da funkcije izračunljive strojem koji uvijek staje ne uključuju proširenja svih parcijalno izračunljivih funkcija, što u konačnici implicira negativan odgovor na prvo pitanje. Ova činjenica je usko povezana
:'''Teorem.''' Postoje parcijalne Turing-izračunljive funkcije koje nemaju proširenje na totalne Turing-izračunljive funkcije. Posebice, parcijalna funkcija ''f'' definirana tako da ''f''(''n'') = ''m'' ako i samo ako Turingov stroj sa indeksom ''n'' koji staje na ulazu ''0'' sa izlazom ''m'' nema proširenja na totalno izračunljivu funkciju.
| |||