"Jesteśmy skazani na śmierć"

Automat skończony ma funkcję przejść. W komputerze, w którym modyfikowany jest kod wykonywalny niestety ta funkcja się modyfikuje:( Na tym zresztą opiera się dowód o nierozstrzygalności. Modyfikacja kodu wykonywalnego to jedne z najwredniejszych błędów przy wykonywaniu programów. Innymi są rozsypanie sterty, modyfikacja tablicy metod wirtualnych i jeszcze dużo dużo dużo tego;( Problem staje się bardziej skomplikowany gdy mamy do czynienia z wieloma procesorami /komputerami.

Powszechnie się wierzy (i tylko wierzy), że teza Churcha-Turinga jest prawdziwa. Podobnie powszechnie wierzy się, że twierdzenie o czterech barwach też jest prawdziwe (dowód uzyskany za pomocą komputera). Szereg innych tez matematycznych zaakceptowano jako twierdzenia mimo, że używano komputera do uzyskania dowodu.

Nieskończona tasiemka w maszynie Turinga jest potrzebna na zapewnienie poprawności dla każdej implementacji algorytmu. Chcemy żeby algorytm się nie zapętlił na każdej implementacji, która zapewni odpowiedni rozmiar zasobów.

Jeśli chodzi o ostatnie to tym samym potwierdzasz, że nawet dla niewinnie wyglądającego algorytmu problem stopu jest bardzo trudny nawet dla ludzi. Dowodu nie podałeś bo go na razie nie ma. Wykonywanie algorytmu dla kolejnych liczb nie jest dowodem bo jest ich nieskończenie wiele. Jeśli jest poprawny dla zbioru 1..2^58 to czy będzie poprawny dla 1..2^64 potem 1..2^128 i tak dalej. Musimy mieć pewność, że dowolna implementacja algorytmu nie wyłoży nam się po drodze.

P.S. Miało być o śmierci a wyszło o informatyce;)