Computability (original) (raw)
الحاسوبية هي القدرة على حل مشكلة ما بطريقة فعاله. وهي الموضوع الرئيسي لمجال نظرية الحاسوبية في المنطق الرياضي ونظرية الحساب في علوم الحاسوب. حاسوبية المشكلة ترتبط بشدة بوجود خوارزمية لحل المشكلة.إن أوسع نماذج الحاسوبية دراسةً هم آلة تورنغ ودوال المايكرو المتكررة وحسابات اللامدا، وجميعهم لهم قوى حسابية معادله. توجد أيضاً أشكال أخرى من الحاسوبية تتم دراستها: مفاهيم الحاسوبية الأضعف من آلات تورنغ تتم دراستهم في نظرية التشغيل الذاتي، بينما مفاهيم الحاسوبية الأقوى من آلات تورنغ تتم دراستهم في مجال الحساب الأعلى.
| Property | Value |
|---|---|
| dbo:abstract | الحاسوبية هي القدرة على حل مشكلة ما بطريقة فعاله. وهي الموضوع الرئيسي لمجال نظرية الحاسوبية في المنطق الرياضي ونظرية الحساب في علوم الحاسوب. حاسوبية المشكلة ترتبط بشدة بوجود خوارزمية لحل المشكلة.إن أوسع نماذج الحاسوبية دراسةً هم آلة تورنغ ودوال المايكرو المتكررة وحسابات اللامدا، وجميعهم لهم قوى حسابية معادله. توجد أيضاً أشكال أخرى من الحاسوبية تتم دراستها: مفاهيم الحاسوبية الأضعف من آلات تورنغ تتم دراستهم في نظرية التشغيل الذاتي، بينما مفاهيم الحاسوبية الأقوى من آلات تورنغ تتم دراستهم في مجال الحساب الأعلى. (ar) Eine mathematische Funktion ist berechenbar (auch effektiv berechenbar oder rekursiv), wenn für sie eine Berechnungsanweisung (Algorithmus) formuliert werden kann (Berechenbarkeitstheorie). Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe reagiert. Der Definitionsbereich der Funktion ist die Menge der Eingaben, für die der Algorithmus eine Ausgabe produziert. Wenn der Algorithmus nicht terminiert, dann ist die Eingabe kein Element der Definitionsmenge. Dem Algorithmusbegriff liegt ein Berechnungsmodell zugrunde. Verschiedene Berechnungsmodelle sind entwickelt worden, es hat sich aber herausgestellt, dass die stärksten davon zum Modell der Turingmaschine gleich stark (Turing-mächtig) sind. Die Church-Turing-These behauptet daher, dass die Turingmaschinen den intuitiven Begriff der Berechenbarkeit wiedergeben. In der Berechenbarkeitstheorie heißen genau die Funktionen berechenbar, die Turing-berechenbar sind. Zu den Turing-mächtigen Berechnungsmodellen gehören neben der Turingmaschine beispielsweise Zweikellerautomaten, WHILE-Programme, μ-rekursive Funktionen, Registermaschinen und der Lambda-Kalkül. Zu den Berechnungsmodellen, die schwächer sind als Turingmaschinen, gehören zum Beispiel die LOOP-Programme. Diese können zum Beispiel die Turing-berechenbare Ackermannfunktion nicht berechnen. Ein dem Begriff der Berechenbarkeit eng verwandter Begriff ist der der Entscheidbarkeit. Eine Teilmenge einer Menge (zum Beispiel eine Formale Sprache) heißt entscheidbar, wenn ihre charakteristische Funktion (im Wesentlichen das zugehörige Prädikat) berechenbar ist. (de) Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power. Other forms of computability are studied as well: computability notions weaker than Turing machines are studied in automata theory, while computability notions stronger than Turing machines are studied in the field of hypercomputation. (en) La teoria della computabilità effettiva si occupa della esistenza o meno di algoritmi risolutivi di problemi. Fra i suoi fondatori vi è Alan Turing. (it) In de complexiteitstheorie is berekenbaarheid een eigenschap van functies. Een overeenkomstige eigenschap voor verzamelingen en eigenschappen is beslisbaarheid. In alle gevallen gaat het om het bestaan van een algoritme. (nl) Обчислюваність — властивість задачі бути ефективно розв'язаною. Це ключова тема в області теорії обчислюваності в рамках математичної логіки і теорії алгоритмів у інформатиці. Обчислюваність задачі тісно пов'язана з задачею існування алгоритму для її вирішення. Найбільш широко вивченими моделями обчислюваності є Тюрінг-обчислювальні і , та лямбда-числення, всі з них мають парно еквівалентну обчислювальну потужність (алгоритми побудовані для однієї системи мають відповідники у інших). Досліджуються й інші форми обчислюваності: в теорії автоматів вивчаються поняття обчислюваності, які слабкіші за машини Тюрінга, тоді як області гіперобчислень вивчаються сильніші поняття обчислюваності. (uk) Computabilidade é a habilidade de resolver problemas de forma efetiva. É um tópico chave para o campo da Teoria da Computabilidade dentro da Lógica Matemática e para a Teoria da Computação dentro da Ciência da Computação. A computabilidade de um problema é intimamente ligada à existência de um algoritmo para resolver o problema. Os modelos mais estudados da computabilidade são as funções Turing-Computáveis e as funções μ-recursivas, e o cálculo lambda, todos os quais têm poderes computacionais equivalentes. Outras formas de computabilidade são também estudadas: noções de computabilidade mais fracas que as máquinas de Turing são estudadas na Teoria dos autômatos, enquanto que noções mais fortes que as máquinas de Turing são estudadas no campo da Hipercomputação. (pt) 可计算性（Computability）是指一个实际问题是否可以使用计算机来解决。从广义上讲如“为我烹制一个汉堡”这样的问题是无法用计算机来解决的（至少在目前）。而计算机本身的优势在于数值计算，因此可计算性通常指这一类问题是否可以用计算机解决。事实上，很多非数值问题（比如文字识别，图象处理等）都可以通过转化成为数值问题来交给计算机处理，但是一个可以使用计算机解决的问题应该被定义为“可以在有限步骤内被解决的问题”，故哥德巴赫猜想这样的问题是不属于“可计算问题”之列的，因为计算机没有办法给出数学意义上的证明，因此也没有任何理由期待计算机能解决世界上所有的问题。分析某个问题的可计算性意义重大，它使得人们不必浪费时间在不可能解决的问题上（因而可以尽早转而使用除计算机以外更加有效的手段），集中资源在可以解决的问题上。 (zh) |
| dbo:wikiPageExternalLink | https://archive.org/details/introductiontoth00sips |
| dbo:wikiPageID | 442136 (xsd:integer) |
| dbo:wikiPageLength | 21881 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1029984338 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Pushdown_automaton dbr:Nondeterministic_finite_automaton dbr:Beta_reduction dbr:Brainfuck dbr:Deterministic_finite_automaton dbr:Algorithm dbr:Hypercomputer dbr:Regular_expression dbr:Decision_problem dbr:Μ-recursive_function dbr:Combinatory_logic dbr:Computability_theory dbr:Context-free_grammar dbr:Mathematical_logic dbr:Pumping_lemma_for_regular_languages dbr:Church–Turing_thesis dbr:Modular_arithmetic dbr:Concurrency_(computer_science) dbr:Context-free_language dbr:Computability_logic dbr:Computational_complexity_theory dbr:Computational_problem dbr:Computer_science dbr:Function_composition_(computer_science) dbr:Function_problem dbr:Petri_net dbr:P′′ dbr:String_(computer_science) dbr:Theory_of_computation dbr:Markov_algorithm dbr:Gödel_numbering dbr:Pumping_lemma_for_context-free_languages dbr:Post_canonical_system dbr:Recursively_enumerable_language dbr:Number_theory dbr:Parallel_random-access_machine dbr:Formal_language dbr:Grammar dbr:Regular_language dbr:Halting_problem dbr:Hypercomputation dbr:Abstract_machine dbc:Computability_theory dbc:Theory_of_computation dbr:Chomsky_hierarchy dbr:Lambda_calculus dbr:Recursive_language dbr:Register_machine dbr:Automata_theory dbr:Pigeonhole_principle dbr:Optimization_problem dbr:Search_problem dbr:Model_of_computation dbr:Turing_machine dbr:String_rewriting_system dbr:Undecidable_problem dbr:List_of_undecidable_problems dbr:Programming_language dbr:Mu-recursive_function dbr:Finite-state_machine dbr:Multitape_Turing_machine dbr:Rice's_theorem dbr:Turing-computable_function dbr:Important_publications_in_computability dbr:Primitive_recursion dbr:Recursion_theory dbr:Primality_testing |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Authority_control dbt:Cite_book dbt:Main dbt:Math dbt:Redirect dbt:Short_description dbt:Computable_knowledge |
| dcterms:subject | dbc:Computability_theory dbc:Theory_of_computation |
| gold:hypernym | dbr:Ability |
| rdf:type | owl:Thing dbo:Disease |
| rdfs:comment | الحاسوبية هي القدرة على حل مشكلة ما بطريقة فعاله. وهي الموضوع الرئيسي لمجال نظرية الحاسوبية في المنطق الرياضي ونظرية الحساب في علوم الحاسوب. حاسوبية المشكلة ترتبط بشدة بوجود خوارزمية لحل المشكلة.إن أوسع نماذج الحاسوبية دراسةً هم آلة تورنغ ودوال المايكرو المتكررة وحسابات اللامدا، وجميعهم لهم قوى حسابية معادله. توجد أيضاً أشكال أخرى من الحاسوبية تتم دراستها: مفاهيم الحاسوبية الأضعف من آلات تورنغ تتم دراستهم في نظرية التشغيل الذاتي، بينما مفاهيم الحاسوبية الأقوى من آلات تورنغ تتم دراستهم في مجال الحساب الأعلى. (ar) La teoria della computabilità effettiva si occupa della esistenza o meno di algoritmi risolutivi di problemi. Fra i suoi fondatori vi è Alan Turing. (it) In de complexiteitstheorie is berekenbaarheid een eigenschap van functies. Een overeenkomstige eigenschap voor verzamelingen en eigenschappen is beslisbaarheid. In alle gevallen gaat het om het bestaan van een algoritme. (nl) 可计算性（Computability）是指一个实际问题是否可以使用计算机来解决。从广义上讲如“为我烹制一个汉堡”这样的问题是无法用计算机来解决的（至少在目前）。而计算机本身的优势在于数值计算，因此可计算性通常指这一类问题是否可以用计算机解决。事实上，很多非数值问题（比如文字识别，图象处理等）都可以通过转化成为数值问题来交给计算机处理，但是一个可以使用计算机解决的问题应该被定义为“可以在有限步骤内被解决的问题”，故哥德巴赫猜想这样的问题是不属于“可计算问题”之列的，因为计算机没有办法给出数学意义上的证明，因此也没有任何理由期待计算机能解决世界上所有的问题。分析某个问题的可计算性意义重大，它使得人们不必浪费时间在不可能解决的问题上（因而可以尽早转而使用除计算机以外更加有效的手段），集中资源在可以解决的问题上。 (zh) Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. (en) Eine mathematische Funktion ist berechenbar (auch effektiv berechenbar oder rekursiv), wenn für sie eine Berechnungsanweisung (Algorithmus) formuliert werden kann (Berechenbarkeitstheorie). Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe reagiert. Der Definitionsbereich der Funktion ist die Menge der Eingaben, für die der Algorithmus eine Ausgabe produziert. Wenn der Algorithmus nicht terminiert, dann ist die Eingabe kein Element der Definitionsmenge. (de) Computabilidade é a habilidade de resolver problemas de forma efetiva. É um tópico chave para o campo da Teoria da Computabilidade dentro da Lógica Matemática e para a Teoria da Computação dentro da Ciência da Computação. A computabilidade de um problema é intimamente ligada à existência de um algoritmo para resolver o problema. (pt) Обчислюваність — властивість задачі бути ефективно розв'язаною. Це ключова тема в області теорії обчислюваності в рамках математичної логіки і теорії алгоритмів у інформатиці. Обчислюваність задачі тісно пов'язана з задачею існування алгоритму для її вирішення. (uk) |
| rdfs:label | Computability (en) الحاسوبية (ar) Berechenbarkeit (de) Computabilità (it) Berekenbaarheid (nl) Computabilidade (pt) Обчислюваність (uk) 可计算性 (zh) |
| owl:sameAs | freebase:Computability wikidata:Computability dbpedia-als:Computability dbpedia-ar:Computability dbpedia-bg:Computability dbpedia-de:Computability dbpedia-fa:Computability dbpedia-he:Computability dbpedia-it:Computability dbpedia-nl:Computability dbpedia-pt:Computability dbpedia-uk:Computability dbpedia-zh:Computability https://global.dbpedia.org/id/4ya7Q |
| prov:wasDerivedFrom | wikipedia-en:Computability?oldid=1029984338&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Computability |
| is dbo:notableIdea of | dbr:Kazem_Sadegh-Zadeh |
| is dbo:wikiPageRedirects of | dbr:Formal_models_of_computation dbr:Calculability dbr:Calculable dbr:Calculably dbr:Calculatable dbr:Computable |
| is dbo:wikiPageWikiLink of | dbr:Scott_Aaronson dbr:List_of_computer_science_conferences dbr:List_of_computer_scientists dbr:Primality_Testing_for_Beginners dbr:David_Harel dbr:Algorithm dbr:List_of_important_publications_in_theoretical_computer_science dbr:Cubical_complex dbr:Index_of_philosophy_articles_(A–C) dbr:Quantum_computing dbr:Computability_theory dbr:General_purpose_analog_computer dbr:Oron_Shagrir dbr:Church–Turing_thesis dbr:Edward_F._Moore dbr:Glossary_of_areas_of_mathematics dbr:Cop-win_graph dbr:Andrzej_Grzegorczyk dbr:Louis_Hodes dbr:Complexity_class dbr:Computability_logic dbr:Computable_analysis dbr:Computable_model_theory dbr:Successor_function dbr:Automated_theorem_proving dbr:Divine_Proportions:_Rational_Trigonometry_to_Universal_Geometry dbr:Logics_for_computability dbr:Ada_Lovelace dbr:Formal_models_of_computation dbr:Brouwer_fixed-point_theorem dbr:Norman_Shapiro dbr:Number_theory dbr:Discrete_mathematics dbr:Michel_Raynal dbr:Heidelberg_University_Faculty_of_Mathematics_and_Computer_Science dbr:Israel_Institute_for_Advanced_Studies dbr:Tal_Rabin dbr:Abstract_machine dbr:Kazem_Sadegh-Zadeh dbr:Lambda_calculus dbr:Effective_topos dbr:Read-only_Turing_machine dbr:Solomonoff's_theory_of_inductive_inference dbr:Field-programmable_gate_array dbr:New_media dbr:Certificate_(complexity) dbr:Shimer_Great_Books_School dbr:Maximal_set dbr:Turing_machine dbr:Vladik_Kreinovich dbr:Well-structured_transition_system dbr:Shadows_of_the_Mind dbr:Queue_automaton dbr:Outline_of_discrete_mathematics dbr:Turing_completeness dbr:Calculability dbr:Calculable dbr:Calculably dbr:Calculatable dbr:Computable |
| is foaf:primaryTopic of | wikipedia-en:Computability |