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

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 . $^{\dagger}$

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.

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

computability undecidability

— 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

$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

$\Sigma^0_1$ $m$ $\Sigma^0_1$

$\Sigma^0_1$

— Carl Mummert
źródło