| dbpprop:abstract
|
- La teoria della computabilità effettiva si occupa della esistenza o meno di algoritmi risolutivi di problemi. Fra i suoi fondatori vi è Alan Turing.
- 再帰理論（さいきりろん、英: Recursion theory）は、数理論理学の一分野で、1930年代の計算可能関数とチューリング次数の研究が源となっている。発展の過程で、この分野は計算可能性や定義可能性全般を対象に含むようになった。これらの領域においては、再帰理論は証明論や effective 記述集合論とも密接に関係する。 再帰理論の根本的疑問は「自然数から自然数への関数が計算可能であるとはどういう意味か?」と、「計算不能関数は、その計算不能性のレベルに基づいて階層分けできるか?」である。これらの疑問への答えを探す過程で豊かな理論が生まれ、現在でも活発な研究が行われている。 数理論理学における再帰理論の研究者がよく扱うのは、この記事で触れる相対的な計算可能性、還元性の概念、次数構造などである。これらは、計算機科学における計算可能性理論が、計算複雑性理論、形式手法、形式言語などを主な研究対象とすることと対照を成す。これら二つの研究コミュニティには知識と手法の面で重なる部分が多々あり、はっきりした境界を引くことは出来ない。
- Teoria rekursji to dział logiki matematycznej, którego początki sięgają lat trzydziestych XX wieku. Do jego powstania i rozwoju w znacznym stopniu przyczynili się między innymi Alan Turing i Stephen Cole Kleene. Teoria rekursji zaczyna od badania obiektów, które nazywa się rekurencyjnymi. Funkcje rekurencyjne to takie funkcje o argumentach i wartościach należących do zbioru liczb naturalnych, które albo są szczególnie prostej postaci (jak funkcja stała czy funkcja identycznościowa), albo powstają z tych pierwszych w wyniku zastosowania skończonej liczby "porządnych" operacji (takich jak składanie funkcji czy definiowanie rekurencyjne). Natomiast zbiór jest rekurencyjny, gdy jego funkcja charakterystyczna jest rekurencyjna. Funkcje rekurencyjne są modelem (w sensie nieformalnym) funkcji czy relacji "obliczalnych", to znaczy takich których wartość dla dowolnych argumentów można podać w skończonej liczbie kroków w sposób mechaniczny. Jak widać pojęcie obliczalności jest nieścisłe i jako takie może być rozumiane wyłącznie w sposób intuicyjny, nieformalny. W przeciwieństwie do "obliczalności", rekurencyjność jest ścisłym pojęciem matematycznym. Obiekty rekurencyjne można też zdefiniować w pozornie inny (lecz tak naprawdę równoważny) sposób. Mianowicie podzbiór A zbioru liczb naturalnych nazywamy rekurencyjnym, jeśli istnieje algorytm rozstrzygający dla każdej liczby naturalnej czy należy ona do zbioru A czy nie. Określone w ten sposób pojęcie zbioru rekurencyjnego nie tylko jest identyczne z podanym powyżej, lecz nawet nie zależy od tego, jaki model obliczeń wybierzemy do wykonywania algorytmów. Równoważność wszystkich "sensownych" modeli obliczeń jest postulowana w tezie Churcha, według której to czy zbiór (funkcja, relacja) jest obliczalny czy też nie, nie zależy od wyboru modelu obliczeń. Po obiektach rekurencyjnych następny stopień złożoności prezentują obiekty rekurencyjnie przeliczalne. Jeśli relacja R(m,... ,m,n,... ,n) jest rekurencyjna, to relacja "istnieją takie m(1),... ,m(k), że R(m,... ,m,n,... ,n)" jest rekurencyjnie przeliczalna. Dodając w definicji relacji kolejne kwantyfikatory ogólne i egzystencjalne w sposób naprzemienny, uzyskujemy nowe relacje, które mają (a w każdym razie mogą mieć) coraz większy stopień złożoności. W ten sposób powstaje cała hierarchia obiektów, nazywana hierarchią arytmetyczną, której "piętra" można ponumerować liczbami naturalnymi. Następnym krokiem jest dalsze komplikowanie rozważanych obiektów, które skutkuje przedłużeniem hierarchii arytmetycznej do jeszcze ogólniejszej hierarchii analitycznej. Teoria rekursji zajmuje się konstrukcją i szczegółowym badaniem tego typu hierarchii oraz szukaniem odpowiedzi na pytania w rodzaju: "jak skomplikowany jest dany zbiór (relacja, funkcja)?", "na którym piętrze w badanej hierarchii można go umieścić?", "na jakim poziomie stabilizuje się dana hierarchia?". Pytania te, jakkolwiek łatwe do formułowania, okazują się często bardzo trudne. Teoria rekursji we współczesnym stanie jest wysoce abstrakcyjną dziedziną, którą zajmuje się stosunkowo niewielka liczba badaczy. Na gruncie teorii rekursji powstała w drugiej połowie XX wieku teoria złożoności obliczeniowej, która stanowi obecnie ważny dział informatyki teoretycznej. Na pewnych wynikach tej teorii oparte zostały zabezpieczenia sieci komputerowych przed włamaniami (chodzi o to, żeby złamanie tych zabezpieczeń musiało trwać dostatecznie długo – czyli aby zabierało "niewielomianowo" wiele czasu). Ma to związek z bardzo ważną i dotychczas nierozstrzygniętą hipotezą P=NP, która dotyczy istnienia szybkich (czyli działających w czasie wielomianowym) algorytmów dla pewnej klasy problemów.
- 递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论(effective descriptive set theory)有所重叠。 数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。相对于计算机科学家，他们研究次递归层次，可行的计算和公用于可计算性理论研究的形式语言。在这两个社区之间有着相当大的知识和方法上的重叠，而没有明显的界限。
- La teoria della computabilità effettiva si occupa della esistenza o meno di algoritmi risolutivi di problemi. Fra i suoi fondatori vi è Alan Turing.
- 再帰理論（さいきりろん、英: Recursion theory）は、数理論理学の一分野で、1930年代の計算可能関数とチューリング次数の研究が源となっている。発展の過程で、この分野は計算可能性や定義可能性全般を対象に含むようになった。これらの領域においては、再帰理論は証明論や effective 記述集合論とも密接に関係する。 再帰理論の根本的疑問は「自然数から自然数への関数が計算可能であるとはどういう意味か?」と、「計算不能関数は、その計算不能性のレベルに基づいて階層分けできるか?」である。これらの疑問への答えを探す過程で豊かな理論が生まれ、現在でも活発な研究が行われている。 数理論理学における再帰理論の研究者がよく扱うのは、この記事で触れる相対的な計算可能性、還元性の概念、次数構造などである。これらは、計算機科学における計算可能性理論が、計算複雑性理論、形式手法、形式言語などを主な研究対象とすることと対照を成す。これら二つの研究コミュニティには知識と手法の面で重なる部分が多々あり、はっきりした境界を引くことは出来ない。
- Teoria rekursji to dział logiki matematycznej, którego początki sięgają lat trzydziestych XX wieku. Do jego powstania i rozwoju w znacznym stopniu przyczynili się między innymi Alan Turing i Stephen Cole Kleene. Teoria rekursji zaczyna od badania obiektów, które nazywa się rekurencyjnymi. Funkcje rekurencyjne to takie funkcje o argumentach i wartościach należących do zbioru liczb naturalnych, które albo są szczególnie prostej postaci (jak funkcja stała czy funkcja identycznościowa), albo powstają z tych pierwszych w wyniku zastosowania skończonej liczby "porządnych" operacji (takich jak składanie funkcji czy definiowanie rekurencyjne). Natomiast zbiór jest rekurencyjny, gdy jego funkcja charakterystyczna jest rekurencyjna. Funkcje rekurencyjne są modelem (w sensie nieformalnym) funkcji czy relacji "obliczalnych", to znaczy takich których wartość dla dowolnych argumentów można podać w skończonej liczbie kroków w sposób mechaniczny. Jak widać pojęcie obliczalności jest nieścisłe i jako takie może być rozumiane wyłącznie w sposób intuicyjny, nieformalny. W przeciwieństwie do "obliczalności", rekurencyjność jest ścisłym pojęciem matematycznym. Obiekty rekurencyjne można też zdefiniować w pozornie inny (lecz tak naprawdę równoważny) sposób. Mianowicie podzbiór A zbioru liczb naturalnych nazywamy rekurencyjnym, jeśli istnieje algorytm rozstrzygający dla każdej liczby naturalnej czy należy ona do zbioru A czy nie. Określone w ten sposób pojęcie zbioru rekurencyjnego nie tylko jest identyczne z podanym powyżej, lecz nawet nie zależy od tego, jaki model obliczeń wybierzemy do wykonywania algorytmów. Równoważność wszystkich "sensownych" modeli obliczeń jest postulowana w tezie Churcha, według której to czy zbiór (funkcja, relacja) jest obliczalny czy też nie, nie zależy od wyboru modelu obliczeń. Po obiektach rekurencyjnych następny stopień złożoności prezentują obiekty rekurencyjnie przeliczalne. Jeśli relacja R(m,... ,m,n,... ,n) jest rekurencyjna, to relacja "istnieją takie m(1),... ,m(k), że R(m,... ,m,n,... ,n)" jest rekurencyjnie przeliczalna. Dodając w definicji relacji kolejne kwantyfikatory ogólne i egzystencjalne w sposób naprzemienny, uzyskujemy nowe relacje, które mają (a w każdym razie mogą mieć) coraz większy stopień złożoności. W ten sposób powstaje cała hierarchia obiektów, nazywana hierarchią arytmetyczną, której "piętra" można ponumerować liczbami naturalnymi. Następnym krokiem jest dalsze komplikowanie rozważanych obiektów, które skutkuje przedłużeniem hierarchii arytmetycznej do jeszcze ogólniejszej hierarchii analitycznej. Teoria rekursji zajmuje się konstrukcją i szczegółowym badaniem tego typu hierarchii oraz szukaniem odpowiedzi na pytania w rodzaju: "jak skomplikowany jest dany zbiór (relacja, funkcja)?", "na którym piętrze w badanej hierarchii można go umieścić?", "na jakim poziomie stabilizuje się dana hierarchia?". Pytania te, jakkolwiek łatwe do formułowania, okazują się często bardzo trudne. Teoria rekursji we współczesnym stanie jest wysoce abstrakcyjną dziedziną, którą zajmuje się stosunkowo niewielka liczba badaczy. Na gruncie teorii rekursji powstała w drugiej połowie XX wieku teoria złożoności obliczeniowej, która stanowi obecnie ważny dział informatyki teoretycznej. Na pewnych wynikach tej teorii oparte zostały zabezpieczenia sieci komputerowych przed włamaniami (chodzi o to, żeby złamanie tych zabezpieczeń musiało trwać dostatecznie długo – czyli aby zabierało "niewielomianowo" wiele czasu). Ma to związek z bardzo ważną i dotychczas nierozstrzygniętą hipotezą P=NP, która dotyczy istnienia szybkich (czyli działających w czasie wielomianowym) algorytmów dla pewnej klasy problemów.
- 递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论(effective descriptive set theory)有所重叠。 数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。相对于计算机科学家，他们研究次递归层次，可行的计算和公用于可计算性理论研究的形式语言。在这两个社区之间有着相当大的知识和方法上的重叠，而没有明显的界限。
|
![[RDF Data]](/statics/sw-cube.png)
