[Slup]

Nie mam czasu, więc odpowiem tylko na jeden poruszany wątek. Przepraszam.

Nie. Krytykujesz formę mych słów, ale treść jest jasna.
"Doom" w ramach p(doom) to nietrywialna własność semantyczna programu w efektywnym modelu świata. Z twierdzenia Rice’a i redukcji ze stopu wynika nierozstrzygalność w pełnej ogólności. To zabija wizję „uniwersalnego testera alignmentu”. Magicznej czarnej skrzynki nie będzie.

To jest typowe dla laików nadużycie twierdzenia Rice'a (podobnie zresztą nadużywane są inne twierdzenia limitacyjne).

Warto zacząć od tego, że każde twierdzenie matematyczne jest sformułowane na gruncie pewnego systemu aksjomatyczno-dedukcyjnego (zazwyczaj jest to ZFC, chociaż w przypadku teorii obliczalności można wziąć znacznie słabszy system). W szczególności ten ustalony system składa się z języka, który ma ograniczoną ekspresywność. Oznacza to, że w tym języku da się wyrazić pewien ściśle ograniczony (nie mylić ze skończonym) zestaw potencjalnych faktów (o charakterze matematycznym i tylko takim). Ta uwaga stanie się jasna za chwilę.

Przejdźmy teraz do teorii obliczalności i twr. Rice'a. Zamiast maszyn Turinga wolę mówić o funkcjach (częściowo) rekurencyjnych. To równoważny model i jednocześnie trochę wcześniejszy niż ten Turinga. Zacznę od tego, że wezmę funkcję 
[latex]\Phi: \mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N}[/latex]
częściowo rekurencyjną, która jest uniwersalna dla jednoargumentowych funkcji częściowo rekurencyjnych. Taka funkcja istnieje (jest odpowiednikiem uniwersalnej maszyny Turinga). Teraz zdefiniuję [latex]\Phi_n: \mathbb{N} \rightarrow \mathbb{N}[/latex] dla [latex]n \in \mathbb{N}[/latex] następująco
[latex]\Phi_n(m) = \Phi(n,m)[/latex]
Oczywiście [latex]\Phi_n[/latex] jest jednoargumentową funkcją częściowo rekurencyjną i ciąg [latex]\{\Phi_n\}_{n \in \mathbb{N}}[/latex] przebiega wszystkie takie funkcje (numeracja Gödela). Teraz można sformułować twierdzenie Rice'a:

Niech [latex]A \subseteq \mathbb{N}[/latex] będzie zbiorem. Załóżmy, że dla każdej pary [latex]n,m\in \mathbb{N}[/latex] takiej, że [latex]\Phi_n = \Phi_m[/latex] z faktu [latex]\Phi_n \in A[/latex] wynika, że [latex]\Phi_m \in A[/latex]. Wówczas [latex]A[/latex] jest nierozstrzygalny za wyjątkiem sytuacji, gdy [latex]A = \emptyset,\mathbb{N}[/latex].

Kilka przykładów poprawnego zastosowania twr. Rice'a. Zbiory:

1. [latex]A_1 = \big\{n\in \mathbb{N}\,\big|\,\Phi_n\mbox{ jest określona dla wszystkich }m\in \mathbb{N}\big\}[/latex]
   
2. [latex]A_2 = \big\{n\in \mathbb{N}\,\big|\,\Phi_n\mbox{ przyjmuje wartość }2\mbox{ dla pewnego }m\in \mathbb{N}\big\}[/latex]
   
3. [latex]A_3 = \big\{n\in \mathbb{N}\,\big|\,\Phi_n\mbox{ jest totalna i rośnie szybciej niż funkcja Ackermanna }\big\}[/latex]
   

są nierozstrzygalne. 

Teraz kilka przykładów nadużycia twr. Rice'a. "Zbiory":

1. [latex]A_4 = \big\{n\in \mathbb{N}\,\big|\,\Phi_n\mbox{ opisuje program, który przyrządza kopytka z ustalonego worka ziemniaków}\big\}[/latex]
   
2. [latex]A_5 = \big\{n\in \mathbb{N}\,\big|\,\Phi_n\mbox{ opisuje program, który niszczy procesor}\big\}[/latex]
   
3. [latex]A_6 = \big\{n\in \mathbb{N}\,\big|\,\Phi_n\mbox{ opisuje program, który doprowadza ludzkość do zagłady}\big\}[/latex]
   

Łatwo widać, że w [latex]A_1,A_2,A_3[/latex] twierdzenie Rice'a zastosowane jest do sytuacji, które mogą być zdefiniowane na gruncie pewnego systemu aksjomatyczno-dedukcyjnego (np. ZFC) tzn. są to dobrze zdefiniowane obiekty matematyczne. Mówiąc językiem technicznym, [latex]A_1,A_2,A_3[/latex] odpowiadają poprawnie zbudowane termy języka teorii zbiorów (lub innego nadającego się do tych celów języka).

Tymczasem w drugim przypadku "zbiory" [latex]A_4,A_5,A_6[/latex] nie są dobrze zdefiniowane. Bo co to miałoby znaczyć, że funkcja częściowo rekurencyjna przyrządza danie z ustalonego worka ziemniaków lub niszczy procesor lub doprowadza ludzkość do zagłady? Funkcje (w tym też te rekurencyjne) nie mają takich zdolności. 

Zresztą ze względu na równoważność między funkcjami częściowo rekurencyjnymi i maszynami Turinga można to samo wyrazić w języku tych maszyn. Maszyny Turinga, jak wiadomo, są abstrakcyjnymi maszynami matematycznymi wyposażonymi w alfabet symboli, skończony zestaw stanów (w tym stany początkowe i końcowe, w których maszyna się zatrzymuje), funkcję przejścia i nieskończoną taśmę podzieloną na komórki. Stąd już widać, że następujące pytania na temat tych maszyn są sensowne:

1. Czy dana maszyna Turinga zatrzymuje się dla każdego wejściowego układu symboli na taśmie?
   
2. Czy dla danej maszyny Turinga istnieje stan początkowy taśmy, że ta maszyna się zatrzymuje i w tym momencie jej taśma zawiera dwa symbole [latex]\textbf{1}[/latex] i pozostałe symbole są puste?
   
3. Czy dana maszyna Turinga zatrzymuje się dla każdego stanu początkowego  i w tym momencie wypisuje więcej symboli na taśmie niż wynosi wartość funkcji Ackermanna od liczby niepustych symboli w stanie początkowym?
   

Natomiast następujące pytania są bezsensowne:

1. Czy dana maszyna Turinga dla pewnego układu wejściowego symboli przyrządza danie z ustalonej porcji ziemniaków (np. tej, którą mam teraz w kuchni)?
   
2. Czy dana maszyny Turinga niszczy procesor?
   
3. Czy dana maszyna Turinga doprowadza do zagłady ludzkości?
   

Łatwo widać, że nie wiadomo w ogóle, co te pytania mają znaczyć. Maszyna Turinga przesuwa swoją głowicę, przechodzi do następnego stanu, zapisuje coś na taśmie. Jak taka maszyna może ugotować ziemniaki lub spalić procesor lub zgładzić ludzkość? 

Tutaj jest jeszcze inny problem. Ta sama maszyna Turinga (funkcja częściowo rekurencyjna) może mieć dwie realizacje fizyczne. Załóżmy, że mamy już tę maszynę Turinga w dwóch realizacjach.

• Pierwsza (Skynet) podłączona jest do internetu i kontroluje amerykański arsenał nuklearny (jak w filmie). 
  
• Druga znajduje się w bunkrze, drukuje na swojej taśmie te same symbole, co pierwsza, ale nie jest do niczego podłączona. Bunkier jest zapomniany i niebawem elektrownia wyłączy jej prąd, bo nikt nie płacił rachunków. Potem przyjdą ludzie i rozłożą maszynę na części, którą sprzedadzą na złom. 
  

W pierwszym przypadku Skynet niszczy ludzkość (a przynajmniej próbuje). W drugim nic się nie dzieje. Twr. Rice'a i w ogóle matematyka nie ma tutaj nic do rzeczy. Istotny jest rzeczywisty kontekst.      

Jest też jedna rzecz, o której ludzie zapominają. Żaden rzeczywisty komputer nie jest maszyną Turinga (funkcją częściowo rekurencyjną). Jest tylko jej przybliżoną realizacją fizyczną. 

Ostatnia uwaga dotyczy tego, że twierdzenie Rice'a wcale nic nie mówi o nieistnieniu czarnych skrzynek tzn. fizycznych procesów, które byłyby istotnie nieobliczalne. Gdyby tak było wystarczyłoby zapoznać Penrose'a z twr. Rice'a i cała ta jego gadanina na temat tych mikrotubuli i kolapsu funkcji falowej byłaby zakończona. W matematyce natomiast rozważa się takie czarne skrzynki w postaci tzw. wyroczni. Bada się ich właśności (twr. Posta). Nie ma z tym najmniejszego kłopotu.