Výpočet v limitu - Computation in the limit - Wikipedia

v teorie vypočítatelnosti, je volána funkce limit vypočítatelný pokud je to limit rovnoměrně vypočítatelné posloupnosti funkcí. Podmínky vypočítatelné v limitu, rekurzivní limit a rekurzivně přibližné jsou také používány. Lze si představit omezitelné vypočítatelné funkce jako ty, které připouštějí nakonec správný vypočítatelný postup hádání na jejich skutečné hodnotě. Sada je vypočítatelný limit, když je charakteristická funkce je limit vypočítatelný.

Pokud je posloupnost relativně vypočítatelná vzhledem k D, pak je funkce limit vypočítatelný v D.

Formální definice

A celková funkce ${ displaystyle r (x)}$ je limit vypočítatelný, pokud existuje celková vypočítatelná funkce ${ displaystyle { hat {r}} (x, s)}$ takhle

${ displaystyle displaystyle r (x) = lim _ {s až infty} { hat {r}} (x, s)}$

Celková funkce ${ displaystyle r (x)}$ je limit vypočítatelný v D pokud existuje celková funkce ${ displaystyle { hat {r}} (x, s)}$ vypočítatelný v D také uspokojující

${ displaystyle displaystyle r (x) = lim _ {s až infty} { hat {r}} (x, s)}$

Sada přirozená čísla je definován jako vypočítatelný v limitu právě tehdy, když je jeho charakteristická funkce je vypočítatelný v limitu. Naproti tomu sada je vypočitatelný právě když je vypočítatelný v limitu funkcí ${ displaystyle phi (t, i)}$ a existuje druhá vypočítatelná funkce, která přijímá vstup i a vrátí hodnotu t dostatečně velký na to ${ displaystyle phi (t, i)}$ se stabilizoval.

Omezit lemma

The omezit lemma uvádí, že množinu přirozených čísel lze vypočítat pomocí limitu právě tehdy, je-li množina vypočítatelná z ${ displaystyle 0 '}$ (dále jen Turingův skok prázdné sady). Relativizované limitní lemma uvádí, že množina je limit, který lze vypočítat ${ displaystyle D}$ právě když je vypočítatelný z ${ displaystyle D '}$Limitní lemma (a jeho relativizace) navíc platí jednotně. Lze tedy přejít z indexu funkce ${ displaystyle { hat {r}} (x, s)}$ do indexu pro ${ displaystyle { hat {r}} (x)}$ ve vztahu k ${ displaystyle 0 '}$. Lze také přejít z indexu pro ${ displaystyle { hat {r}} (x)}$ ve vztahu k ${ displaystyle 0 '}$ pro některé index ${ displaystyle { hat {r}} (x, s)}$ to má limit ${ displaystyle { hat {r}} (x)}$.

Důkaz

Tak jako ${ displaystyle 0 '}$ je [vypočítatelně vyčíslitelná] množina, musí být vypočítatelná v samotném limitu, protože lze definovat vypočítatelnou funkci

${ displaystyle displaystyle { hat {r}} (x, s) = { begin {cases} 1 & { text {if by stage}} s, x { text {has been enumerated into}} 0 ' 0 & { text {pokud ne}} end {cases}}}$

jehož limit ${ displaystyle r (x)}$ tak jako ${ displaystyle s}$ jde do nekonečna je charakteristická funkce ${ displaystyle 0 '}$.

Proto stačí ukázat, že pokud je mezní vypočítatelnost zachována Turingova redukce, protože to ukáže, že všechny sady lze vypočítat z ${ displaystyle 0 '}$ jsou vypočítatelné. Opravné sady ${ displaystyle X, Y}$ které jsou identifikovány s jejich charakteristickými funkcemi a vypočítatelnou funkcí ${ displaystyle X_ {s}}$ s limitem ${ displaystyle X}$. Předpokládejme to ${ displaystyle Y (z) = phi ^ {X} (z)}$ pro nějakou Turingovu redukci ${ displaystyle phi}$ a definovat vypočítatelnou funkci ${ displaystyle Y_ {s}}$ jak následuje

${ displaystyle displaystyle Y_ {s} (z) = { begin {cases} phi ^ {X_ {s}} (z) & { text {if}} phi ^ {X_ {s}} { text {konverguje maximálně}} s { text {kroky.}} 0 & { text {jinak}} end {případy}}}$

Nyní předpokládejme, že výpočet ${ displaystyle phi ^ {X} (z)}$ sblíží se ${ displaystyle s}$ kroky a dívá se pouze na první ${ displaystyle s}$ kousky ${ displaystyle X}$. Nyní vyberte ${ displaystyle s '> s}$ takové, že pro všechny ${ displaystyle z$ ${ displaystyle X_ {s '} (z) = X (z)}$. Li ${ displaystyle t> s '}$ pak výpočet ${ displaystyle phi ^ {X_ {t}} (z)}$ konverguje maximálně ${ displaystyle s '$ kroky k ${ displaystyle phi ^ {X} (z)}$. Proto ${ displaystyle Y_ {s} (z)}$ má limit ${ displaystyle phi ^ {X} (z) = Y (z)}$, tak ${ displaystyle Y}$ je limit vypočítatelný.

Jako ${ displaystyle Delta _ {2} ^ {0}}$ množiny jsou jen množiny, z nichž lze vypočítat ${ displaystyle 0 '}$ podle Postova věta, limitní lemma také znamená, že limitní vypočítatelné množiny jsou ${ displaystyle Delta _ {2} ^ {0}}$ sady.

Omezte vypočítatelná reálná čísla

A reálné číslo X je vypočítatelné v limitu pokud existuje vypočítatelná sekvence ${ displaystyle r_ {i}}$ z racionální čísla (nebo, což je ekvivalentní, vypočítatelná reálná čísla ) který konverguje k X. Skutečné číslo je naopak vypočitatelný právě když existuje řada racionálních čísel, která k ní konverguje a která má vypočítatelný modul konvergence.

Když je reálné číslo zobrazeno jako posloupnost bitů, platí následující ekvivalentní definice. Nekonečná sekvence ${ displaystyle omega}$ binárních číslic je vypočítatelný v limitu právě tehdy, když existuje celková vypočítatelná funkce ${ displaystyle phi (t, i)}$ odebírání hodnot v sadě ${ displaystyle {0,1 }}$ takové, že pro každého i omezení ${ displaystyle lim _ {t rightarrow infty} phi (t, i)}$ existuje a rovná se ${ displaystyle omega (i)}$. Tak pro každého i, tak jako t zvyšuje hodnotu ${ displaystyle phi (t, i)}$ nakonec se stane konstantní a rovná se ${ displaystyle omega (i)}$. Stejně jako v případě vypočítatelných reálných čísel není možné efektivně se pohybovat mezi dvěma reprezentacemi limitních vypočítatelných reálných čísel.

Příklady

• Skutečný, jehož binární expanze kóduje zastavení problému je vypočítatelný v limitu, ale není vypočítatelný.
• Skutečný, jehož binární expanze kóduje sadu pravd aritmetika prvního řádu není v limitu vypočítatelný.

Viz také

• Speckerova sekvence

Reference

1. J. Schmidhuber, „Hierarchie zobecněných Kolmogorovových složitostí a nepočítatelné univerzální míry vypočítatelné v mezích“, International Journal of Foundations of Computer Science, 2002.
2. R. Soare. Rekurzivně vyčíslitelné sady a stupně. Springer-Verlag 1987.