HTML Microdata document

This HTML5 document contains 345 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dbt	http://dbpedia.org/resource/Template:
dbpedia-el	http://el.dbpedia.org/resource/
wikipedia-en	http://en.wikipedia.org/wiki/
dbr	http://dbpedia.org/resource/
dbpedia-ar	http://ar.dbpedia.org/resource/
dbpedia-he	http://he.dbpedia.org/resource/
dbpedia-fr	http://fr.dbpedia.org/resource/
dct	http://purl.org/dc/terms/
rdfs	http://www.w3.org/2000/01/rdf-schema#
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
dbp	http://dbpedia.org/property/
xsdh	http://www.w3.org/2001/XMLSchema#
dbpedia-uk	http://uk.dbpedia.org/resource/
dbo	http://dbpedia.org/ontology/
dbpedia-sr	http://sr.dbpedia.org/resource/
dbpedia-vi	http://vi.dbpedia.org/resource/
dbpedia-pt	http://pt.dbpedia.org/resource/
dbpedia-ja	http://ja.dbpedia.org/resource/
dbc	http://dbpedia.org/resource/Category:
dbpedia-pl	http://pl.dbpedia.org/resource/
yago	http://dbpedia.org/class/yago/
dbpedia-ru	http://ru.dbpedia.org/resource/
wikidata	http://www.wikidata.org/entity/
n26	http://dbpedia.org/resource/Reverse_Mathematics:
gold	http://purl.org/linguistics/gold/
yago-res	http://yago-knowledge.org/resource/
n37	https://global.dbpedia.org/id/
n32	https://academic.oup.com/plms/issue/s2-42/
dbpedia-it	http://it.dbpedia.org/resource/
dbpedia-ca	http://ca.dbpedia.org/resource/
n14	http://ast.dbpedia.org/resource/
prov	http://www.w3.org/ns/prov#
foaf	http://xmlns.com/foaf/0.1/
dbpedia-simple	http://simple.dbpedia.org/resource/
dbpedia-zh	http://zh.dbpedia.org/resource/
dbpedia-ko	http://ko.dbpedia.org/resource/
dbpedia-gl	http://gl.dbpedia.org/resource/
dbpedia-es	http://es.dbpedia.org/resource/
freebase	http://rdf.freebase.com/ns/
owl	http://www.w3.org/2002/07/owl#

Statements

Subject Item: dbr:Primitive_recursive_function
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Entscheidungsproblem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:List_of_forcing_notions
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Myhill_isomorphism_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Paris–Harrington_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Total_computable_function
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: dbr:Brainfuck
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Algorithmic_probability
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:History_of_the_function_concept
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Hyperoperation
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Peano_axioms
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Reverse_mathematics
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Reversible_cellular_automaton
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Uncomputable
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: dbr:Decidability_(logic)
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Index_set_(computability)
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:List_of_important_publications_in_mathematics
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:List_of_inventions_and_discoveries_by_women
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:List_of_mathematical_functions
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:List_of_mathematical_logic_topics
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Numbering_(computability_theory)
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Penrose–Lucas_argument
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Space_hierarchy_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:0
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Computability_theory
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Computable_function
rdf:type: yago:WikicatFunctionsAndMappings yago:Function113783816 yago:Abstraction100002137 yago:Relation100031921 dbo:Planet owl:Thing yago:MathematicalRelation113783581
rdfs:label: Обчислювана функція 계산 가능 함수 Funció computable Função computável دالة قابلة للحساب Вычислимая функция Función computable Fonction calculable 計算可能関数可计算函数 Υπολογίσιμη συνάρτηση Funzione calcolabile Computable function Funkcja obliczalna
rdfs:comment: Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y son, específicamente, las funciones que pueden ser calculadas por una máquina de Turing. Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Any definition, however, must make reference to some specific model of computation but all valid definitions yield the same class of functions.Particular models of computability that give rise to the set of computable functions are the Turing-computable functions and the general recursi Υπολογίσιμες συναρτήσεις είναι τα βασικά αντικείμενα μελέτης στη θεωρία υπολογισιμότητας. Υπολογίσιμες συναρτήσεις είναι η τυποποιημένη αναλογική της διαισθητικής ιδέας του αλγορίθμου, με την έννοια ότι μια συνάρτηση είναι υπολογίσιμη αν υπάρχει ένας αλγόριθμος που μπορεί να κάνει τη δουλειά της συνάρτησης, δηλαδή με δεδομένο εισόδου το πεδίο ορισμού της συνάρτησης να μπορεί να επιστρέψει το αντίστοιχο της παραγωγής. Υπολογίσιμες συναρτήσεις χρησιμοποιούνται για να συζητήσουν υπολογισιμότητα, χωρίς να αναφέρονται σε κανένα συγκεκριμένο μοντέλο υπολογισμού όπως παραδείγματος χάρη οι μηχανές Τούρινγκ ή οι . Κάθε ορισμός, ωστόσο, πρέπει να κάνει αναφορά σε κάποιο συγκεκριμένο μοντέλο υπολογισμού αλλά ισχύουν οι ορισμοί της απόδοσης της ίδιας κατηγορίας των συναρτήσεων.Συγκεκριμένα μοντέλα υπο 계산 가능한 함수(computable function)는 그 함수의 결과값을 특정한 계산 방식을 따라 유한 시간 안에 얻어낼 수 있는 함수를 의미한다. 계산 가능한 함수는 알고리즘의 개념을 함수로 표현한 것으로 볼 수 있는데, 이때 함수는 특정한 알고리즘으로 정의되고, 해당 알고리즘을 계산하는 것으로 함수의 값을 얻는다. 계산 가능한 함수의 구체적인 정의는 계산 모델에 따라 결정되는데, 다음의 계산 모델은 모두 동일한 계산 가능성을 가지며, 따라서 이를 기반으로 정의하는 계산 가능한 함수 역시 동일한 의미를 가진다. * 튜링 기계 * μ-재귀 함수 * 람다 대수 Обч́ислювана фу́нкція (англ. computable function) — основний об'єкт вивчення теорії обчислень. Обчислюваною функцією називають таку функцію, результат якої може бути отримано за допомогою деякого ефективного процесу. Це поняття дозволяє при формулюванні алгоритмів не спиратися на конкретні реалізації обчислювальних машин, а зосередитися на загальних алгоритмічних принципах. Існують різні формальні способи конкретизувати, як саме має бути реалізовано цей процес. Це може бути зроблено за допомогою наступних систем: * машина Тьюрінга * * Лямбда-числення * Машина Поста * Le funzioni calcolabili sono il principale oggetto di studio della teoria della calcolabilità. Le funzioni calcolabili sono l'analogo formale della nozione intuitiva di algoritmo, nel senso che una funzione è calcolabile se esiste un algoritmo che può svolgere il compito della funzione stessa, cioè se dato un input del dominio della funzione, questa è in grado di restituire il corrispondente output. Secondo la (non ancora dimostrata) tesi di Church-Turing, le funzioni calcolabili corrispondono alle funzioni ricorsive, e quindi a tutti i modelli di calcolo equivalenti. الدوال الحسابية (بالإنجليزية: Computable function)‏ هي المواد الأساسية في دراسة النظرية الحسابية. الدوال الحسابية هي التماثلية الرسمية للفكرة البديهية للخوارزمية.. وهي تستخدم لمناقشة الحسابية دون الإشارة إلى أي نموذج ملموس من الحساب مثل آلات تورنغ أو آلات التسجيل. ورغم ذلك فإن أي تعريف يجب أن يكون له مرجعية لبعض النماذج المحددة من الحساب ولكن كل التعريفات الصحيحة تحقق نفس الدرجة من الوظائف. نماذج معينة من الحاسوبية التي تؤدي إلى مجموعة من الوظائف الحسابية هي دوال تورنغ الحسابية ودوال المايكرو المتكررة.قبل التعريف الدقيق للدالة الحسابية، غالباً ما كان يستخدم علماء الرياضيات المصطلح غير الرسمي محسوب بشكل فعّال. لقد أصبح هذا المصطلح منذ ذلك الحين معرّف بالدوال الحسابية. لاحظ أن الحاسوبية الفعّآلة لهذه الدوال لا تدل على أنه يمكن حسابهم بطريقة فعّآلة (بمعنى: يتم حسابهم في قدر معقول من الوقت). ف Les funcions computables són l'objecte bàsic d'estudi de la teoria de la computabilitat i consisteixen en les funcions que poden ser calculades per una màquina de Turing. Funkcje obliczalne – podstawowy obiekt badań teorii obliczalności. Zbiór funkcji obliczalnych jest równoważny zbiorowi funkcji obliczalnych w sensie Turinga oraz funkcji częściowo rekurencyjnych. Funkcje obliczalne stanowią analogon intuicyjnego pojęcia algorytmu. Tego pojęcia używa się do dyskusji obliczalności bez odniesienia do określonego modelu obliczalności takiego jak maszyna Turinga lub . Jednak ich definicja musi mieć odniesienie do określonego modelu obliczalności. Funções computáveis são os objetos básicos de estudo na teoria da computabilidade. Funções computáveis são uma analogia formalizada da noção intuitiva de algoritmos. Elas são usadas para discutir a computabilidade sem se referir a algum modelo de computação concreto, como a máquina de Turing e a máquina registradora. Entretanto, o conjunto das funções computáveis é equivalente ao conjunto de funções computáveis numa máquina de Turing. No entanto, qualquer definição precisa fazer referência a algum modelo específico de computação, mas todas as referências válidas geram a mesma classe de funções. Modelos particulares de computabilidade que dão origem ao conjunto de funções computáveis são as funções Turing-computáveis e as funções μ-recursivas. Вычислимые функции — это множество функций вида, которые могут быть реализованы на машине Тьюринга. Задачу вычисления функции называют алгоритмически разрешимой или алгоритмически неразрешимой, в зависимости от того, возможен ли алгоритм, вычисляющий эту функцию. В качестве множества обычно рассматривается множество — множество слов в двоичном алфавите , с оговоркой, что результатом вычисления может быть не только слово, но и специальное значение «неопределённость», соответствующее случаю, когда алгоритм «зависает». Таким образом, можно дать следующее определение : 在可计算性理论中，可计算函数（computable function）或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确。使用可计算函数来讨论可计算性而不提及任何具体的计算模型，如图灵机或寄存器机。但是它们的定义必须提及某种特殊的计算模型。在可计算函数的精确定义之前，数学家经常使用非正式术语可有效计算的。这个术语因此可以被认同为可计算函数。尽管这些函数被叫做有效的，它们可能极其困难。和计算复杂性研究可有效计算的函数。依据邱奇-图灵论题，可计算函数精确的是使用给出无限数量的时间和存储空间的机器计算设备来计算的函数。等价的说，这个论题声称有算法的任何函数都是可计算的。可以使用布盧姆公理来在可计算函数的集合上定义抽象计算复杂性理论。在计算复杂性理论中，确定一个可计算函数的复杂性的问题叫做功能性问题。計算可能関数（けいさんかのうかんすう、英: Computable function）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。
rdfs:seeAlso: dbr:Total_Turing_machine
dct:subject: dbc:Theory_of_computation dbc:Computability_theory
dbo:wikiPageID: 1139338
dbo:wikiPageRevisionID: 1122713957
dbo:wikiPageWikiLink: dbr:Natural_number dbr:Natural_numbers dbr:Countability dbr:Prime_factor dbr:Tuple dbr:Diagonal_lemma dbr:Model_of_computation dbr:Effectively_calculable dbr:Recursion_theory dbr:Μ_operator dbr:Constant_function dbr:Semicomputable_function dbr:Domain_of_a_function dbr:First-order_logic dbr:Arithmetical_hierarchy dbr:Computability_theory_(computer_science) dbr:Arity dbr:Greatest_common_divisor dbr:Feasible_computability dbr:Register_machine dbr:Function_composition dbr:Function_problem dbr:Algorithm dbr:Turing_jump dbr:Computational_complexity_theory dbr:Finitary dbr:Computable_ordinal dbr:If_and_only_if dbr:Mathematician dbr:David_Hilbert dbr:Lambda_calculus dbr:Partial_function dbr:Addition dbr:A._Turing dbr:Computable_number dbr:Ackermann_function dbr:Compiler dbr:Blum_axioms dbr:Busy_beaver dbr:Tetration dbc:Theory_of_computation dbr:Recursive_definition dbr:Entscheidungsproblem dbr:Theory_of_computation dbr:Soundness dbr:Primitive_recursive_function dbr:Finitary_relation dbr:Chaitin's_constant dbr:Herbert_Enderton dbr:Injective dbr:Recursively_enumerable dbr:Turing_machine dbr:Hyperarithmetical_theory dbr:Gödel_number dbr:General_recursive_function dbr:Unary_operation dbr:Church–Turing_thesis dbr:Formal_language dbr:Exponential_growth dbr:Turing_degree dbr:Arg_max dbr:Hypercomputation dbr:Μ-recursive_function dbr:Closure_(mathematics) dbr:Relative_computability dbr:Set_(mathematics) dbr:Kolmogorov_complexity dbr:Halting_problem dbr:Oracle_(computability) dbr:Bézout_coefficient dbc:Computability_theory dbr:Super-recursive_algorithm dbr:Post–Turing_machine dbr:Tag_system dbr:Peano_arithmetic dbr:Multiplication dbr:Turing-computable_function dbr:Effective_method
dbo:wikiPageExternalLink: n32:1
owl:sameAs: freebase:m.049pw9 dbpedia-ja:計算可能関数 yago-res:Computable_function dbpedia-gl:Función_computábel dbpedia-sr:Израчунљива_функција n14:Función_computable dbpedia-he:פונקציה_בת-חישוב dbpedia-ca:Funció_computable dbpedia-vi:Hàm_tính_toán_được dbpedia-fr:Fonction_calculable dbpedia-pt:Função_computável dbpedia-ar:دالة_قابلة_للحساب dbpedia-simple:Computable_function dbpedia-zh:可计算函数 dbpedia-it:Funzione_calcolabile dbpedia-es:Función_computable dbpedia-el:Υπολογίσιμη_συνάρτηση dbpedia-ru:Вычислимая_функция dbpedia-pl:Funkcja_obliczalna dbpedia-ko:계산_가능_함수 n37:CbmG wikidata:Q1148456 dbpedia-uk:Обчислювана_функція
dbp:wikiPageUsesTemplate: dbt:See_also dbt:Citation_needed dbt:Ordered_list dbt:Mset dbt:ComplexityClasses dbt:= dbt:Pi dbt:Math dbt:Short_description dbt:Reflist dbt:Main dbt:Mathematical_logic dbt:Mvar
dbo:abstract: Funções computáveis são os objetos básicos de estudo na teoria da computabilidade. Funções computáveis são uma analogia formalizada da noção intuitiva de algoritmos. Elas são usadas para discutir a computabilidade sem se referir a algum modelo de computação concreto, como a máquina de Turing e a máquina registradora. Entretanto, o conjunto das funções computáveis é equivalente ao conjunto de funções computáveis numa máquina de Turing. No entanto, qualquer definição precisa fazer referência a algum modelo específico de computação, mas todas as referências válidas geram a mesma classe de funções. Modelos particulares de computabilidade que dão origem ao conjunto de funções computáveis são as funções Turing-computáveis e as funções μ-recursivas. Antes de uma definição precisa do termo, matemáticos usavam informalmente o termo "efetivamente computável". Desde então, esse termo vem sendo identificado como função computável. Note que a computabilidade efetiva de tais funções não implica que elas são eficientemente computáveis, isto é, a execução em certa quantidade tolerável de tempo. De fato, pode-se mostrar que para algumas funções computáveis, qualquer algoritmo que a implemente será ineficiente na medida em que seu tempo de execução crescerá exponencialmente (ou mesmo superexponencialmente) de acordo com o tamanho da entrada. Os campos da computação factível e complexidade computacional estudam funções que podem ser computadas eficientemente. De acordo com a tese de Church-Turing, funções computáveis são exatamente as funções que podem ser calculadas usando um dispositivo mecânico de calculo dado uma quantidade ilimitada de espaço de armazenamento e de tempo de execução. De maneira equivalente, a mesma tese define que qualquer função que possui um algoritmo é computável. Observe que um algoritmo, neste sentido, é interpretado como sendo uma sequência de passos que uma pessoa, com tempo ilimitado e caneta e papéis infinitos, pode seguir. Os axiomas de Blum podem ser usados para definir uma teoria de complexidade computacional abstrato, sobre o conjunto de funções computáveis. Na teoria da complexidade computacional, o problema de se determinar a complexidade de uma função computável é conhecido como problema de função. الدوال الحسابية (بالإنجليزية: Computable function)‏ هي المواد الأساسية في دراسة النظرية الحسابية. الدوال الحسابية هي التماثلية الرسمية للفكرة البديهية للخوارزمية.. وهي تستخدم لمناقشة الحسابية دون الإشارة إلى أي نموذج ملموس من الحساب مثل آلات تورنغ أو آلات التسجيل. ورغم ذلك فإن أي تعريف يجب أن يكون له مرجعية لبعض النماذج المحددة من الحساب ولكن كل التعريفات الصحيحة تحقق نفس الدرجة من الوظائف. نماذج معينة من الحاسوبية التي تؤدي إلى مجموعة من الوظائف الحسابية هي دوال تورنغ الحسابية ودوال المايكرو المتكررة.قبل التعريف الدقيق للدالة الحسابية، غالباً ما كان يستخدم علماء الرياضيات المصطلح غير الرسمي محسوب بشكل فعّال. لقد أصبح هذا المصطلح منذ ذلك الحين معرّف بالدوال الحسابية. لاحظ أن الحاسوبية الفعّآلة لهذه الدوال لا تدل على أنه يمكن حسابهم بطريقة فعّآلة (بمعنى: يتم حسابهم في قدر معقول من الوقت). في الحقيقة، بالنسبة لبعض الدوال المحسوبة بشكل فعّال فهي قد تظهر أن أي خوارزمية تقوم بحسابهم سوف لن تكون فعّآلة في إدراك أن الوقت المنصرم من الخوارزمية يزيد باطراد (أو حتى باطراد مضاعف) مع مدة المدخلات. مجالات الحاسوبية العملية والتعقيد الحسابي تدرس الدوال التي قد تكون محسوبة بشكل فعّال. طبقاً لفرضية تورنغ-الكنيسة، فإن الدوال الحسابية هم بالضبط الدوال التي من الممكن أن يتم حسابها باستخدام أداة حساب ميكانيكية بفرض وجود كمية غير محدودة من الوقت ومساحة التخزين. بالمقابل، وتنص هذه الفرضية على أن أي دالة التي لها خوارزمية يمكن حسابها. لاحظ أن الخوارزمية في هذا المعنى تُفهم على أنها سلسلة متعاقبه من الخطوات التي يمكن لشخص لديه وقت غير محدود وإمداد غير منتهي من الأقلام والأوراق أن يتبعها.يمكن استخدام بديهية بلام لتعريف النظرية المجردة للتعقيد الحاسوبي على مجموعة من الدوال حسابية. في نظرية التعقيد الحاسوبي، مشكلة تحديد تعقيد الدالة المحسوبة يعرف بمشكلة الدالة. Funkcje obliczalne – podstawowy obiekt badań teorii obliczalności. Zbiór funkcji obliczalnych jest równoważny zbiorowi funkcji obliczalnych w sensie Turinga oraz funkcji częściowo rekurencyjnych. Funkcje obliczalne stanowią analogon intuicyjnego pojęcia algorytmu. Tego pojęcia używa się do dyskusji obliczalności bez odniesienia do określonego modelu obliczalności takiego jak maszyna Turinga lub . Jednak ich definicja musi mieć odniesienie do określonego modelu obliczalności. Zanim wprowadzono precyzyjną definicję funkcji obliczalnych, matematycy używali nieformalnego terminu „funkcji efektywnych”. Od tego czasu to określenie zaczęto utożsamiać z funkcjami obliczalnymi. Dokładniej można dla niektórych funkcji efektywnych wykazać, że każdy algorytm je obliczający będzie niewydajny w takim sensie, że każdy taki algorytm będzie potrzebował czasu rosnącego wykładniczo w zależności od długości wprowadzanych doń danych. Teoria obliczalności i teoria złożoności zajmują się zagadnieniami obliczalności oraz złożoności obliczeń funkcji obliczalnych wydajnie. Zgodnie z hipotezą Churcha i Turinga, funkcjami obliczalnymi są dokładnie te funkcje, które można obliczyć, używając urządzenia maszynowego, mając nieskończenie wiele czasu oraz przestrzeni pamięciowej. Równoważnie twierdzenie to oznacza, że każda funkcja dająca się wyrazić przez algorytm jest obliczalna. Aksjomaty Bluma dają nam abstrakcyjną definicję teorii złożoności na zbiorze funkcji obliczalnych. W teorii złożoności obliczeń problem określenia złożoności obliczalności jest znany jako zagadnienie funkcji. Υπολογίσιμες συναρτήσεις είναι τα βασικά αντικείμενα μελέτης στη θεωρία υπολογισιμότητας. Υπολογίσιμες συναρτήσεις είναι η τυποποιημένη αναλογική της διαισθητικής ιδέας του αλγορίθμου, με την έννοια ότι μια συνάρτηση είναι υπολογίσιμη αν υπάρχει ένας αλγόριθμος που μπορεί να κάνει τη δουλειά της συνάρτησης, δηλαδή με δεδομένο εισόδου το πεδίο ορισμού της συνάρτησης να μπορεί να επιστρέψει το αντίστοιχο της παραγωγής. Υπολογίσιμες συναρτήσεις χρησιμοποιούνται για να συζητήσουν υπολογισιμότητα, χωρίς να αναφέρονται σε κανένα συγκεκριμένο μοντέλο υπολογισμού όπως παραδείγματος χάρη οι μηχανές Τούρινγκ ή οι . Κάθε ορισμός, ωστόσο, πρέπει να κάνει αναφορά σε κάποιο συγκεκριμένο μοντέλο υπολογισμού αλλά ισχύουν οι ορισμοί της απόδοσης της ίδιας κατηγορίας των συναρτήσεων.Συγκεκριμένα μοντέλα υπολογισιμότητας που προκαλούν το σύνολο των υπολογίσιμων συναρτήσεων είναι οι Τούρινγκ-υπολογίσιμες συναρτήσεις και οι μ-αναδρομικές συναρτήσεις. Πριν τον ακριβή ορισμό της υπολογίσιμης συνάρτησης, οι μαθηματικοί συχνά χρησιμοποιούσαν τον άτυπο όρο αποτελεσματικά υπολογίσιμη. Ο όρος αυτός έχει από τότε να ταυτιστεί με τις υπολογίσιμες συναρτήσεις. Σημειώστε ότι η αποτελεσματική υπολογισιμότητα από αυτές τις συναρτήσεις δεν σημαίνει ότι μπορούν να είναι αποτελεσματικά υπολογίσιμες (δηλαδή υπολογίζεται σε εύλογο χρονικό διάστημα). Στην πραγματικότητα, για κάποιες αποτελεσματικά υπολογίσιμες συναρτήσεις μπορεί να αποδειχθεί ότι κάθε αλγόριθμος που τις υπολογίζει θα είναι πολύ αναποτελεσματικός, με την έννοια ότι ο χρόνος εκτέλεσης του αλγορίθμου αυξάνεται εκθετικά (ή ακόμα και ) με το μήκος της εισόδου. Τα πεδία της εφικτής υπολογισιμότητας και υπολογιστικής πολυπλοκότητας μελετούν συναρτήσεις που μπορούν να υπολογιστούν αποτελεσματικά. Σύμφωνα με την Τούρινγκ διατριβή, υπολογίσιμες συναρτήσεις είναι ακριβώς εκείνες οι συναρτήσεις που μπορούν να υπολογιστούν χρησιμοποιώντας μια συσκευή μηχανικού υπολογισμού με δεδομένο απεριόριστο ποσό χρόνου και χώρου αποθήκευσης. Αντίστοιχα, η διατριβή αυτή ορίζει ότι κάθε συνάρτηση που έχει έναν αλγόριθμο είναι υπολογίσιμη και αντίστροφα. Σημειώστε ότι ένας αλγόριθμος με αυτή την έννοια είναι κατανοητό να είναι μια ακολουθία από βήματα, ένα άτομο με απεριόριστο χρόνο και μια άπειρη προμήθεια από στυλό και χαρτί θα μπορούσε να συμβαδίσει. Τα αξιώματα Μπλουμ μπορούν να χρησιμοποιηθούν για να ορίσουμε μια αφηρημένη θεωρία υπολογιστικής πολυπλοκότητας για το σύνολο των υπολογίσιμων συναρτήσεων. Στην θεωρία υπολογιστικής πολυπλοκότητας, το πρόβλημα προσδιορισμού της πολυπλοκότητας μίας υπολογίσιμης συνάρτηση είναι γνωστό ως . 在可计算性理论中，可计算函数（computable function）或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确。使用可计算函数来讨论可计算性而不提及任何具体的计算模型，如图灵机或寄存器机。但是它们的定义必须提及某种特殊的计算模型。在可计算函数的精确定义之前，数学家经常使用非正式术语可有效计算的。这个术语因此可以被认同为可计算函数。尽管这些函数被叫做有效的，它们可能极其困难。和计算复杂性研究可有效计算的函数。依据邱奇-图灵论题，可计算函数精确的是使用给出无限数量的时间和存储空间的机器计算设备来计算的函数。等价的说，这个论题声称有算法的任何函数都是可计算的。可以使用布盧姆公理来在可计算函数的集合上定义抽象计算复杂性理论。在计算复杂性理论中，确定一个可计算函数的复杂性的问题叫做功能性问题。 Les funcions computables són l'objecte bàsic d'estudi de la teoria de la computabilitat i consisteixen en les funcions que poden ser calculades per una màquina de Turing. Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Any definition, however, must make reference to some specific model of computation but all valid definitions yield the same class of functions.Particular models of computability that give rise to the set of computable functions are the Turing-computable functions and the general recursive functions. Before the precise definition of computable function, mathematicians often used the informal term effectively calculable. This term has since come to be identified with the computable functions. Note that the effective computability of these functions does not imply that they can be efficiently computed (i.e. computed within a reasonable amount of time). In fact, for some effectively calculable functions it can be shown that any algorithm that computes them will be very inefficient in the sense that the running time of the algorithm increases exponentially (or even superexponentially) with the length of the input. The fields of feasible computability and computational complexity study functions that can be computed efficiently. According to the Church–Turing thesis, computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space. Equivalently, this thesis states that a function is computable if and only if it has an algorithm. Note that an algorithm in this sense is understood to be a sequence of steps a person with unlimited time and an unlimited supply of pen and paper could follow. The Blum axioms can be used to define an abstract computational complexity theory on the set of computable functions. In computational complexity theory, the problem of determining the complexity of a computable function is known as a function problem. Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y son, específicamente, las funciones que pueden ser calculadas por una máquina de Turing. Le funzioni calcolabili sono il principale oggetto di studio della teoria della calcolabilità. Le funzioni calcolabili sono l'analogo formale della nozione intuitiva di algoritmo, nel senso che una funzione è calcolabile se esiste un algoritmo che può svolgere il compito della funzione stessa, cioè se dato un input del dominio della funzione, questa è in grado di restituire il corrispondente output. Secondo la (non ancora dimostrata) tesi di Church-Turing, le funzioni calcolabili corrispondono alle funzioni ricorsive, e quindi a tutti i modelli di calcolo equivalenti. 계산 가능한 함수(computable function)는 그 함수의 결과값을 특정한 계산 방식을 따라 유한 시간 안에 얻어낼 수 있는 함수를 의미한다. 계산 가능한 함수는 알고리즘의 개념을 함수로 표현한 것으로 볼 수 있는데, 이때 함수는 특정한 알고리즘으로 정의되고, 해당 알고리즘을 계산하는 것으로 함수의 값을 얻는다. 계산 가능한 함수의 구체적인 정의는 계산 모델에 따라 결정되는데, 다음의 계산 모델은 모두 동일한 계산 가능성을 가지며, 따라서 이를 기반으로 정의하는 계산 가능한 함수 역시 동일한 의미를 가진다. * 튜링 기계 * μ-재귀 함수 * 람다 대수 Обч́ислювана фу́нкція (англ. computable function) — основний об'єкт вивчення теорії обчислень. Обчислюваною функцією називають таку функцію, результат якої може бути отримано за допомогою деякого ефективного процесу. Це поняття дозволяє при формулюванні алгоритмів не спиратися на конкретні реалізації обчислювальних машин, а зосередитися на загальних алгоритмічних принципах. Існують різні формальні способи конкретизувати, як саме має бути реалізовано цей процес. Це може бути зроблено за допомогою наступних систем: * машина Тьюрінга * * Лямбда-числення * Машина Поста * Хоча всі ці моделі працюють по-різному, множина задач, які може бути розв'язано за їх допомогою — одна й та сама. Це пов'язано з тим, що будь-яку з цих машин можна змоделювати за допомогою будь-якої з інших. Алгоритм, що обраховує значення функції, в загальному виді має такі властивості: * Він має скінченну довжину * Якщо є визначеним для деякого , то алгоритм, отримавши на вхід , зупиниться, і видасть * Якщо не визначене для даного , то алгоритм, отримавши на вхід , ніколи не зупиниться. Часто множину обмежують її підмножиною {0, 1}. Таким чином, фактично, алгоритм працює з ланцюжком бітів. 計算可能関数（けいさんかのうかんすう、英: Computable function）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。 Вычислимые функции — это множество функций вида, которые могут быть реализованы на машине Тьюринга. Задачу вычисления функции называют алгоритмически разрешимой или алгоритмически неразрешимой, в зависимости от того, возможен ли алгоритм, вычисляющий эту функцию. В качестве множества обычно рассматривается множество — множество слов в двоичном алфавите , с оговоркой, что результатом вычисления может быть не только слово, но и специальное значение «неопределённость», соответствующее случаю, когда алгоритм «зависает». Таким образом, можно дать следующее определение : где , а — специальный элемент, означающий неопределённость. Роль множества может играть множество натуральных чисел, к которому добавлен элемент , и тогда вычислимые функции — это некоторое подмножество натуральнозначных функций натурального аргумента.Удобно считать, что в качестве могут выступать различные счётные множества — множество натуральных чисел, множество рациональных чисел, множество слов в каком-либо конечном алфавите и др. Важно, чтобы существовал некоторый формальный язык в конечном алфавите описания элементов множества и чтобы задача распознавания корректных описаний была вычислима.Например, для описания натуральных чисел удобно использовать двоичную систему счисления — язык описания натуральных чисел в алфавите . В данном определении вместо исполнителя машин Тьюринга можно взять один из Тьюринг-полных исполнителей.Грубо говоря, «эталонным исполнителем» может быть некоторый абстрактный компьютер, подобный используемым персональным компьютерам, но с потенциально бесконечной памятью и особенностями архитектуры, позволяющими использовать эту бесконечную память. Важно отметить, что множество программ для этого исполнителя (например, множество машин Тьюринга при фиксированном алфавите входных и выходных данных) счётно. Поэтому множество вычислимых функций не более чем счётно, в то время как множество функций вида несчётно, если счётно.Значит, есть невычислимые функции, причём мощность их множества больше, чем мощность множества вычислимых функций.Примером невычислимой функции (алгоритмически неразрешимой проблемы) может быть функция определения остановки — функция, которая получает на вход описание некоторой машины Тьюринга и вход для неё, а возвращает 0 или 1 в зависимости от того, остановится данная машина на данном входе или нет. Ещё одним примером невычислимой функции является колмогоровская сложность.
gold:hypernym: dbr:Objects
prov:wasDerivedFrom: wikipedia-en:Computable_function?oldid=1122713957&ns=0
dbo:wikiPageLength: 24417
foaf:isPrimaryTopicOf: wikipedia-en:Computable_function

Subject Item: dbr:Computer
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Computer_algebra
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Constructivism_(philosophy_of_mathematics)
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Mathematical_logic
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Numbering_scheme
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Μ_operator
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Scott–Curry_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Church–Turing_thesis
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Enumeration
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Free_variables_and_bound_variables
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Function_(mathematics)
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:General_recursive_function
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Glossary_of_areas_of_mathematics
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Glossary_of_computer_science
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Bourbaki–Witt_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Constructive_set_theory
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Creative_and_productive_sets
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Thoralf_Skolem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Orchestrated_objective_reduction
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Ordinal_analysis
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Ordinal_notation
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Arithmetical_hierarchy
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Arithmetical_set
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Blum's_speedup_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Blum_axioms
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Stanisław_Mazur
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Stephen_Cole_Kleene
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Structured_programming
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Subgroup_distortion
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Complete_numbering
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Compression_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Computable_analysis
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Computable_isomorphism
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Computable_number
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Computable_set
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Computably_enumerable_set
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Function_type
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Hardware_acceleration
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:P′′
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Specker_sequence
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Successor_function
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Markov's_principle
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Buchholz_hydra
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Busy_beaver
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Time_complexity
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Type_system
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Gap_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Langton's_loops
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Large_countable_ordinal
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Lazy_linear_hybrid_automaton
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Learning_automaton
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Logic_of_Computable_Functions
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Robinson_arithmetic
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Truth-table_reduction
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Recursively_enumerable_language
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Test_vector
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Algorithm_characterizations
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:ELEMENTARY
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Equivalence_partitioning
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Brouwer–Heyting–Kolmogorov_interpretation
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Non-computable_function
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: dbr:Noncomputable_function
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: dbr:Church's_thesis_(constructive_mathematics)
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Diagonal_lemma
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Fast-growing_hierarchy
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Goodstein's_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Graham's_number
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:History_of_randomness
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:History_of_the_Church–Turing_thesis
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Kolmogorov_complexity
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:RE_(complexity)
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:R_(complexity)
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Recursive_function
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Reduction_(complexity)
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Gödel's_incompleteness_theorems
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Halting_problem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Hans_Hermes
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Back-and-forth_method
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Hyperarithmetical_theory
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Hypercomputation
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Todd–Coxeter_algorithm
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Subcountability
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Smn_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:AI-complete
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Ackermann_function
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:LOOP_(programming_language)
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Lambda_calculus
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:BlooP_and_FlooP
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Effective_method
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Effective_results_in_number_theory
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Higher-order_logic
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Realizability
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Philosophy_of_mathematics
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Implicit_graph
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Incomputable
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: dbr:Kurt_Gödel
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Ordinal_number
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Chaitin's_constant
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:C_(disambiguation)
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageDisambiguates: dbr:Computable_function

Subject Item: dbr:Word_problem_(mathematics)
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Klam_value
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Kleene's_O
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Kleene's_T_predicate
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Kleene's_recursion_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Kleene–Brouwer_order
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Markov_decision_process
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Mathematical_universe_hypothesis
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Turing_machine
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Undecidable_problem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Universal_Turing_machine
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Incomputable_function
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: dbr:Unifying_theories_in_mathematics
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Non-recursive_function
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Euclid–Mullin_sequence
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:List_of_types_of_functions
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Turing_jump
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Semicomputable_function
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Structured_program_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Turing_reduction
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:UTM_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Semi-membership
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: n26:_Proofs_from_the_Inside_Out
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Outline_of_logic
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:PA_degree
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Rice's_theorem
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Uncomputable_function
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: dbr:Turing_completeness
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Structural_complexity_theory
dbo:wikiPageWikiLink: dbr:Computable_function

Subject Item: dbr:Provably_total
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: dbr:Turing-computable
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: dbr:Turing_computable
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: dbr:Effectively_computable
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: dbr:Partial_computable_function
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: dbr:Computable_predicate
dbo:wikiPageWikiLink: dbr:Computable_function
dbo:wikiPageRedirects: dbr:Computable_function

Subject Item: wikipedia-en:Computable_function
foaf:primaryTopic: dbr:Computable_function