Przedmiotem problemu jest pytanie, czy dla każdej dodatniej liczby naturalnej istnieje takie wielokrotne złożenie funkcji że jego wartość dla tej liczby to 1. Można pokazać, że problem ten jest nierozstrzygalny, to znaczy, nie istnieje ogólny algorytm, który działając na dowolny ciąg par określających funkcje odpowiada na tak postawione pytanie poprawnie. Można zauważyć, że problem Collatza to przypadek, gdy ciąg par to {},
Zobacz też obliczalność zbioru twierdzeń ogólna rekurencyjność twierdzenie Gödla
Przypisy
Bibliografia
Kategoria:Teoria obliczeń Kategoria:Logika matematyczna
ca:Indecidibilitat