Computable function (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (ca) الدوال الحسابية (بالإنجليزية: Computable function) هي المواد الأساسية في دراسة النظرية الحسابية. الدوال الحسابية هي التماثلية الرسمية للفكرة البديهية للخوارزمية.. وهي تستخدم لمناقشة الحسابية دون الإشارة إلى أي نموذج ملموس من الحساب مثل آلات تورنغ أو آلات التسجيل. ورغم ذلك فإن أي تعريف يجب أن يكون له مرجعية لبعض النماذج المحددة من الحساب ولكن كل التعريفات الصحيحة تحقق نفس الدرجة من الوظائف. نماذج معينة من الحاسوبية التي تؤدي إلى مجموعة من الوظائف الحسابية هي دوال تورنغ الحسابية ودوال المايكرو المتكررة.قبل التعريف الدقيق للدالة الحسابية، غالباً ما كان يستخدم علماء الرياضيات المصطلح غير الرسمي محسوب بشكل فعّال. لقد أصبح هذا المصطلح منذ ذلك الحين معرّف بالدوال الحسابية. لاحظ أن الحاسوبية الفعّآلة لهذه الدوال لا تدل على أنه يمكن حسابهم بطريقة فعّآلة (بمعنى: يتم حسابهم في قدر معقول من الوقت). في الحقيقة، بالنسبة لبعض الدوال المحسوبة بشكل فعّال فهي قد تظهر أن أي خوارزمية تقوم بحسابهم سوف لن تكون فعّآلة في إدراك أن الوقت المنصرم من الخوارزمية يزيد باطراد (أو حتى باطراد مضاعف) مع مدة المدخلات. مجالات الحاسوبية العملية والتعقيد الحسابي تدرس الدوال التي قد تكون محسوبة بشكل فعّال. طبقاً لفرضية تورنغ-الكنيسة، فإن الدوال الحسابية هم بالضبط الدوال التي من الممكن أن يتم حسابها باستخدام أداة حساب ميكانيكية بفرض وجود كمية غير محدودة من الوقت ومساحة التخزين. بالمقابل، وتنص هذه الفرضية على أن أي دالة التي لها خوارزمية يمكن حسابها. لاحظ أن الخوارزمية في هذا المعنى تُفهم على أنها سلسلة متعاقبه من الخطوات التي يمكن لشخص لديه وقت غير محدود وإمداد غير منتهي من الأقلام والأوراق أن يتبعها.يمكن استخدام بديهية بلام لتعريف النظرية المجردة للتعقيد الحاسوبي على مجموعة من الدوال حسابية. في نظرية التعقيد الحاسوبي، مشكلة تحديد تعقيد الدالة المحسوبة يعرف بمشكلة الدالة. (ar) Υπολογίσιμες συναρτήσεις είναι τα βασικά αντικείμενα μελέτης στη θεωρία υπολογισιμότητας. Υπολογίσιμες συναρτήσεις είναι η τυποποιημένη αναλογική της διαισθητικής ιδέας του αλγορίθμου, με την έννοια ότι μια συνάρτηση είναι υπολογίσιμη αν υπάρχει ένας αλγόριθμος που μπορεί να κάνει τη δουλειά της συνάρτησης, δηλαδή με δεδομένο εισόδου το πεδίο ορισμού της συνάρτησης να μπορεί να επιστρέψει το αντίστοιχο της παραγωγής. Υπολογίσιμες συναρτήσεις χρησιμοποιούνται για να συζητήσουν υπολογισιμότητα, χωρίς να αναφέρονται σε κανένα συγκεκριμένο μοντέλο υπολογισμού όπως παραδείγματος χάρη οι μηχανές Τούρινγκ ή οι . Κάθε ορισμός, ωστόσο, πρέπει να κάνει αναφορά σε κάποιο συγκεκριμένο μοντέλο υπολογισμού αλλά ισχύουν οι ορισμοί της απόδοσης της ίδιας κατηγορίας των συναρτήσεων.Συγκεκριμένα μοντέλα υπολογισιμότητας που προκαλούν το σύνολο των υπολογίσιμων συναρτήσεων είναι οι Τούρινγκ-υπολογίσιμες συναρτήσεις και οι μ-αναδρομικές συναρτήσεις. Πριν τον ακριβή ορισμό της υπολογίσιμης συνάρτησης, οι μαθηματικοί συχνά χρησιμοποιούσαν τον άτυπο όρο αποτελεσματικά υπολογίσιμη. Ο όρος αυτός έχει από τότε να ταυτιστεί με τις υπολογίσιμες συναρτήσεις. Σημειώστε ότι η αποτελεσματική υπολογισιμότητα από αυτές τις συναρτήσεις δεν σημαίνει ότι μπορούν να είναι αποτελεσματικά υπολογίσιμες (δηλαδή υπολογίζεται σε εύλογο χρονικό διάστημα). Στην πραγματικότητα, για κάποιες αποτελεσματικά υπολογίσιμες συναρτήσεις μπορεί να αποδειχθεί ότι κάθε αλγόριθμος που τις υπολογίζει θα είναι πολύ αναποτελεσματικός, με την έννοια ότι ο χρόνος εκτέλεσης του αλγορίθμου αυξάνεται εκθετικά (ή ακόμα και ) με το μήκος της εισόδου. Τα πεδία της εφικτής υπολογισιμότητας και υπολογιστικής πολυπλοκότητας μελετούν συναρτήσεις που μπορούν να υπολογιστούν αποτελεσματικά. Σύμφωνα με την Τούρινγκ διατριβή, υπολογίσιμες συναρτήσεις είναι ακριβώς εκείνες οι συναρτήσεις που μπορούν να υπολογιστούν χρησιμοποιώντας μια συσκευή μηχανικού υπολογισμού με δεδομένο απεριόριστο ποσό χρόνου και χώρου αποθήκευσης. Αντίστοιχα, η διατριβή αυτή ορίζει ότι κάθε συνάρτηση που έχει έναν αλγόριθμο είναι υπολογίσιμη και αντίστροφα. Σημειώστε ότι ένας αλγόριθμος με αυτή την έννοια είναι κατανοητό να είναι μια ακολουθία από βήματα, ένα άτομο με απεριόριστο χρόνο και μια άπειρη προμήθεια από στυλό και χαρτί θα μπορούσε να συμβαδίσει. Τα αξιώματα Μπλουμ μπορούν να χρησιμοποιηθούν για να ορίσουμε μια αφηρημένη θεωρία υπολογιστικής πολυπλοκότητας για το σύνολο των υπολογίσιμων συναρτήσεων. Στην θεωρία υπολογιστικής πολυπλοκότητας, το πρόβλημα προσδιορισμού της πολυπλοκότητας μίας υπολογίσιμης συνάρτηση είναι γνωστό ως . (el) 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. (en) 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. (es) 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. (it) 計算可能関数（けいさんかのうかんすう、英: Computable function）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。 計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。 チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。 ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。 (ja) 계산 가능한 함수(computable function)는 그 함수의 결과값을 특정한 계산 방식을 따라 유한 시간 안에 얻어낼 수 있는 함수를 의미한다. 계산 가능한 함수는 알고리즘의 개념을 함수로 표현한 것으로 볼 수 있는데, 이때 함수는 특정한 알고리즘으로 정의되고, 해당 알고리즘을 계산하는 것으로 함수의 값을 얻는다. 계산 가능한 함수의 구체적인 정의는 계산 모델에 따라 결정되는데, 다음의 계산 모델은 모두 동일한 계산 가능성을 가지며, 따라서 이를 기반으로 정의하는 계산 가능한 함수 역시 동일한 의미를 가진다. * 튜링 기계 * μ-재귀 함수 * 람다 대수 (ko) 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. (pl) 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. (pt) Вычислимые функции — это множество функций вида, которые могут быть реализованы на машине Тьюринга. Задачу вычисления функции называют алгоритмически разрешимой или алгоритмически неразрешимой, в зависимости от того, возможен ли алгоритм, вычисляющий эту функцию. В качестве множества обычно рассматривается множество — множество слов в двоичном алфавите , с оговоркой, что результатом вычисления может быть не только слово, но и специальное значение «неопределённость», соответствующее случаю, когда алгоритм «зависает». Таким образом, можно дать следующее определение : где , а — специальный элемент, означающий неопределённость. Роль множества может играть множество натуральных чисел, к которому добавлен элемент , и тогда вычислимые функции — это некоторое подмножество натуральнозначных функций натурального аргумента.Удобно считать, что в качестве могут выступать различные счётные множества — множество натуральных чисел, множество рациональных чисел, множество слов в каком-либо конечном алфавите и др. Важно, чтобы существовал некоторый формальный язык в конечном алфавите описания элементов множества и чтобы задача распознавания корректных описаний была вычислима.Например, для описания натуральных чисел удобно использовать двоичную систему счисления — язык описания натуральных чисел в алфавите . В данном определении вместо исполнителя машин Тьюринга можно взять один из Тьюринг-полных исполнителей.Грубо говоря, «эталонным исполнителем» может быть некоторый абстрактный компьютер, подобный используемым персональным компьютерам, но с потенциально бесконечной памятью и особенностями архитектуры, позволяющими использовать эту бесконечную память. Важно отметить, что множество программ для этого исполнителя (например, множество машин Тьюринга при фиксированном алфавите входных и выходных данных) счётно. Поэтому множество вычислимых функций не более чем счётно, в то время как множество функций вида несчётно, если счётно.Значит, есть невычислимые функции, причём мощность их множества больше, чем мощность множества вычислимых функций.Примером невычислимой функции (алгоритмически неразрешимой проблемы) может быть функция определения остановки — функция, которая получает на вход описание некоторой машины Тьюринга и вход для неё, а возвращает 0 или 1 в зависимости от того, остановится данная машина на данном входе или нет. Ещё одним примером невычислимой функции является колмогоровская сложность. (ru) Обч́ислювана фу́нкція (англ. computable function) — основний об'єкт вивчення теорії обчислень. Обчислюваною функцією називають таку функцію, результат якої може бути отримано за допомогою деякого ефективного процесу. Це поняття дозволяє при формулюванні алгоритмів не спиратися на конкретні реалізації обчислювальних машин, а зосередитися на загальних алгоритмічних принципах. Існують різні формальні способи конкретизувати, як саме має бути реалізовано цей процес. Це може бути зроблено за допомогою наступних систем: * машина Тьюрінга * * Лямбда-числення * Машина Поста * Хоча всі ці моделі працюють по-різному, множина задач, які може бути розв'язано за їх допомогою — одна й та сама. Це пов'язано з тим, що будь-яку з цих машин можна змоделювати за допомогою будь-якої з інших. Алгоритм, що обраховує значення функції, в загальному виді має такі властивості: * Він має скінченну довжину * Якщо є визначеним для деякого , то алгоритм, отримавши на вхід , зупиниться, і видасть * Якщо не визначене для даного , то алгоритм, отримавши на вхід , ніколи не зупиниться. Часто множину обмежують її підмножиною {0, 1}. Таким чином, фактично, алгоритм працює з ланцюжком бітів. (uk) 在可计算性理论中，可计算函数（computable function）或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确。使用可计算函数来讨论可计算性而不提及任何具体的计算模型，如图灵机或寄存器机。但是它们的定义必须提及某种特殊的计算模型。 在可计算函数的精确定义之前，数学家经常使用非正式术语可有效计算的。这个术语因此可以被认同为可计算函数。尽管这些函数被叫做有效的，它们可能极其困难。和计算复杂性研究可有效计算的函数。 依据邱奇-图灵论题，可计算函数精确的是使用给出无限数量的时间和存储空间的机器计算设备来计算的函数。等价的说，这个论题声称有算法的任何函数都是可计算的。 可以使用布盧姆公理来在可计算函数的集合上定义抽象计算复杂性理论。在计算复杂性理论中，确定一个可计算函数的复杂性的问题叫做功能性问题。 (zh) |
| dbo:wikiPageExternalLink | https://academic.oup.com/plms/issue/s2-42/1 |
| dbo:wikiPageID | 1139338 (xsd:integer) |
| dbo:wikiPageLength | 24417 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1122713957 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Primitive_recursive_function dbr:Entscheidungsproblem dbr:Bézout_coefficient dbr:David_Hilbert dbr:Algorithm dbr:Arg_max dbr:Peano_arithmetic dbr:Unary_operation dbr:Μ-recursive_function dbr:Compiler dbr:Computability_theory_(computer_science) dbr:Constant_function dbr:Prime_factor dbr:Μ_operator dbr:Church–Turing_thesis dbr:Function_composition dbr:General_recursive_function dbr:Greatest_common_divisor dbr:Multiplication dbr:Arithmetical_hierarchy dbr:Arity dbr:Blum_axioms dbr:Closure_(mathematics) dbr:Computable_number dbr:Computable_ordinal dbr:Computational_complexity_theory dbr:Function_problem dbr:Partial_function dbr:Tag_system dbr:Theory_of_computation dbr:Mathematician dbr:Busy_beaver dbr:Tuple dbr:Domain_of_a_function dbr:Addition dbr:Finitary_relation dbr:First-order_logic dbr:Diagonal_lemma dbr:Formal_language dbr:Kolmogorov_complexity dbr:Recursive_definition dbr:Recursively_enumerable dbr:Halting_problem dbr:Herbert_Enderton dbr:Tetration dbr:Hyperarithmetical_theory dbr:Hypercomputation dbr:Ackermann_function dbc:Computability_theory dbc:Theory_of_computation dbr:Lambda_calculus dbr:Effective_method dbr:Register_machine dbr:Post–Turing_machine dbr:If_and_only_if dbr:Natural_number dbr:Natural_numbers dbr:Chaitin's_constant dbr:Set_(mathematics) dbr:Model_of_computation dbr:Turing_machine dbr:Soundness dbr:Exponential_growth dbr:Turing_jump dbr:Semicomputable_function dbr:Finitary dbr:Super-recursive_algorithm dbr:Injective dbr:Turing_degree dbr:Feasible_computability dbr:Turing-computable_function dbr:Oracle_(computability) dbr:Countability dbr:Effectively_calculable dbr:Relative_computability dbr:A._Turing dbr:Recursion_theory dbr:Gödel_number |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Citation_needed dbt:Main dbt:Math dbt:Mvar dbt:Ordered_list dbt:Pi dbt:Reflist dbt:See_also dbt:Short_description dbt:Mset dbt:ComplexityClasses dbt:Mathematical_logic |
| dct:subject | dbc:Computability_theory dbc:Theory_of_computation |
| gold:hypernym | dbr:Objects |
| rdf:type | owl:Thing yago:Abstraction100002137 yago:Function113783816 yago:MathematicalRelation113783581 yago:Relation100031921 yago:WikicatFunctionsAndMappings dbo:Planet |
| rdfs:comment | 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. (ca) 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. (es) 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. (it) 計算可能関数（けいさんかのうかんすう、英: Computable function）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。 計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。 チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。 ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。 (ja) 계산 가능한 함수(computable function)는 그 함수의 결과값을 특정한 계산 방식을 따라 유한 시간 안에 얻어낼 수 있는 함수를 의미한다. 계산 가능한 함수는 알고리즘의 개념을 함수로 표현한 것으로 볼 수 있는데, 이때 함수는 특정한 알고리즘으로 정의되고, 해당 알고리즘을 계산하는 것으로 함수의 값을 얻는다. 계산 가능한 함수의 구체적인 정의는 계산 모델에 따라 결정되는데, 다음의 계산 모델은 모두 동일한 계산 가능성을 가지며, 따라서 이를 기반으로 정의하는 계산 가능한 함수 역시 동일한 의미를 가진다. * 튜링 기계 * μ-재귀 함수 * 람다 대수 (ko) 在可计算性理论中，可计算函数（computable function）或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确。使用可计算函数来讨论可计算性而不提及任何具体的计算模型，如图灵机或寄存器机。但是它们的定义必须提及某种特殊的计算模型。 在可计算函数的精确定义之前，数学家经常使用非正式术语可有效计算的。这个术语因此可以被认同为可计算函数。尽管这些函数被叫做有效的，它们可能极其困难。和计算复杂性研究可有效计算的函数。 依据邱奇-图灵论题，可计算函数精确的是使用给出无限数量的时间和存储空间的机器计算设备来计算的函数。等价的说，这个论题声称有算法的任何函数都是可计算的。 可以使用布盧姆公理来在可计算函数的集合上定义抽象计算复杂性理论。在计算复杂性理论中，确定一个可计算函数的复杂性的问题叫做功能性问题。 (zh) الدوال الحسابية (بالإنجليزية: Computable function) هي المواد الأساسية في دراسة النظرية الحسابية. الدوال الحسابية هي التماثلية الرسمية للفكرة البديهية للخوارزمية.. وهي تستخدم لمناقشة الحسابية دون الإشارة إلى أي نموذج ملموس من الحساب مثل آلات تورنغ أو آلات التسجيل. ورغم ذلك فإن أي تعريف يجب أن يكون له مرجعية لبعض النماذج المحددة من الحساب ولكن كل التعريفات الصحيحة تحقق نفس الدرجة من الوظائف. نماذج معينة من الحاسوبية التي تؤدي إلى مجموعة من الوظائف الحسابية هي دوال تورنغ الحسابية ودوال المايكرو المتكررة.قبل التعريف الدقيق للدالة الحسابية، غالباً ما كان يستخدم علماء الرياضيات المصطلح غير الرسمي محسوب بشكل فعّال. لقد أصبح هذا المصطلح منذ ذلك الحين معرّف بالدوال الحسابية. لاحظ أن الحاسوبية الفعّآلة لهذه الدوال لا تدل على أنه يمكن حسابهم بطريقة فعّآلة (بمعنى: يتم حسابهم في قدر معقول من الوقت). ف (ar) Υπολογίσιμες συναρτήσεις είναι τα βασικά αντικείμενα μελέτης στη θεωρία υπολογισιμότητας. Υπολογίσιμες συναρτήσεις είναι η τυποποιημένη αναλογική της διαισθητικής ιδέας του αλγορίθμου, με την έννοια ότι μια συνάρτηση είναι υπολογίσιμη αν υπάρχει ένας αλγόριθμος που μπορεί να κάνει τη δουλειά της συνάρτησης, δηλαδή με δεδομένο εισόδου το πεδίο ορισμού της συνάρτησης να μπορεί να επιστρέψει το αντίστοιχο της παραγωγής. Υπολογίσιμες συναρτήσεις χρησιμοποιούνται για να συζητήσουν υπολογισιμότητα, χωρίς να αναφέρονται σε κανένα συγκεκριμένο μοντέλο υπολογισμού όπως παραδείγματος χάρη οι μηχανές Τούρινγκ ή οι . Κάθε ορισμός, ωστόσο, πρέπει να κάνει αναφορά σε κάποιο συγκεκριμένο μοντέλο υπολογισμού αλλά ισχύουν οι ορισμοί της απόδοσης της ίδιας κατηγορίας των συναρτήσεων.Συγκεκριμένα μοντέλα υπο (el) 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 (en) 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. (pl) 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. (pt) Вычислимые функции — это множество функций вида, которые могут быть реализованы на машине Тьюринга. Задачу вычисления функции называют алгоритмически разрешимой или алгоритмически неразрешимой, в зависимости от того, возможен ли алгоритм, вычисляющий эту функцию. В качестве множества обычно рассматривается множество — множество слов в двоичном алфавите , с оговоркой, что результатом вычисления может быть не только слово, но и специальное значение «неопределённость», соответствующее случаю, когда алгоритм «зависает». Таким образом, можно дать следующее определение : (ru) Обч́ислювана фу́нкція (англ. computable function) — основний об'єкт вивчення теорії обчислень. Обчислюваною функцією називають таку функцію, результат якої може бути отримано за допомогою деякого ефективного процесу. Це поняття дозволяє при формулюванні алгоритмів не спиратися на конкретні реалізації обчислювальних машин, а зосередитися на загальних алгоритмічних принципах. Існують різні формальні способи конкретизувати, як саме має бути реалізовано цей процес. Це може бути зроблено за допомогою наступних систем: * машина Тьюрінга * * Лямбда-числення * Машина Поста * (uk) |
| rdfs:label | دالة قابلة للحساب (ar) Funció computable (ca) Υπολογίσιμη συνάρτηση (el) Función computable (es) Computable function (en) Funzione calcolabile (it) Fonction calculable (fr) 計算可能関数 (ja) 계산 가능 함수 (ko) Funkcja obliczalna (pl) Função computável (pt) Вычислимая функция (ru) Обчислювана функція (uk) 可计算函数 (zh) |
| rdfs:seeAlso | dbr:Total_Turing_machine |
| owl:sameAs | freebase:Computable function yago-res:Computable function wikidata:Computable function dbpedia-ar:Computable function http://ast.dbpedia.org/resource/Función_computable dbpedia-ca:Computable function dbpedia-el:Computable function dbpedia-es:Computable function dbpedia-fr:Computable function dbpedia-gl:Computable function dbpedia-he:Computable function dbpedia-it:Computable function dbpedia-ja:Computable function dbpedia-ko:Computable function dbpedia-pl:Computable function dbpedia-pt:Computable function dbpedia-ru:Computable function dbpedia-simple:Computable function dbpedia-sr:Computable function dbpedia-uk:Computable function dbpedia-vi:Computable function dbpedia-zh:Computable function https://global.dbpedia.org/id/CbmG |
| prov:wasDerivedFrom | wikipedia-en:Computable_function?oldid=1122713957&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Computable_function |
| is dbo:wikiPageDisambiguates of | dbr:C_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Total_computable_function dbr:Uncomputable dbr:Non-computable_function dbr:Noncomputable_function dbr:Incomputable dbr:Incomputable_function dbr:Uncomputable_function dbr:Provably_total dbr:Turing-computable dbr:Turing_computable dbr:Effectively_computable dbr:Partial_computable_function dbr:Computable_predicate |
| is dbo:wikiPageWikiLink of | dbr:Primitive_recursive_function dbr:Entscheidungsproblem dbr:List_of_forcing_notions dbr:Myhill_isomorphism_theorem dbr:Paris–Harrington_theorem dbr:Total_computable_function dbr:Brainfuck dbr:Algorithmic_probability dbr:History_of_the_function_concept dbr:Hyperoperation dbr:Peano_axioms dbr:Reverse_mathematics dbr:Reversible_cellular_automaton dbr:Uncomputable dbr:Decidability_(logic) dbr:Index_set_(computability) dbr:List_of_important_publications_in_mathematics dbr:List_of_inventions_and_discoveries_by_women dbr:List_of_mathematical_functions dbr:List_of_mathematical_logic_topics dbr:Numbering_(computability_theory) dbr:Penrose–Lucas_argument dbr:Space_hierarchy_theorem dbr:0 dbr:Computability_theory dbr:Computer dbr:Computer_algebra dbr:Constructivism_(philosophy_of_mathematics) dbr:Mathematical_logic dbr:Numbering_scheme dbr:Μ_operator dbr:Scott–Curry_theorem dbr:Church–Turing_thesis dbr:Enumeration dbr:Free_variables_and_bound_variables dbr:Function_(mathematics) dbr:General_recursive_function dbr:Glossary_of_areas_of_mathematics dbr:Glossary_of_computer_science dbr:Bourbaki–Witt_theorem dbr:Constructive_set_theory dbr:Creative_and_productive_sets dbr:Thoralf_Skolem dbr:Orchestrated_objective_reduction dbr:Ordinal_analysis dbr:Ordinal_notation dbr:Arithmetical_hierarchy dbr:Arithmetical_set dbr:Blum's_speedup_theorem dbr:Blum_axioms dbr:Stanisław_Mazur dbr:Stephen_Cole_Kleene dbr:Structured_programming dbr:Subgroup_distortion dbr:Complete_numbering dbr:Compression_theorem dbr:Computable_analysis dbr:Computable_isomorphism dbr:Computable_number dbr:Computable_set dbr:Computably_enumerable_set dbr:Function_type dbr:Hardware_acceleration dbr:P′′ dbr:Specker_sequence dbr:Successor_function dbr:Markov's_principle dbr:Buchholz_hydra dbr:Busy_beaver dbr:Time_complexity dbr:Type_system dbr:Gap_theorem dbr:Langton's_loops dbr:Large_countable_ordinal dbr:Lazy_linear_hybrid_automaton dbr:Learning_automaton dbr:Logic_of_Computable_Functions dbr:Robinson_arithmetic dbr:Truth-table_reduction dbr:Recursively_enumerable_language dbr:Test_vector dbr:Algorithm_characterizations dbr:ELEMENTARY dbr:Equivalence_partitioning dbr:Brouwer–Heyting–Kolmogorov_interpretation dbr:Non-computable_function dbr:Noncomputable_function dbr:Church's_thesis_(constructive_mathematics) dbr:Diagonal_lemma dbr:Fast-growing_hierarchy dbr:Goodstein's_theorem dbr:Graham's_number dbr:History_of_randomness dbr:History_of_the_Church–Turing_thesis dbr:Kolmogorov_complexity dbr:RE_(complexity) dbr:R_(complexity) dbr:Recursive_function dbr:Reduction_(complexity) dbr:Gödel's_incompleteness_theorems dbr:Halting_problem dbr:Hans_Hermes dbr:Back-and-forth_method dbr:Hyperarithmetical_theory dbr:Hypercomputation dbr:Todd–Coxeter_algorithm dbr:Subcountability dbr:Smn_theorem dbr:AI-complete dbr:Ackermann_function dbr:LOOP_(programming_language) dbr:Lambda_calculus dbr:BlooP_and_FlooP dbr:Effective_method dbr:Effective_results_in_number_theory dbr:Higher-order_logic dbr:Realizability dbr:Philosophy_of_mathematics dbr:Implicit_graph dbr:Incomputable dbr:Kurt_Gödel dbr:Ordinal_number dbr:Chaitin's_constant dbr:C_(disambiguation) dbr:Word_problem_(mathematics) dbr:Klam_value dbr:Kleene's_O dbr:Kleene's_T_predicate dbr:Kleene's_recursion_theorem dbr:Kleene–Brouwer_order dbr:Markov_decision_process dbr:Mathematical_universe_hypothesis dbr:Turing_machine dbr:Undecidable_problem dbr:Universal_Turing_machine dbr:Incomputable_function dbr:Unifying_theories_in_mathematics dbr:Non-recursive_function dbr:Euclid–Mullin_sequence dbr:List_of_types_of_functions dbr:Turing_jump dbr:Semicomputable_function dbr:Structured_program_theorem dbr:Turing_reduction dbr:UTM_theorem dbr:Semi-membership dbr:Reverse_Mathematics:_Proofs_from_the_Inside_Out dbr:Outline_of_logic dbr:PA_degree dbr:Rice's_theorem dbr:Uncomputable_function dbr:Turing_completeness dbr:Structural_complexity_theory dbr:Provably_total dbr:Turing-computable dbr:Turing_computable dbr:Effectively_computable dbr:Partial_computable_function dbr:Computable_predicate |
| is foaf:primaryTopic of | wikipedia-en:Computable_function |