| dbo:abstract
|
- نظرية الحاسوبية (بالإنجليزية: computability theory) وتعرف أيضاً بالنظرية العودية وأيضا بنظرية الاستدعاء الذاتي (بالإنجليزية: Recursion theory) وهي أحد فروع المعلوماتية النظرية تم تأسيسه في عام 1930م theoretical computer science والتي تدرس مسائل قابلة للحلحلة حاسوبيا computationally solvable باستخدام نماذج مختلفة للحوسبة. نظرية الحاسوبية تختلف عن التخصصات المشابهة لنظرية التعقيد الحسابي computational complexity theory ، فالأخيرة تتعامل مع سؤال كيفية حل المسألة حاسوبيا بفعالية، بدلا من سؤال إذا كانت المسألة قابلة للحل حاسوبيا أم لا؟ solvable الذي تتناوله نظرية الحاسوبية. (ar)
- La teoria de la computabilitat és la part de la computació que estudia els problemes de decisió que poden ser resolts amb un algorisme o equivalentment amb una màquina de Turing. La teoria de la computabilitat s'interessa per quatre preguntes:
* Quins problemes pot resoldre una màquina de Turing?
* Quins altres formalismes equivalen a les màquines de Turing?
* Quins problemes requereixen màquines més poderoses?
* Quins problemes requereixen màquines menys poderoses? La teoria de la complexitat computacional classifica les funcions computables segons l'ús que fan de diversos recursos en diversos tipus de màquina. (ca)
- Teorie vyčíslitelnosti je vědní obor na pomezí matematiky a informatiky, který zkoumá otázky algoritmické řešitelnosti problémů. Vytváří teoretický základ a zkoumá možnosti a hranice využití algoritmicky pracujících postupů, což se v praxi uplatňuje především na počítačové programy. Pod pojmem algoritmu se běžně rozumí mechanizovaný postup, který lze realizovat třeba na Turingově stroji. Významnou roli ve filozofickém podložení teorie vyčíslitelnosti hraje Churchova–Turingova teze, podle níž jsou všechny „rozumné“ výpočetní modely ekvivalentní Turingově stroji. Pro teoretický popis pojmu algoritmu se využívá množství výpočetních modelů – například Turingův stroj, částečně rekurzivní funkce, RAM stroj a Lambda kalkul (nebo ). (cs)
- Η Θεωρία της Υπολογισιμότητας ή Θεωρία της Αναδρομής, είναι ένας κλάδος της μαθηματικής λογικής, της πληροφορικής και της θεωρίας υπολογισμού που προήλθε από την έρευνα των υπολογίσιμων συναρτήσεων και του βαθμού Turing (=βαθμος μη επιλυσιμότητας) στα μέσα της δεκαετίας του 1930. Τα βασικά ερωτήματα που απευθύνονται από την Θεωρία Αναδρομής είναι «Τι σημαίνει για μια συνάρτηση, ορισμένη στους φυσικούς αριθμούς, ότι είναι υπολογίσιμη;» και «Πώς μπορούν μη-υπολογίσιμες συναρτήσεις να κατηγοριοποιηθούν ιεραρχικά ανάλογα με το βαθμό μη-υπολογισιμότητας τους;». Η απάντηση σε αυτές τις ερωτήσεις οδήγησε σε μία πλούσια θεωρία η οποία ακόμη απασχολεί τους επιστήμονες. Το πεδίο των ερευνών αυτών έχει διευρυνθεί από τότε και πλέον περιέχει την έρευνα της γενικευμένης υπολογισιμότητας και προσδιορισιμότητας. Αξιοσημείωτη είναι η εφεύρεση του κεντρικού συνδυαστικού αντικειμένου της Αναδρομικής Θεωρίας, δηλαδή το Universal Turing Machine,το οποίο προηγείται και προκαθορίζει την εφεύρεση των σύγχρονων υπολογιστών. Ιστορικά, η έρευνα των αλγοριθμικά αναποφαινόμενων (undecidable) συνόλων και συναρτήσεων προέκυψε από διάφορα μαθηματικά προβλήματα που κατέληγαν αναποφασίσιμα (undecidable). Υπάρχουν πολλές εφαρμογές αυτής της θεωρίας σε άλλους κλάδους των μαθηματικών που δεν επικεντρώνονται απαραίτητα στην αναποφασισιμότητα (undecidability). Στις πρώτες εφαρμογές της περιλαμβάνονταν το θεώρημα ενσωμάτωσης του Higman (Higman's embedding theorem), το οποίο συνδέει την Αναδρομική Θεωρία με την Θεωρία των Ομάδων που ήταν αποτέλεσμα των Michael O. Rabin και Anatoly Maltsev στην αλγοριθμική παρουσίαση της άλγεβρας αλλά και την αρνητική λύση του Hilbert's Tenth Problem. Οι πιο νέες εφαρμογές περιλαμβάνουν την αλγοριθμική τυχαιότητα που αποτελεί έρευνα του Theodore Allen Slaman, ο οποίος εφάρμοσε αναδρομικές-θεωρητικές μεθόδους για να επιλύσει προβλήματα Αλγεβρικής Γεωμετρίας και η νεότερη του δουλειά εστιάζεται στους κανονικούς αριθμούς για να λύσει προβλήματα της Αναλυτικής Θεωρίας Αριθμών. Η Θεωρία της Αναδρομής συνδυάζεται με την Θεωρία των Αποδείξεων,με την Αποτελεσματική Περιγραφική Θεωρία Συνόλων, την Θεωρία Μοντέλων και την Αφηρημένη Άλγεβρα. Μάλιστα, Θα μπορούσαμε να χαρακτηρίσουμε ότι η Θεωρία της Πολυπλοκότητας είναι γέννημα της Αναδρομικής Θεωρίας καθώς και οι δύο μοιράζονται ίδιο τεχνικό εργαλείο ,δηλαδή τη μηχανή Turing Οι θεωρητικοί της Αναδρομής στη μαθηματική λογική συχνά μελετούν τη θεωρία της σχετικής υπολογιστικότητας. Αυτό έρχεται σε αντίθεση με τη θεωρία της αναδρομικής ιεραρχίας, επίσημων μεθόδων και επίσημων γλωσσών, το οποίο είναι σύνηθες στην μελέτη της υπολογιστικής θεωρίας και της Πληροφορικής. Υπάρχει ένα αξιοσημείωτο κενό στις γνώσεις και στις μεθόδους μεταξύ των δύο ερευνητικώνκοινοτήτων, ωστόσο δεν μπορούν να διαχωριστούν εντελώς. Για παράδειγμα η παραμετρική πολυπλοκότητα, εφευρέθηκε από τον θεωρητικό της πολυπλοκότητας, Michael Fellows και τον θεωρητικό της αναδρομής Rod Downey. (el)
- Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory. Basic questions addressed by computability theory include:
* What does it mean for a function on the natural numbers to be computable?
* How can noncomputable functions be classified into a hierarchy based on their level of noncomputability? Although there is considerable overlap in terms of knowledge and methods, mathematical computability theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of subrecursive hierarchies, formal methods, and formal languages. (en)
- Die Berechenbarkeitstheorie (auch Rekursionstheorie) ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere damit, welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen Modells einer Maschine) oder eines anderen mathematischen Modells der Berechenbarkeit lösbar sind. Sie ist eng verwandt mit der formalen Semantik, richtet aber die Aufmerksamkeit mehr auf die Terminiertheit von Programmen und Algorithmen. Die zentrale Frage der Rekursionstheorie ist, welche Funktionen (bzw. Mengen) sich mit welchem Berechenbarkeitsmodell berechnen lassen. Es werden dazu Modelle für die Berechenbarkeit und deren Leistungsfähigkeit untersucht. Aus der Art der betrachteten Berechnungsmodelle ergibt sich eine unscharfe Abgrenzung zur Komplexitätstheorie, in der vor allem Berechnungsmodelle mit Ressourcenbeschränkung betrachtet werden. Schwerpunkt vieler Untersuchungen in der Rekursionstheorie ist die relative Berechenbarkeit von Funktionen, d. h., welche Funktionen lassen sich mit einer gegebenen Funktion unter Verwendung eines bestimmten Berechnungsmodells berechnen (siehe zum Beispiel unter Turinggrade). (de)
- Konputagarritasunaren teoria problema erabakigarriak aztertzen dituen konputazioko atala da, 1930ean aztertzen hasi zena. Orokorrean, algoritmo baten bidez edo Turing makina baten bidez (baliokidea dena) ebatzi daitezkeen problemak aztertzen ditu, hain zuzen. (eu)
- La teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que se pueden resolver con un algoritmo o equivalentemente con una máquina de Turing. Las preguntas fundamentales de la teoría de la computabilidad son:
* ¿Qué problemas puede resolver una máquina de Turing?
* ¿Qué otros formalismos equivalen a las máquinas de Turing?
* ¿Qué problemas requieren máquinas más poderosas?
* ¿Qué problemas requieren máquinas menos poderosas? La teoría de la complejidad computacional clasifica las funciones computables según el uso que hacen de diversos recursos en diversos tipos de máquina. (es)
- La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique. La calculabilité (parfois appelée « computationnalité »[réf. nécessaire], de l'anglais computability) cherche d'une part à identifier la classe des fonctions qui peuvent être calculées à l'aide d'un algorithme et d'autre part à appliquer ces concepts à des questions fondamentales des mathématiques. Une bonne appréhension de ce qui est calculable et de ce qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs. Mais la notion de calculabilité ne se limite pas aux fonctions. On peut parler également de nombres calculables (réels ou complexes). (fr)
- 計算可能性理論（けいさんかのうせいりろん、英: computability theory）とは、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。 (ja)
- La teoria della calcolabilità, della computabilità, e della ricorsione cerca di comprendere quali funzioni possono essere calcolate tramite un procedimento automatico. In altre parole, essa cerca di determinare se una data funzione è teoricamente calcolabile a prescindere dal fatto che sia anche trattabile, cioè a prescindere dalla quantità di risorse che la sua esecuzione richiede in termini di tempo o di memoria, che a livello pratico potrebbero essere proibitive. Questa disciplina è comune sia alla matematica sia all'informatica. Di conseguenza l'obiettivo principale è dare una definizione formale e matematicamente rigorosa dell'idea intuitiva di funzione calcolabile. Da una parte l'approccio è quello di approfondire il concetto di calcolabilità, cercando di individuare le categorie di problemi che sono teoricamente risolvibili, e dall'altra mappare questo concetto su ciò che è teoricamente calcolabile sui computer, sempre senza considerare le limitazioni imposte dai costi, dal tempo e dalla quantità di memoria impiegata. Un altro importante aspetto è quello di definire matematicamente il concetto di algoritmo in modo che i programmi possano essere concretamente pensati in termini di oggetti matematici, più precisamente come funzioni che restituiscono un determinato risultato a partire da un certo insieme di dati in ingresso. (it)
- ( 재귀 이론은 여기로 연결됩니다. 다른 뜻에 대해서는 문서를 참고하십시오.) 계산 가능성 이론(計算可能性理論, 영어: computability theory) 또는 재귀 이론(再歸理論, 영어: recursion theory)은 수학기초론의 중요한 분야이자 컴퓨터 과학에서는 계산 이론의 한 갈래이다. 계산 가능성 이론의 기초는 가산 집합 상에서 함수의 해를 찾는 문제와 관련이 있다. 1930년대 불완전성 정리와 함께 람다 대수와 튜링 기계라는 계산 모형이 만들어지면서, 어떤 집합이 효율적으로 계산 가능한지의 문제는 실질적으로 그 집합을 효율적으로 계산해 내는 함수를 만들어 내는 것과 같은 일이 되었다. 계산 가능성 이론의 초기 성과는 이들 집합을 계산적으로 동치인 것들로 묶어 위계로 분류한 것이다. 수학적으로 유한히 정의된 함수를 계산 가능성에 따라 분류했을 때 어떤 함수의 계산 가능성 문제를 다른 함수(다른 함수들)의 문제로 환원할 수 있다는 것을 보임으로써, 굳이 알고리즘 자체를 증명에 끌어들이지 않고도 계산 가능성을 증명할 수 있는 것이다. 이에 따라 대안적인 공리계를 모색하기 위한 이론적 토대가 마련되었고, 수리논리학과 증명론에서 직관주의가 입지를 공고히 했으며, 유형 이론과 고차 논리, 자연 연역, 헤이팅 대수의 비약적 발전에 영향을 주었다. 계산 복잡도 이론에서는 계산 가능한 집합을 그 함수의 해를 찾는 효율적인 알고리즘에 의해 소모되는 시공간적 자원의 추세를 토대로 분류한다. 이에 따라 계산 복잡도 이론과 계산 가능성 이론 중 어느 쪽이 상위의 개념인지에 관해 다소 논쟁이 있다. (ko)
- Teoria obliczalności, także teorii rekursji – dział teorii obliczeń zajmujący się badaniem jakie problemy są rozwiązywalne przy użyciu komputerów. Nie należy mylić teorii obliczalności z teorią złożoności obliczeniowej, zajmującej się badaniem jak efektywnie da się rozwiązywać różne problemy. Podstawowym obiektem badań teorii obliczalności są funkcje obliczalne. (pl)
- A teoria da computabilidade, também chamada de teoria da recursão, é um ramo da lógica matemática que foi originado na década de 1930 com o estudo das funções computáveis e do grau de Turing. O ramo se estendeu e passou a incluir o estudo generalizado da computabilidade e definibilidade. Nessas áreas, a teoria da recursão sobrepõe-se à teoria da prova e teoria efetiva de descrição dos conjuntos. As questões básicas envolvidas na teoria da recursão são " O que significa para uma função (N->N) ser computável?" e "Como funções não-computáveis são classificadas em uma teoria baseada nos seus níveis de não-computabilidade?". As respostas para estas perguntas levaram a uma rica teoria que ainda está sendo estudada atualmente.O ramo se aproximou também com relação à ciência da computação. Estudiosos da recursão em lógica matemática frequentemente estudam a teoria da computabilidade relativa, noções de redutibilidade e estruturas de grau descritas neste artigo. Isto contrasta com a teoria das hierarquias subrecursivas, métodos formais e linguagens formais que são comuns no estudo da teoria da computabilidade na ciência da computação. Existe uma sobreposição considerável no conhecimento e nos métodos entre estas duas comunidades de pesquisa. No entanto, não existe uma grande separação entre elas. (pt)
- Теорія обчислюваності, також відома як теорія рекурсії, є розділом математичної логіки, інформатики та теорії обчислень, що виникла в 1930-х роках з вивчення обчислювальних функцій і степенів Тюрінга. З тих пір ця сфера розширилася, включивши в себе вивчення узагальненої обчислюваності та . У цих областях теорія обчислюваності перетинається з теорією доказів та . Основні питання, які вирішує теорія обчислюваності, включають:
* Що означає обчислюваність функції над натуральними числами?
* Як можна класифікувати необчислювані функції в ієрархію на основі їхнього рівня не обчислюваності? Теоретики математичної обчислюваності вивчають теорію відносної обчислюваності, поняття зведеності та структури степенів; В свою чергу, в фокусі інформатики знаходяться теорія субрекурсивних ієрархій, формальні методи і формальні мови. (uk)
- Теория вычислимости, также известная как теория рекурсивных функций, — это раздел современной математики, лежащий на стыке математической логики, теории алгоритмов и информатики, возникшей в результате изучения понятий вычислимости и невычислимости. Изначально теория была посвящена вычислимым и невычислимым функциям и сравнению различных моделей вычислений. Сейчас поле исследования теории вычислимости расширилось — появляются новые определения понятия вычислимости и идёт слияние с математической логикой, где вместо вычислимости и невычислимости идёт речь о доказуемости и недоказуемости (выводимости и невыводимости) утверждений в рамках каких-либо теорий. Теория вычислимости берёт своё начало от работы Алана Тьюринга (1936) «On Computable Numbers, With An Application to Entscheidungsproblem», в которой он ввел понятие абстрактной вычислительной машины, получившей впоследствии его имя, и доказал фундаментальную теорему о неразрешимости задачи о её остановке. Знаменитая теорема Гёделя о неполноте (1931) была доказана в терминах примитивно рекурсивных функций, класс которых в 1934 году Гёдель расширил до класса общерекурсивных функций. Формализм, развитый Гёделем, оказался эквивалентным тьюринговскому (а также многим другим). Вместе с тезисом Чёрча — Тьюринга этот факт явно продемонстрировал содержательность новой теории, и сейчас эти определения общеприняты в качестве формального аналога алгоритмически вычислимых функций. Определение вычислимых функций, данное Гёделем, носило синтаксический характер, и лишь установление совпадения этого класса с классом общерекурсивных функций (вместе с формулировкой и «принятием» тезиса Чёрча) показало действительную значимость теоремы о неполноте.Ершов, Юрий Леонидович (ru)
- 在计算机科学中，可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。 (zh)
|
| rdfs:comment
|
- نظرية الحاسوبية (بالإنجليزية: computability theory) وتعرف أيضاً بالنظرية العودية وأيضا بنظرية الاستدعاء الذاتي (بالإنجليزية: Recursion theory) وهي أحد فروع المعلوماتية النظرية تم تأسيسه في عام 1930م theoretical computer science والتي تدرس مسائل قابلة للحلحلة حاسوبيا computationally solvable باستخدام نماذج مختلفة للحوسبة. نظرية الحاسوبية تختلف عن التخصصات المشابهة لنظرية التعقيد الحسابي computational complexity theory ، فالأخيرة تتعامل مع سؤال كيفية حل المسألة حاسوبيا بفعالية، بدلا من سؤال إذا كانت المسألة قابلة للحل حاسوبيا أم لا؟ solvable الذي تتناوله نظرية الحاسوبية. (ar)
- Konputagarritasunaren teoria problema erabakigarriak aztertzen dituen konputazioko atala da, 1930ean aztertzen hasi zena. Orokorrean, algoritmo baten bidez edo Turing makina baten bidez (baliokidea dena) ebatzi daitezkeen problemak aztertzen ditu, hain zuzen. (eu)
- 計算可能性理論（けいさんかのうせいりろん、英: computability theory）とは、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。 (ja)
- Teoria obliczalności, także teorii rekursji – dział teorii obliczeń zajmujący się badaniem jakie problemy są rozwiązywalne przy użyciu komputerów. Nie należy mylić teorii obliczalności z teorią złożoności obliczeniowej, zajmującej się badaniem jak efektywnie da się rozwiązywać różne problemy. Podstawowym obiektem badań teorii obliczalności są funkcje obliczalne. (pl)
- 在计算机科学中，可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。 (zh)
- La teoria de la computabilitat és la part de la computació que estudia els problemes de decisió que poden ser resolts amb un algorisme o equivalentment amb una màquina de Turing. La teoria de la computabilitat s'interessa per quatre preguntes:
* Quins problemes pot resoldre una màquina de Turing?
* Quins altres formalismes equivalen a les màquines de Turing?
* Quins problemes requereixen màquines més poderoses?
* Quins problemes requereixen màquines menys poderoses? (ca)
- Teorie vyčíslitelnosti je vědní obor na pomezí matematiky a informatiky, který zkoumá otázky algoritmické řešitelnosti problémů. Vytváří teoretický základ a zkoumá možnosti a hranice využití algoritmicky pracujících postupů, což se v praxi uplatňuje především na počítačové programy. Pod pojmem algoritmu se běžně rozumí mechanizovaný postup, který lze realizovat třeba na Turingově stroji. Významnou roli ve filozofickém podložení teorie vyčíslitelnosti hraje Churchova–Turingova teze, podle níž jsou všechny „rozumné“ výpočetní modely ekvivalentní Turingově stroji. (cs)
- Η Θεωρία της Υπολογισιμότητας ή Θεωρία της Αναδρομής, είναι ένας κλάδος της μαθηματικής λογικής, της πληροφορικής και της θεωρίας υπολογισμού που προήλθε από την έρευνα των υπολογίσιμων συναρτήσεων και του βαθμού Turing (=βαθμος μη επιλυσιμότητας) στα μέσα της δεκαετίας του 1930. (el)
- Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory. Basic questions addressed by computability theory include: (en)
- La teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que se pueden resolver con un algoritmo o equivalentemente con una máquina de Turing. Las preguntas fundamentales de la teoría de la computabilidad son:
* ¿Qué problemas puede resolver una máquina de Turing?
* ¿Qué otros formalismos equivalen a las máquinas de Turing?
* ¿Qué problemas requieren máquinas más poderosas?
* ¿Qué problemas requieren máquinas menos poderosas? (es)
- Die Berechenbarkeitstheorie (auch Rekursionstheorie) ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere damit, welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen Modells einer Maschine) oder eines anderen mathematischen Modells der Berechenbarkeit lösbar sind. Sie ist eng verwandt mit der formalen Semantik, richtet aber die Aufmerksamkeit mehr auf die Terminiertheit von Programmen und Algorithmen. (de)
- La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique. La calculabilité (parfois appelée « computationnalité »[réf. nécessaire], de l'anglais computability) cherche d'une part à identifier la classe des fonctions qui peuvent être calculées à l'aide d'un algorithme et d'autre part à appliquer ces concepts à des questions fondamentales des mathématiques. Une bonne appréhension de ce qui est calculable et de ce qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs. (fr)
- La teoria della calcolabilità, della computabilità, e della ricorsione cerca di comprendere quali funzioni possono essere calcolate tramite un procedimento automatico. In altre parole, essa cerca di determinare se una data funzione è teoricamente calcolabile a prescindere dal fatto che sia anche trattabile, cioè a prescindere dalla quantità di risorse che la sua esecuzione richiede in termini di tempo o di memoria, che a livello pratico potrebbero essere proibitive. Questa disciplina è comune sia alla matematica sia all'informatica. (it)
- ( 재귀 이론은 여기로 연결됩니다. 다른 뜻에 대해서는 문서를 참고하십시오.) 계산 가능성 이론(計算可能性理論, 영어: computability theory) 또는 재귀 이론(再歸理論, 영어: recursion theory)은 수학기초론의 중요한 분야이자 컴퓨터 과학에서는 계산 이론의 한 갈래이다. 계산 가능성 이론의 기초는 가산 집합 상에서 함수의 해를 찾는 문제와 관련이 있다. 1930년대 불완전성 정리와 함께 람다 대수와 튜링 기계라는 계산 모형이 만들어지면서, 어떤 집합이 효율적으로 계산 가능한지의 문제는 실질적으로 그 집합을 효율적으로 계산해 내는 함수를 만들어 내는 것과 같은 일이 되었다. 계산 가능성 이론의 초기 성과는 이들 집합을 계산적으로 동치인 것들로 묶어 위계로 분류한 것이다. 수학적으로 유한히 정의된 함수를 계산 가능성에 따라 분류했을 때 어떤 함수의 계산 가능성 문제를 다른 함수(다른 함수들)의 문제로 환원할 수 있다는 것을 보임으로써, 굳이 알고리즘 자체를 증명에 끌어들이지 않고도 계산 가능성을 증명할 수 있는 것이다. 이에 따라 대안적인 공리계를 모색하기 위한 이론적 토대가 마련되었고, 수리논리학과 증명론에서 직관주의가 입지를 공고히 했으며, 유형 이론과 고차 논리, 자연 연역, 헤이팅 대수의 비약적 발전에 영향을 주었다. (ko)
- A teoria da computabilidade, também chamada de teoria da recursão, é um ramo da lógica matemática que foi originado na década de 1930 com o estudo das funções computáveis e do grau de Turing. O ramo se estendeu e passou a incluir o estudo generalizado da computabilidade e definibilidade. Nessas áreas, a teoria da recursão sobrepõe-se à teoria da prova e teoria efetiva de descrição dos conjuntos. As questões básicas envolvidas na teoria da recursão são " O que significa para uma função (N->N) ser computável?" e "Como funções não-computáveis são classificadas em uma teoria baseada nos seus níveis de não-computabilidade?". As respostas para estas perguntas levaram a uma rica teoria que ainda está sendo estudada atualmente.O ramo se aproximou também com relação à ciência da computação. Estudio (pt)
- Теория вычислимости, также известная как теория рекурсивных функций, — это раздел современной математики, лежащий на стыке математической логики, теории алгоритмов и информатики, возникшей в результате изучения понятий вычислимости и невычислимости. Изначально теория была посвящена вычислимым и невычислимым функциям и сравнению различных моделей вычислений. Сейчас поле исследования теории вычислимости расширилось — появляются новые определения понятия вычислимости и идёт слияние с математической логикой, где вместо вычислимости и невычислимости идёт речь о доказуемости и недоказуемости (выводимости и невыводимости) утверждений в рамках каких-либо теорий. (ru)
- Теорія обчислюваності, також відома як теорія рекурсії, є розділом математичної логіки, інформатики та теорії обчислень, що виникла в 1930-х роках з вивчення обчислювальних функцій і степенів Тюрінга. З тих пір ця сфера розширилася, включивши в себе вивчення узагальненої обчислюваності та . У цих областях теорія обчислюваності перетинається з теорією доказів та . Основні питання, які вирішує теорія обчислюваності, включають:
* Що означає обчислюваність функції над натуральними числами?
* Як можна класифікувати необчислювані функції в ієрархію на основі їхнього рівня не обчислюваності? (uk)
|