Twierdzenie Rice'a o właściwościach nie semantycznych

30

Twierdzenie Rice'a mówi nam, że jedynymi właściwościami semantycznymi Maszyn Turinga (tj. Właściwościami obliczonymi przez maszynę), o których możemy decydować, są dwie trywialne właściwości (tj. Zawsze prawdziwe i zawsze fałszywe).

Ale istnieją inne właściwości Maszyn Turinga, których nie można rozstrzygać. Na przykład właściwość, że istnieje stan nieosiągalny w danej maszynie Turinga, jest nierozstrzygalna .

Czy istnieje podobne twierdzenie do twierdzenia Rice'a, które kategoryzuje rozstrzygalność podobnych właściwości? Nie mam dokładnej definicji. Każde znane twierdzenie, które obejmuje podany przeze mnie przykład, byłoby dla mnie interesujące.

łatwo jest udowodnić, że ten zestaw jest nierozstrzygalny za pomocą twierdzeń Kleene'a o rekurencji / stałym punkcie .

Kaveh
źródło
Problem zatrzymania polega zasadniczo na tym, czy stan zatrzymania jest osiągalny, więc ogólne pytanie, które stany są osiągalne, z pewnością będzie nierozwiązywalne.
Carl Mummert,
@Carl, tak, wiem o tym, ale różni się to od mojego przykładu. Mój przykład to: biorąc pod uwagę <M>, czy jest stan, który jest nieosiągalny (usunięcie go nie wpłynie na maszynę na żadne dane wejściowe). Jest podobny do pytań w metodach formalnych: czy istnieje linia kodu, która nie jest potrzebna? (co zwykle oznacza, że ​​program tak naprawdę nie działa zgodnie z oczekiwaniami).
Kaveh
@Kaveh: Zasadniczo problem zatrzymania jest równy - problemowi zatrzymania dla maszyn, które całkowicie ignorują swój wkład, a dla tej specjalnej klasy maszyn problemem zatrzymania jest problem, czy stan zatrzymania jest osiągalny w twoim sens. 1
Carl Mummert
@Carl, tak, znam bezpośrednią redukcję (musimy upewnić się, że wszystkie inne stany są osiągalne). Ale moje pytanie nie dotyczy samego problemu, był to prosty przykład niezdecydowanego nie-semantycznego języka. Czy wiesz, czy istnieje coś podobnego do twierdzenia Rice'a, które obejmuje właściwości nie-semantyczne? A może uważasz, że takie twierdzenie jest mało prawdopodobne?
Kaveh

Odpowiedzi:

14

Σ10mΣ10

Σ10

Carl Mummert
źródło