Funkcja obliczalna: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m Zmiana z "w ziemii" na bardziej ogólne pojęcie "we wszechświecie" Znaczniki: VisualEditor Z urządzenia mobilnego Z wersji mobilnej (przeglądarkowej) Zadanie nowicjusza Zasugerowano edycję: poprawa stylu |
m Pogrubienie "nie" dla zwiększonej czytelności. Znaczniki: Wycofane VisualEditor Z urządzenia mobilnego Z wersji mobilnej (przeglądarkowej) Zadanie nowicjusza Zasugerowano edycję: poprawa stylu |
||
Linia 74:
* Funkcja <math>f,</math> taka, że <math>f(n) = 1,</math> gdy istnieje ciąg <math>n</math> następujących piątek w rozwinięciu dziesiętnym <math>\pi</math> i <math>f(n) = 0,</math> w przeciwnym przypadku jest obliczalna. (Dana funkcja <math>f</math> jest albo stałą funkcją 1, która jest obliczalna, albo istnieje takie <math>k</math> że <math>f(n) = 1</math> dla <math>n < k</math> i <math>f(n) = 0</math> dla <math>n \geqslant k.</math> Wiemy, że każda taka funkcja <math>f</math> musi być obliczalna – nie wiadomo jednak czy istnieją dowolnie długie ciągi następujących po sobie piątek w rozwinięciu dziesiętnym π, tak więc nie wiemy, które z tych dwóch przekształceń definicji funkcji <math>f</math> jest poprawne, a jeżeli drugie byłoby poprawne, to ile wynosiłoby <math>k.</math>)
* Każdy skończony ciąg '''''nie'''''obliczalnych liczb naturalnych (takich, że [[Pracowity bóbr|Funkcja pracowitego bobra]] <math>\Sigma</math>) jest obliczalny. W szczególności dla każdej liczby naturalnej <math>n</math> istnieje algorytm obliczający skończony ciąg <math>\Sigma(0), \Sigma(1), \Sigma(2), \dots, \Sigma(n)</math> – w przeciwieństwie do tego, że nie ma algorytmu obliczającego pełny ciąg <math>\Sigma,</math> tzn. <math>\Sigma(n)</math> dla każdego <math>n.</math> Tak więc „Drukuj 0, 1, 4, 6, 13” jest trywialnym algorytmem obliczającym <math>\Sigma(0), \Sigma(1), \Sigma(2), \Sigma(3), \Sigma(4).</math> Podobnie istnieje taki trywialny algorytm dla każdego danego <math>n,</math> obliczający (nawet jeśli nigdy nie będzie on nikomu znany lub przez kogokolwiek odkryty) <math>\Sigma(0), \Sigma(1), \Sigma(2), \dots, \Sigma(n).</math>
== Hipoteza Churcha-Turinga ==
| |||