Pytania otagowane jako semi-decidability

2
Dlaczego sumy funkcji nie są policzalne?
Dowiedzieliśmy się o koncepcji wyliczenia funkcji. W praktyce odpowiadają one językom programowania. W pewnej uwadze profesor wspomniał, że klasa wszystkich całkowitych funkcji (tj. Funkcji, które zawsze kończą się dla każdego wejścia) nie jest wyliczalna. Oznaczałoby to, że nie możemy opracować języka programowania, który pozwala nam pisać wszystkie funkcje całkowite, ale …
3
Czy są jakieś zbiory policzalne, których nie można wyliczyć?
Zbiór jest policzalny, jeśli ma bijectję z liczbami naturalnymi, i jest obliczalny (ce), jeśli istnieje algorytm, który wylicza jego elementy. Każdy nieskończony obliczalny zestaw wyliczalny musi być policzalny, ponieważ możemy zbudować bijection z wyliczenia. Czy są jakieś przykłady zbiorów policzalnych, których nie da się wyliczyć? Oznacza to, że istnieje bijection …
3
nierozstrzygalny problem i jego negacja jest nierozstrzygalna
Wiele „znanych” nierozstrzygalnych problemów jest jednak co najmniej w połowie nierozstrzygalnych, a ich dopełnienie jest nierozstrzygalne. Jednym z przykładów może być przede wszystkim problem zatrzymania i jego uzupełnienie. Czy ktoś może jednak podać przykład, w którym zarówno problem, jak i jego uzupełnienie są nierozstrzygalne i nierozstrzygalne? Myślałem o języku diagonalizacji …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.