Computability theory (original) (raw)
نظرية الحاسوبية (بالإنجليزية: computability theory) وتعرف أيضاً بالنظرية العودية وأيضا بنظرية الاستدعاء الذاتي (بالإنجليزية: Recursion theory) وهي أحد فروع المعلوماتية النظرية تم تأسيسه في عام 1930م theoretical computer science والتي تدرس مسائل قابلة للحلحلة حاسوبيا computationally solvable باستخدام نماذج مختلفة للحوسبة. نظرية الحاسوبية تختلف عن التخصصات المشابهة لنظرية التعقيد الحسابي computational complexity theory ، فالأخيرة تتعامل مع سؤال كيفية حل المسألة حاسوبيا بفعالية، بدلا من سؤال إذا كانت المسألة قابلة للحل حاسوبيا أم لا؟ solvable الذي تتناوله نظرية الحاسوبية.
Property | Value |
---|---|
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) |
dbo:wikiPageExternalLink | http://www.aslonline.org/ http://www.maths.leeds.ac.uk/cie/ http://web.mit.edu/~6.863/www/spring2009/readings/gold67limit.pdf http://www.comp.nus.edu.sg/~fstephan/learning.ps http://www.comp.nus.edu.sg/~fstephan/recursiontheory.html https://archive.org/details/classicalrecursi0000odif https://archive.org/details/handbookofmathem0090unse/page/527 https://web.archive.org/web/20090125120159/http:/www.isrl.uiuc.edu/~amag/langev/paper/gold67limit.html |
dbo:wikiPageID | 155414 (xsd:integer) |
dbo:wikiPageLength | 55425 (xsd:nonNegativeInteger) |
dbo:wikiPageRevisionID | 1120805891 (xsd:integer) |
dbo:wikiPageWikiLink | dbr:Cantor's_theorem dbr:Primitive_recursive_function dbr:Neural_network dbr:North-Holland dbr:Algorithm dbr:Annals_of_Mathematics dbr:Hypersimple_set dbr:Peano_arithmetic dbr:Reverse_mathematics dbr:Definable_set dbr:Μ-recursive_function dbr:Dynamical_system dbr:E._Mark_Gold dbr:Computability dbr:Computability_in_Europe dbr:Computable_function dbr:Countable_set dbr:Analog_computer dbr:Analog_signal_processing dbr:Analytical_hierarchy dbr:Mathematical_logic dbr:Mathematics dbr:Matiyasevich's_theorem dbr:Pyotr_Novikov dbr:Church–Turing_thesis dbr:Elsevier dbr:Function_(mathematics) dbr:Control_theory dbr:Erlangen_program dbr:Andrey_Markov_Jr. dbr:Arithmetical_hierarchy dbr:MIT_Press dbr:Blum–Shub–Smale_machine dbr:Stephen_Kleene dbr:Computability_logic dbr:Computable_set dbr:Computably_enumerable_set dbr:Computational_complexity_theory dbr:Computer_science dbr:Yuri_Matiyasevich dbr:Friedberg_numbering dbr:Henry_Gordon_Rice dbr:Identity_element dbr:Primitive_recursive_arithmetic dbr:Steve_Simpson_(mathematician) dbr:Theoretical_Computer_Science_(journal) dbr:Theory_of_computation dbr:Many-one_reduction dbr:Busy_Beaver dbr:Admissible_numbering dbr:Total_function dbr:William_Boone_(mathematician) dbr:Gödel's_completeness_theorem dbr:Harvey_Friedman dbr:Julia_Robinson dbr:Alan_Turing dbr:Alfred_Tarski dbr:Alonzo_Church dbr:Analog_electronics dbr:Alpha_recursion_theory dbr:First-order_logic dbr:Oxford_University_Press dbr:Differential_equation dbr:Formal_language dbr:Goodstein's_theorem dbr:Hilbert's_tenth_problem dbr:Journal_of_Symbolic_Logic dbr:Kolmogorov_complexity dbr:Proof_theory dbr:Recursively_enumerable dbr:Group_(mathematics) dbr:Gödel's_incompleteness_theorem dbr:Halting_problem dbr:Ackermann_function dbc:Computability_theory dbc:Mathematical_logic dbr:Chapman_&_Hall dbr:Bijection dbr:Effective_descriptive_set_theory dbr:Tarski's_indefinability_theorem dbr:Word_problem_for_groups dbr:Diophantine_equation dbr:Association_for_Symbolic_Logic dbr:Injective_function dbr:Algorithmically_random_set dbr:Kurt_Gödel dbr:Natural_number dbr:Cantor_space dbr:Recursion_(computer_science) dbr:Recursive_set dbr:Recursively_enumerable_set dbr:Reduction_(recursion_theory) dbr:Set_theory dbr:Maximal_set dbr:Model_of_computation dbr:Turing_machine dbr:Rózsa_Péter dbr:Second-order_arithmetic dbr:Universal_Turing_machine dbr:List_of_undecidable_problems dbr:Turing_jump dbr:Robert_I._Soare dbr:Post's_theorem dbr:Transcomputational_problem dbr:Word_problem_for_semigroups dbr:Simple_set dbr:Rice's_theorem dbr:Turing_degree dbr:Uncountable_set dbr:The_Journal_of_Symbolic_Logic dbr:Transactions_of_the_American_Mathematical_Society dbr:Post's_problem dbr:Powerset dbr:Limiting_recursive dbr:Turing_reducible dbr:Springer-Verlag dbr:Emil_Post dbr:Analog_computation dbr:Arithmetic_reducibility dbr:Arithmetical_reducibility dbr:Nigel_J._Cutland dbr:Oracle_Turing_machine dbr:Hyperarithmetical_reducibility dbr:Formal_method dbr:Information_and_Control dbr:Algorithmic_randomness dbr:Bradford_Book dbr:Semirecursive dbr:Truth_table_reduction dbr:Degree_of_constructibility |
dbp:cs1Dates | y (en) |
dbp:date | August 2022 (en) |
dbp:group | "nb" (en) |
dbp:wikiPageUsesTemplate | dbt:Blockquote dbt:Cite_book dbt:Cite_journal dbt:Color dbt:Commonscat dbt:For dbt:Further dbt:Main dbt:Portal dbt:Reflist dbt:Rp dbt:Short_description dbt:Use_dmy_dates dbt:Use_list-defined_references dbt:Val dbt:Harvnb dbt:Computer_science dbt:Mathematical_logic dbt:COther |
dct:subject | dbc:Computability_theory dbc:Mathematical_logic |
gold:hypernym | dbr:Branch |
rdf:type | dbo:Organisation |
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) |
rdfs:label | Computability theory (en) نظرية الحاسوبية (ar) Teoria de la computabilitat (ca) Teorie vyčíslitelnosti (cs) Berechenbarkeitstheorie (de) Θεωρία υπολογισιμότητας (el) Teoría de la computabilidad (es) Konputagarritasunaren teoria (eu) Théorie de la calculabilité (fr) Teoria della calcolabilità (it) 계산 가능성 이론 (ko) 計算可能性理論 (ja) Teoria da computabilidade (pt) Teoria obliczalności (pl) Теория вычислимости (ru) Теорія обчислюваності (uk) 可计算性理论 (zh) |
owl:sameAs | freebase:Computability theory http://sw.cyc.com/concept/Mx4rv_1KSZwpEbGdrcN5Y29ycA wikidata:Computability theory dbpedia-ar:Computability theory http://ast.dbpedia.org/resource/Teoría_de_la_computabilidá dbpedia-bg:Computability theory http://bn.dbpedia.org/resource/পরিগণনীয়তা_তত্ত্ব_(কম্পিউটার_বিজ্ঞান) dbpedia-ca:Computability theory dbpedia-cs:Computability theory http://cv.dbpedia.org/resource/Шутланаяслăх_теорийĕ dbpedia-da:Computability theory dbpedia-de:Computability theory dbpedia-el:Computability theory dbpedia-es:Computability theory dbpedia-eu:Computability theory dbpedia-fa:Computability theory dbpedia-fr:Computability theory dbpedia-gl:Computability theory dbpedia-he:Computability theory dbpedia-hr:Computability theory dbpedia-it:Computability theory dbpedia-ja:Computability theory dbpedia-ko:Computability theory dbpedia-la:Computability theory http://my.dbpedia.org/resource/တွက်ချက်နိုင်စွမ်းသီအိုရီ dbpedia-pl:Computability theory dbpedia-pt:Computability theory dbpedia-ro:Computability theory dbpedia-ru:Computability theory dbpedia-sh:Computability theory dbpedia-simple:Computability theory dbpedia-sk:Computability theory dbpedia-sr:Computability theory dbpedia-th:Computability theory http://tl.dbpedia.org/resource/Teorya_ng_komputabilidad dbpedia-tr:Computability theory dbpedia-uk:Computability theory dbpedia-vi:Computability theory dbpedia-zh:Computability theory https://global.dbpedia.org/id/4ydB8 |
prov:wasDerivedFrom | wikipedia-en:Computability_theory?oldid=1120805891&ns=0 |
foaf:isPrimaryTopicOf | wikipedia-en:Computability_theory |
is dbo:knownFor of | dbr:Yuri_Matiyasevich dbr:Valentina_Harizanov |
is dbo:wikiPageRedirects of | dbr:Computability_theory_(computer_science) dbr:Turing_computability dbr:Computability_Theory dbr:Continuous_computability_theory dbr:Ecursion_theory dbr:Recursion_theory dbr:Computability_theory_(computation) dbr:Theory_of_computability |
is dbo:wikiPageWikiLink of | dbr:Bekić's_theorem dbr:Primitive_recursive_function dbr:Rod_Downey dbr:Enumeration_algorithm dbr:Enumeration_reducibility dbr:List_of_Utah_State_University_alumni dbr:List_of_algorithm_general_topics dbr:List_of_computability_and_complexity_topics dbr:List_of_computer_scientists dbr:Mortality_(computability_theory) dbr:Boris_Trakhtenbrot dbr:Decider_(Turing_machine) dbr:Algorithm dbr:Algorithmic_information_theory dbr:Approximation-preserving_reduction dbr:History_of_the_function_concept dbr:John_Myhill dbr:List_of_important_publications_in_computer_science dbr:List_of_pioneers_in_computer_science dbr:Richard_M._Friedberg dbr:Cylindric_numbering dbr:Cylindrification dbr:Undefined_value dbr:Universality_probability dbr:Vladimir_Andreyevich_Uspensky dbr:Decision_problem dbr:Definable_set dbr:Dynamic_epistemic_logic dbr:Incompressibility_method dbr:Index_of_computing_articles dbr:Index_set_(computability) dbr:Integer-valued_function dbr:List_of_mathematical_logic_topics dbr:List_of_people_with_bipolar_disorder dbr:Numbering_(computability_theory) dbr:Combinatory_logic dbr:Computability dbr:Computability_in_Europe dbr:Computability_theory_(computer_science) dbr:Computably_inseparable dbr:Computer dbr:Course-of-values_recursion dbr:Mathematical_analysis dbr:Mathematical_logic dbr:Mathematics dbr:S._Barry_Cooper dbr:Generic_filter dbr:Generic_property dbr:Numbering_scheme dbr:Oracle_machine dbr:Sierpiński_space dbr:Trakhtenbrot's_theorem dbr:Edward_F._Moore dbr:Emil_Leon_Post dbr:Enumeration dbr:Epistemology dbr:Function_(mathematics) dbr:Glossary_of_areas_of_mathematics dbr:Glossary_of_artificial_intelligence dbr:Glossary_of_computer_science dbr:Constant-recursive_sequence dbr:Constructive_set_theory dbr:Constructor_theory dbr:Theory dbr:Orchestrated_objective_reduction dbr:Basis_theorem_(computability) dbr:Logic dbr:Chong_Chi_Tat dbr:Complete_numbering dbr:Complexity_class dbr:Computability_in_Analysis_and_Physics dbr:Computable_analysis dbr:Computable_number dbr:Computable_ordinal dbr:Computable_set dbr:Computably_enumerable_set dbr:Computation_in_the_limit dbr:Computational_complexity_theory dbr:Computer_science dbr:Yuri_Matiyasevich dbr:Friedberg_numbering dbr:Hardy_hierarchy dbr:Partial_function dbr:Programming_language_theory dbr:Psi_(Greek) dbr:Specker_sequence dbr:Theoretical_computer_science dbr:Theory_of_computation dbr:Many-one_reduction dbr:Markov's_principle dbr:Mathematical_psychology dbr:Busy_beaver dbr:Admissible_numbering dbr:Turing_computability dbr:William_Gasarch dbr:Gödel_numbering dbr:Joel_David_Hamkins dbr:Julia_F._Knight dbr:Julia_Robinson dbr:K-trivial_set dbr:Lambda-mu_calculus dbr:Logic_in_computer_science dbr:Truth-table_reduction dbr:20th_century_in_science dbr:Dag_Normann dbr:EXPTIME dbr:Fallibilism dbr:Formal_epistemology dbr:Anil_Nerode dbr:Diagonal_lemma dbr:Fast-growing_hierarchy dbr:Forcing_(computability) dbr:Hilbert's_tenth_problem dbr:Hill_Tinsley_Medal dbr:History_of_logic dbr:History_of_mathematics dbr:John_V._Tucker dbr:Valentina_Harizanov dbr:Quine_(computing) dbr:RE_(complexity) dbr:Recognizable_set dbr:Reduction_(complexity) dbr:Reductionism dbr:Gödel's_incompleteness_theorems dbr:Günter_Asser dbr:High_(computability) dbr:Hilary_Putnam dbr:Bakhadyr_Khoussainov dbr:Counter_(digital) dbr:Counting_problem_(complexity) dbr:Subcountability dbr:Smn_theorem dbr:Ackermann_function dbr:Karl_Svozil dbr:Kenneth_Appel dbr:Effective_dimension dbr:Effective_method dbr:Effective_results_in_number_theory dbr:Write-only_memory_(engineering) dbr:Reduction_(computability_theory) dbr:Marcia_Groszek dbr:Martin_Löb dbr:Piergiorgio_Odifreddi dbr:Grzegorczyk_hierarchy dbr:Recursion_(computer_science) dbr:Search_problem dbr:Self-reference dbr:Kleene's_O dbr:Kleene's_T_predicate dbr:Kleene's_recursion_theorem dbr:Mathematics_Subject_Classification dbr:Schröder–Bernstein_property dbr:Undecidable_problem dbr:Viggo_Stoltenberg-Hansen dbr:European_Master_Program_in_Computational_Logic dbr:Computability_Theory dbr:Impossibility_of_a_gambling_system dbr:List_of_undecidable_problems dbr:Turing_jump dbr:Real_computation dbr:Fixed-point_theorems dbr:Spin_model dbr:Tarski–Kuratowski_algorithm dbr:Super-recursive_algorithm dbr:Turing_reduction dbr:UTM_theorem dbr:Reverse_Mathematics:_Proofs_from_the_Inside_Out dbr:The_Dream_of_Reality dbr:Simple_set dbr:Outline_of_epistemology dbr:Outline_of_logic dbr:PA_degree dbr:Rice's_theorem dbr:Slicing_the_Truth dbr:Slow-growing_hierarchy dbr:Turing_degree dbr:Turing_completeness dbr:Π01_class dbr:Continuous_computability_theory dbr:Ecursion_theory dbr:Recursion_theory dbr:Computability_theory_(computation) dbr:Theory_of_computability |
is dbp:mainInterests of | dbr:Vladimir_Andreyevich_Uspensky |
is rdfs:seeAlso of | dbr:Quantum_computing |
is foaf:primaryTopic of | wikipedia-en:Computability_theory |