Jak dobry może być detektor zatrzymania?

Czy istnieje Maszyna Turinga, która może zadecydować, czy prawie wszystkie inne Maszyny Turinga zatrzymają się?

Załóżmy, że mamy jakieś wyliczenie maszyn Turinga i pewne pojęcie o „rozmiarze” zbioru liczb naturalnych, a my definiujemy:$\mathbb{N} \rightarrow \{M_i\}$$\| \cdot \|$

Jakie cechy minimalnej wartości $f$ istnieją dla różnych $\| \cdot \|$? Załóżmy na przykład $\| S \|$jest limsup proporcji liczb do $k$ , które są w $S$ . Czy istnieje $i$ dla którego $f(i) = 0$ ?

To nie jest „ładna” właściwość, ponieważ to, czy jest to prawda, czy fałsz, zależy od kodowania.

Zobacz Asymptotycznie prawie wszystkie terminy są silnie normalizowane$\lambda$ , co potwierdza to, co napisano w tytule. Jednak ten dokument pokazuje również, że odwrotna sytuacja dotyczy kombinatorów SKI (w których składowe mogą być składane warunki lambda).

W rachunku lambda redukcja jest ekwiwalentem kroku maszyny Turinga, a silna normalizacja jest właściwością, że każda sekwencja redukcji ostatecznie osiąga normalną formę - tzn. Dalsze redukcje nie są możliwe. (Ponieważ dany termin lambda może mieć wiele ważnych redukcji, silna normalizacja przypomina trochę powiedzenie, że dana niedeterministyczna maszyna Turinga zawsze przestaje.) A zatem fakt, że asymptotycznie prawie wszystkie terminy są silnie normalizowane, oznacza, że ​​z prawdopodobieństwem zbliżającym się do 1, zmniejszenie dużych wyrażeń lambda zawsze osiągnie normalną formę.$\lambda$

Terminy lambda można jednak przetłumaczyć w sposób zachowujący znaczenie na rachunek kombinacyjny, taki jak kombinatory SKI (i odwrotnie), a w rachunku kombinatorycznym asymptotycznie pętla wszystkich terminów.