Zestaw rekurencyjny

W teoria obliczalności , wykorzystując zbiór rekurencyjny lub rozstrzygalne zestaw to zestaw z liczb całkowitych (lub elementy łatwe do kodowania w całkowitych), którego funkcja charakterystyczna jest rekurencyjna funkcja w sensie logiki matematycznej .

Innymi słowy, zbiór jest rekurencyjny wtedy i tylko wtedy, gdy istnieje maszyna Turinga ( program komputerowy ) pozwalająca określić w skończonym czasie, czy jakakolwiek liczba całkowita jest obecna czy nie. mi{\ displaystyle E} T{\ displaystyle T}mi{\ displaystyle E}

∀nie∈NIE{\ displaystyle \ forall n \ in \ mathbb {N}}
T(nie)=OUja gdyby nie∈mi{\ Displaystyle T (n) = TAK \ {\ mbox {si}} \ n \ in E}
T(nie)=NIEONIE gdyby nie∉mi{\ Displaystyle T (n) = NIE \ {\ mbox {si}} \ n \ notin E}

Ten typ zestawu odpowiada rzeczywistej koncepcji z John R. Myhill , które są koncepcje, które mogą być zdefiniowane szeroko i jednoznaczny. Pojęcie zbioru rekurencyjnie wyliczalnego (nierekurencyjnego) jest raczej koncepcją konstruktywną , której treść staje się jaśniejsza, lepsza i lepiej rozumiana w czasie, bez możliwości jej całkowitego zdefiniowania.

Definicja pod względem systemu formalnego

W terminologii systemów formalnych równoważna jest następująca definicja:

mi{\ displaystyle E}jest rekurencyjny wtedy i tylko wtedy, gdy istnieje poprawny i kompletny system formalny dla stwierdzeń formy „  jest w  ” i formy „  nie jest w  ”.nie{\ displaystyle n}mi{\ displaystyle E}nie{\ displaystyle n}mi{\ displaystyle E}

Nieruchomości

• Zbiór A jest rekurencyjny wtedy i tylko wtedy, gdy A i jego uzupełnienie są rekurencyjnie wyliczalne .
• Jeśli A i B są rekurencyjne, to A ∩ B i A ∪ B są rekurencyjne.

Przykłady

Następujące zestawy są rekurencyjne:

• dowolny skończony zbiór (pusty zbiór ∅ jest trywialnym przykładem);
• zbiór wielokrotności liczby całkowitej (liczby całkowite, liczby parzyste itp.);k{\ displaystyle k}
• zbiór liczb pierwszych;
• zbiór rozwiązań danego równania diofantycznego .

Następujące zestawy są wyliczalne rekurencyjnie, ale nie są rekurencyjne:

• zbiór równań diofantyny, które mają rozwiązanie całkowite;
• wszystkie programy, które się zatrzymują (programy, które nie działają w nieskończoność): zobacz „  Zatrzymywanie problemu  ”.

Obecnie nie wiadomo, czy wielozbiór terminów sekwencji Syracuse terminu początkowego jest rekurencyjny dla dowolnego (domniemana: liczba całkowita). Syracuse przypuszczenie twierdzi coś przeciwnego, ale pozostaje do dziś undemonstrated. Z drugiej strony jest rekurencyjnie wyliczalny z definicji. u0=k{\ displaystyle u_ {0} = k}k>0{\ displaystyle k> 0}k{\ displaystyle k}

Uwagi i odniesienia

1. Jean-Paul Delahaye , Information, Complexity and Chance , Hermes Science Publishing,1999( ISBN  2-7462-0026-0 )p. 74.

Zobacz też

Powiązane artykuły

• Rozstrzygalny problem
• Dziesiąty problem Hilberta

Link zewnętrzny

Kurs rekurencyjny