Turing completeness (original) (raw)
Mit Turing-Vollständigkeit eines Systems wird seine universelle Programmierbarkeit beschrieben. Für die Adjektivform Turing-vollständig wird synonym häufig auch turingmächtig verwendet. Der Name ist abgeleitet vom englischen Mathematiker Alan Turing, der das Modell der universellen Turingmaschine eingeführt hat.
| Property | Value |
|---|---|
| dbo:abstract | En la teoria d'ordinadors reals i imaginaris, dels llenguatges de programació i d'altres sistemes lògics, un sistema Turing complet és aquell que té un poder computacional equivalent a la màquina universal de Turing. En altres paraules, el sistema i la màquina universal de Turing poden emular-se entre si. Encara quan és físicament impossible que existeixin aquestes màquines a causa que requereixen emmagatzematge il·limitat i probabilitat zero d'error, de forma col·loquial la completesa de Turing s'atribueix a màquines físiques o llenguatges de programació que podrien ser universals si tinguessin emmagatzematge infinit i fossin absolutament fiables. La primera d'aquestes màquines va aparèixer en 1941: la Z3 de Konrad Zuse, que era controlada per programes. La seva universalitat, no obstant això, va ser demostrada molt de temps després per en 1998. En aquest sentit, tots els ordinadors moderns són també Turing complets. La completesa de Turing és significativa, doncs, cada disseny plausible d'un dispositiu de computació, per més avançat que sigui (àdhuc els ordinadors quàntics), poden ser emulades per una màquina universal de Turing. Així, una màquina que pugui actuar com una màquina universal de Turing pot, en principi, fer qualsevol càlcul que qualsevol altre ordinador és capaç de fer (en altres paraules, és programable). No obstant això, no hi ha esforç d'escriure un programa per a la màquina o sobre el temps que pot prendre el càlcul. Hi ha la hipòtesi que l'Univers és Turing complet (vegeu implicacions filosòfiques en la Tesi de Church-Turing i en Física digital). Vegeu l'article de Teoria de la computabilitat per a una llarga llista de sistemes que són Turing complets, així com diversos sistemes que són menys potents, i diversos sistemes teòrics que són encara més potents que la màquina universal de Turing. (ca) Turingovská úplnost je pojem z oboru teorie vyčíslitelnosti: Turingovsky kompletní, turingovsky úplný nebo turingovsky ekvivalentní (anglicky Turing-complete) je stroj (počítač), programovací jazyk, úloha nebo , který má stejnou výpočetní sílu jako Turingův stroj. Tato třída je důležitá proto, že není znám žádný způsob řešení úlohy, která je těžší (podle Churchovy–Turingovy teze žádné konečné zařízení víc spočítat nedokáže). Dá se tedy říct, že turingovsky kompletní stroj je tak univerzální, jak je jen možné (to ovšem neříká nic o efektivitě). Speciálně lze sestrojit univerzální Turingův stroj, který dokáže simulovat libovolný jiný Turingův stroj (zadaný na vstupu). Jazyky přijímané Turingovým strojem se nazývají rekurzivně spočetné jazyky. Gramatiky, které generují tyto jazyky, se v rámci Chomského hierarchie označují jako gramatiky typu 0. Typickým problémem, který nelze řešit na Turingově stroji, je problém zastavení (anglicky halting problem), tedy problém zastavení Turingova stroje. Matematicky je tento problém demonstrací neuzavřenosti třídy rekurzivně spočetných jazyků na doplněk. Teorie vyčíslitelnosti pokračuje v teoretickém výzkumu k ještě složitějším problémům – aritmetická hierarchie je posloupnost tříd jazyků. Její nultý stupeň jsou rekurzivně spočetné jazyky, všechny jazyky na stejném stupni jsou mezi sebou turingovsky převoditelné a problém zastavení pro stupeň N je ve stupni N+1. (cs) في نظرية الحاسوبية، يقال عن نظام قواعد التعامل مع البيانات (مثل مجموعة التعليمات لكمبيوتر، لغة البرمجة، أوخلايا ذاتية السلوك) بأنها كاملة حسب تورنغ أو عامة حسابيا إذا كان يمكن استخدامها لمحاكاة أي آلة تورنغ وحيدة الشريط. يستقى هذا المفهوم من عالم الرياضيات الإنجليزي آلان تورنغ. المثال التقليدي هو حساب لامدا. هناك مفهوم يرتبط ارتباطا وثيقا هو تكافؤ تورنغ - إذا كان لدينا جهازي كمبيوتر P وQ فإننا نقول بانهما متكافئان حسب تورنغ إذا كان P يمكنه محاكاة Q وQ يمكنه محاكاة P.أطروحة تشرتش-تورنغ تقول بأن أي وظيفة التي يمكن حساب مقاديرها بوساطة خوارزمية يمكن حسابها من قبل آلة تورنغ، وبالتالي أنه إذا كان يمكن محاكاة أي جهاز كمبيوتر في العالم الحقيقي من قبل آلة تورنغ، فهو مكافئ تورنغ لآلة تورنغ. آلة تورنغ العامة يمكن استخدامها لمحاكاة أي آلة تورنغ وبالتالي محاكاة الجوانب الحسابية لأي جهاز كمبيوتر في العالم الحقيقي. لاظهار ان هناك شيئا كاملاً حسب تورنغ، يكفي إظهار أنه يمكن استخدامه لمحاكاة نظام تورنغ كامل ما. على سبيل المثال، اللغة الأمرية هي كاملة حسب تورنغ إذا كان لديه التفرع المشروط (على سبيل المثال تعليمات، "if" و"go to"، أو أمر "branch if zero". انظر )، والقدرة على تغيير مقدار الذاكرة الأولي (على سبيل المثال، القدرة على الحفاظ على عدد ما من المتغيرات). وبما أن هذا هو الحال دائما تقريبا، معظم (إن لم يكن كل) اللغات حتمية وتورنغ كاملة إذا تم تجاهل القيود المفروضة على ذاكرة محدودة. (ar) Στη θεωρία υπολογισιμότητας, ένα σύστημα κανόνων διαχείρισης δεδομένων (όπως οι ομάδες εντολών του υπολογιστή, ή η γλώσσα προγραμματισμού ή ένα κυψελοειδές αυτόματο), λέγεται ότι είναι "Τούρινγκ {Turing} πλήρες" ή "υπολογιστικά καθολικό" αν μπορεί να χρησιμοποιηθεί για να προσομοιώσει οποιαδήποτε μηχανή Τούρινγκ. Αυτό σημαίνει, ότι αυτό το σύστημα είναι σε θέση να αναγνωρίσει ή να αποφασίσει άλλα σύνολα κανόνων χειρισμού δεδομένων. Αυτή η "πληρότητα Turing", χρησιμοποιείται ως ένας τρόπος έκφρασης της ισχύος ενός τέτοιου κανόνα διαχείρισης δεδομένων. Η δύναμη έκφρασης αυτών των "γραμματικών", καταγράφεται στην "". Πρακτικά, σχεδόν όλες οι γλώσσες προγραμματισμού, είναι σήμερα "Τούρινγκ πλήρεις". Η ονομασία της έννοιας αυτής είναι φόρος τιμής στον Άγγλο μαθηματικό και επιστήμονα πληροφορικής, Άλαν Τούρινγκ. Μια σχετική ιδέα είναι αυτή της ισοδυναμίας Τούρινγκ, ότι δηλαδή, δύο υπολογιστές Α και Β ονομάζονται "ισοδύναμοι", αν o Α μπορεί να προσομοιώσει τον Β και ο Β μπορεί να προσομοιώσει τον Α. Η , λέει ότι οποιαδήποτε συνάρτηση, της οποίας οι τιμές μπορούν να υπολογιστούν από έναν αλγόριθμο, μπορούν να υπολογιστούν και από μια μηχανή Τούρινγκ και επομένως ότι αν οποιοσδήποτε πραγματικός υπολογιστής μπορεί να προσομοιώσει μια μηχανή Turing, είναι "Τούρινγκ ισοδύναμος" με μια μηχανή Τούρινγκ. Μια καθολική μηχανή Τούρινγκ, μπορεί να χρησιμοποιηθεί για την προσομοίωση οποιασδήποτε άλλης μηχανής Turing και κατ' επέκταση των υπολογιστικών πτυχών οποιουδήποτε πιθανού υπολογιστή στον πραγματικό κόσμο. Για να δείξουμε ότι κάτι είναι "Τούρινγκ πλήρες", αρκεί μόνο να δείξουμε ότι μπορεί να χρησιμοποιηθεί για να προσομοιώσει ένα "Τούρινγκ πλήρες" σύστημα. Για παράδειγμα, μια προστακτική γλώσσα είναι "Τούρινγκ πλήρης" εάν έχει τις λεγόμενες "υπό συνθήκη διακλαδώσεις", (π.χ., "if" και "goto" δηλώσεις, ή μια εντολή "branch if zero") και την ικανότητα να αλλάξει ένα αυθαίρετο ποσό μνήμης (π.χ., η ικανότητα διατήρησης ενός αυθαίρετου αριθμού στοιχείων δεδομένων). Φυσικά, κανένα φυσικό σύστημα δεν μπορεί να έχει άπειρη μνήμη, αλλά αν αγνοηθεί ο περιορισμός της πεπερασμένης μνήμης, οι περισσότερες γλώσσες προγραμματισμού είναι "Τούρινγκ πλήρεις". (el) Mit Turing-Vollständigkeit eines Systems wird seine universelle Programmierbarkeit beschrieben. Für die Adjektivform Turing-vollständig wird synonym häufig auch turingmächtig verwendet. Der Name ist abgeleitet vom englischen Mathematiker Alan Turing, der das Modell der universellen Turingmaschine eingeführt hat. (de) Turing kompleteco estas esprimo uzita en komputebleca teorio por priskribi abstraktajn maŝinojn, kutime nomitajn aŭtomatojn. Tia aŭtomato estas Turing-kompleta, se ĝi povas esti uzata por emuli Turing-maŝinon. Ĝi ankaŭ nomiĝas komputile universala. Plej multaj modernaj programlingvoj estas Turing-kompletaj. Estas lingvoj uzataj por klasifiki kaj priskribi la enhavon de dokumentoj; ekzemple HTML. HTML ne estas Turing-kompleta, ĉar ĝi ne povas aktive ŝanĝi la staton de la sistemo. HTML povas esti kombinata kun teknologio kiel JavaScript; ambaŭ kune fariĝas Turing-kompletaj. La normaj regulaj esprimoj, kiujn plej multaj programlingvoj uzas, ankaŭ ne estas Turing-kompletaj. Plej multaj regulaj esprimaj motoroj estis adaptitaj por inkluzivi malantaŭajn referencojn. La problemo pri tio estas, ke finia aŭtomato ne povas trakti malantaŭajn referencojn. (eo) En la teoría de computadoras reales y virtuales, de los lenguajes de programación y de otros sistemas lógicos, un sistema Turing completo es aquel que tiene un poder computacional equivalente a la máquina de Turing universal. En otras palabras, el sistema y la máquina universal de Turing pueden emularse entre sí. Aun cuando es físicamente imposible que existan estas máquinas debido a que requieren de almacenamiento ilimitado y probabilidad cero de falla, de forma coloquial la completitud de Turing se atribuye a máquinas físicas o lenguajes de programación que podrían ser universales si tuvieran almacenamiento infinito y fueran absolutamente fiables. La primera de esas máquinas apareció en 1941: la Z3 de Konrad Zuse, que era controlada por programas. Su universalidad, sin embargo, fue demostrada mucho después por Raúl Rojas en 1998. En ese sentido laxo, todas las computadoras modernas son también Turing completas. La completitud de Turing es significativa, pues, cada diseño verosímil de un dispositivo de computación, por más avanzado que sea (aun las computadoras cuánticas), pueden ser emuladas por una máquina universal de Turing. Así, una máquina que pueda actuar como una máquina universal de Turing puede, en principio, hacer cualquier cálculo que cualquier otra computadora es capaz de hacer (ver Tesis de Church-Turing). Obsérvese, sin embargo, que no dice nada sobre el esfuerzo de escribir un programa para la máquina o sobre el tiempo que puede tomar el cálculo. Está la hipótesis de que el Universo es Turing completo (ver implicaciones filosóficas en la Tesis de Church-Turing y en Física digital). Ver el artículo en Teoría de la computabilidad para una larga lista de sistemas que son Turing completos, así como varios sistemas que son menos poderosos, y varios sistemas teóricos que serían aún más poderosos que la máquina universal de Turing. (es) En informatique et en logique, un système formel est dit complet au sens de Turing ou Turing-complet (par calque de l’anglais Turing-complete) s’il possède un pouvoir expressif au moins équivalent à celui des machines de Turing. Dans un tel système, il est donc possible de programmer n'importe quelle machine de Turing. Cette notion est rendue pertinente par la thèse de Church, qui postule l’existence d’une notion naturelle de calculabilité. Ainsi, le pouvoir expressif des machines de Turing coïncide avec celui des fonctions récursives, du lambda calcul, ou encore des machines à compteurs. Bien que certains modèles de calcul, appelés des hypercalculs, soient strictement plus expressifs que les machines de Turing, ces modèles sont des objets de spéculation (requérant par exemple d’effectuer une infinité d’opérations, ou de calculer sur l’ensemble des nombres réels) et l’on ignore s’ils sont physiquement réalisables. Dans ces conditions, la thèse de Church conjecture l’universalité du modèle de calcul des machines de Turing : tout système Turing-complet serait en fait équivalent aux machines de Turing. (fr) In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Turing machine (devised by English mathematician and computer scientist Alan Turing). This means that this system is able to recognize or decide other data-manipulation rule sets. Turing completeness is used as a way to express the power of such a data-manipulation rule set. Virtually all programming languages today are Turing-complete. A related concept is that of Turing equivalence – two computers P and Q are called equivalent if P can simulate Q and Q can simulate P. The Church–Turing thesis conjectures that any function whose values can be computed by an algorithm can be computed by a Turing machine, and therefore that if any real-world computer can simulate a Turing machine, it is Turing equivalent to a Turing machine. A universal Turing machine can be used to simulate any Turing machine and by extension the computational aspects of any possible real-world computer. To show that something is Turing-complete, it is enough to show that it can be used to simulate some Turing-complete system. No physical system can have infinite memory, but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete. (en) La Turing equivalenza è la proprietà dei che hanno lo stesso potere computazionale di una macchina di Turing universale (MdTu). Un modello che ha lo stesso potere computazionale di una MdTu si dice Turing equivalente o Turing completo. (it) 튜링 완전(turing completeness)이란 어떤 프로그래밍 언어나 추상 기계가 튜링 기계와 동일한 계산 능력을 가진다는 의미이다. 이것은 튜링 기계로 풀 수 있는 문제, 즉 계산적인 문제를 그 프로그래밍 언어나 추상 기계로 풀 수 있다는 의미이다. 제한 없는 크기의 기억 장치를 갖는 기계를 만드는 것이 불가능하므로, 진정한 의미의 튜링 완전 기계는 아마도 물리적으로 불가능할 것이다. 그러나, 제한 없이 기억 장치의 크기를 늘려갈 수 있다고 가정할 수 있는 물리적인 기계 혹은 프로그래밍 언어에 대해서는, 느슨하게 튜링 완전하다고 간주한다. 이런 맥락에서, 요즘 나온 컴퓨터들은 튜링 완전하다고 여겨지고 있다. (ko) チューリング完全（チューリングかんぜん、英語: Turing-complete）とは、計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全あるいは計算完備であるという。 チャーチ＝チューリングのテーゼによれば「計算可能関数」は、それを計算しようとする計算モデルがチューリング完全であれば計算できる。 一般的なプログラミング言語の背景にある計算モデルの多くはチューリング完全である。一見単純な機能しか持たない言語がチューリング完全な例としては、Lazy K、Brainfuckなどがある。究極的に単純な計算モデルとしては「がチューリング完全であると証明されている。 チューリング完全かどうかという事は、計算可能性理論の問題である。計算複雑性の分野の問題である時間や記憶容量の消費量については考えない。表計算における数式の処理などで、繰り返し処理をどうやっても実現できなければそれはチューリング完全ではない。 (ja) Kompletność Turinga – cecha systemu przetwarzającego dane lub języka programowania, polegająca na tym, że można za jego pomocą rozwiązać identyczną klasę problemów obliczeniowych, jak na uproszczonym modelu programowalnego komputera zwanego maszyną Turinga. W praktyce oznacza to, że jeśli dany język, maszyna lub inny system potrafi wykonać lub wyrazić każdy algorytm, określany jest mianem zupełnego, przy czym nie jest wymagane, by algorytm ten realizowany był prosto, wydajnie bądź efektywnie. Termin wywodzi się od nazwiska matematyka Alana Turinga, który jako pierwszy zaproponował model uniwersalnej maszyny Turinga. (pl) In de berekenbaarheidstheorie wordt een programmeertaal, of een ander systeem om bewerkingen mee uit te drukken, turingvolledig (vaker: turingcompleet) genoemd als het de uitdrukkingskracht heeft van een universele turingmachine. Dat betekent ruwweg dat elke berekening of gegevensbewerking die geprogrammeerd kan worden, ook in dit systeem geprogrammeerd kan worden. Het woord verwijst naar de wiskundige Alan Turing, die de turingmachine als algemene maatstaf van berekenbaarheid heeft uitgevonden. (nl) Na teoria da computação, a completude de Turing ou Turing-completo (do inglês: Turing-completeness; batizado em memória de Alan Turing), também chamado computacionalmente universal, é um conjunto de regras para manipulação de dados (semelhante a uma linguagem de programação, um autómato celular, um conjunto de instruções) que pode ser usado para resolver qualquer problema de computação (simula a lógica de qualquer algoritmo de computador). este é completo ou universal se e somente se puder ser usado para controlar a máquina de Turing (a máquina digital primitiva e universal), e assim podendo controlar qualquer computador. Um exemplo clássico é o cálculo lambda (um sistema formal que estuda funções recursivas computáveis). Na prática, completude de Turing significa que, regras seguidas em sequência sobre dados arbitrários podem produzir o resultado de qualquer cálculo. Em linguagens procedurais isso poder ser satisfeito tendo-se, no mínimo, saltos condicionais (usando "if" ou "goto") e a habilidade de modificar arbitrariamente locais da memória RAM (como as variáveis). Para mostrar que algo é Turing-completo, é suficiente mostrar que ele pode ser usado para simular o computador mais primitivo, pois mesmo o tipo mais simples de computador pode ser usado para simular os tipos mais complexos. Todas as linguagens de programação de uso geral e todos os conjuntos de instruções de máquina modernos são Turing-completos, não obstante limitações de memória finita. Um conceito relacionado a completude é, a equivalência de Turing, onde dois computadores "P" e "Q" são chamados de equivalentes se "P" pode simular "Q" e "Q" pode simular "P". Um computador universal é definido como um dispositivo com um conjunto de instruções Turing-completo, memória infinita, e um tempo de vida infinito. Todos os sistemas do mundo real necessariamente possuem memória finita, fazendo do verdadeiro computador universal apenas uma construção teórica. Na teoria da computação, há um conceito bastante relacionado chamado de Turing-equivalência. Dois computadores P e Q são ditos Turing-equivalentes se P puder simular Q e Q puder simular P. Assim, um sistema Turing-completo é aquele que pode simular uma máquina de Turing. Porém, o termo é normalmente usado com o significado de Turing-equivalente a uma máquina de Turing. A razão é que qualquer máquina do mundo real pode ser simulada por uma máquina de Turing, observação esta codificada como a Tese de Church-Turing. Um computador com acesso a uma fita infinita de dados é às vezes mais poderoso que uma máquina de Turing, pois a fita, a princípio, pode conter a solução para o problema da parada, ou para algum outro problema indecidível. Uma fita infinita de dados é chamada de Turing-oráculo. Até mesmo um Turing-oráculo com dados aleatórios não é computável (com probabilidade 1), pois há um número contável de computações, mas um número incontável de oráculos. Então, um computador com um Turing-oráculo aleatório pode computar coisas que uma máquina de Turing não pode. Uma máquina que é universal, exceto que não possui um Turing-oráculo, é chamada de máquina fracamente universal. (pt) Turingkomplett är ett begrepp som lanserades av den brittiske matematikern Alan Turing (1912–1954). Ett programspråk anses vara turingkomplett då man kan beräkna samtliga beräkningsbara problem i det, givet tillräcklig tid och tillräckligt minnesutrymme. En maskin anses vara turingkomplett när den kan utföra de operationer som behövs för att kunna beräkna alla beräkningsbara problem som finns. Denna maskin är då en turingmaskin. I teorin kan en maskin som är turingkomplett exekvera samtliga programvaror för andra turingkompletta maskiner, förutsatt att programvaran skrivs om för den aktuella maskinens hårdvara, eller körs i en emulator. (sv) Полнота по Тьюрингу — характеристика исполнителя (множества вычисляющих элементов) в теории вычислимости, означающая возможность реализовать на нём любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных). Свойство названо по имени Алана Тьюринга, разработавшего абстрактный вычислитель— машину Тьюринга, и давшего определение множества функций, вычислимых посредством машин Тьюринга. (ru) 在可计算性理论，如果一系列操作数据的规则（如指令集、编程语言、细胞自动机）可以用来模拟任何图灵机，那么它是图灵完备的。这意味着这个系统也可以识别其他数据处理规则集，图灵完备性被用作表达这种数据处理规则集的一种属性。如今，几乎所有编程语言都是具有图灵完备性的。这个词以引入图灵机概念的数学家艾伦·图灵命名。 还有一个相关概念是图灵等价 – 如果P可以模拟Q并且Q可以模拟P，则两台计算机P和Q称为等效计算机。 邱奇－图灵论题认为任何可以通过算法计算其值的函数都可以由图灵机计算，因此，如果任何真实世界的计算机都可以模拟图灵机，则其对图灵机是图灵等价的。 通用图灵机可用于模拟任何图灵机，且可以扩展现实世界计算机的计算方面。 如果某物是图灵完备的，则它可以用于模拟某些图灵完备的系统。例如，一个指令式编程具有条件表达式（例如，“ if”和“ goto”语句，或者“branch if zero”的指令；请参见单一指令计算机）并且具有更改任意指令的能力，则他为图灵完备的。 注意，虽然任何物理系统都不可能进行无限的迭代展开，但如果忽略了这一限制，则绝大多数物理系统都将是图灵完备的。 (zh) У теорії алгоритмів набір правил маніпуляції даними (набір інструкцій, мова програмування чи клітинний автомат) вважається повним за Тюрінгом тоді і тільки тоді, коли цей набір може моделювати однострічкову машину Тюрінга. Класичними системами, що теж описуються простими правилами та є Тюрінг-повними, є контекстно-залежні граматики, рекурсивні функції та лямбда-числення. На практиці повнота за Тюрінгом означає, що при застосуванні певної послідовності правил над даними можна отримати результат будь-якого обчислення. Пристрій з Тюрінг-повним набором інструкцій є означенням універсального комп'ютера. Щоб бути повним за Тюрінгом достатньо мати команди переходу як , так і безумовний оператори, та можливість змінювати пам'ять. Щоб показати, що щось є Тюрінг-повним, достатньо показати, що на ньому можна емулювати найпримітивніший універсальний комп'ютер, оскільки навіть найпростіший універсальний комп'ютер може емулювати найскладніший. Всі мови загального призначення та набори машинних інструкцій є повними за Тюрінгом, доки не постає проблема скінченності пам'яті. Тюрінг-повні машини описані як такі, що мають необмежений обсяг пам'яті, а в той час набори машинних інструкцій складені, щоб працювати з конкретним, обмеженим обсягом оперативної пам'яті. У теорії алгоритмів існує близький термін: Тюрінг-еквівалентність — два комп'ютери P та Q називаються Тюрінг-еквівалентними, якщо P може імітувати Q та Q може імітувати P. Машину Тюрінга може імітувати тільки Тюрінг-повна система, тому цей термін найчастіше застосовується, щоб описати еквівалентну за Тюрінгом до машини Тюрінга. А все тому, що кожен реальний комп'ютер може моделюватись машиною Тюрінга, це спостереження зафіксоване тезою Черча. (uk) |
| dbo:wikiPageExternalLink | https://c2.com/cgi/wiki%3FTuringComplete https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf https://archive.org/details/theoryofcomputat00brai https://www.newscientist.com/article/dn12826-simplest-universal-computer-wins-student-25000.html |
| dbo:wikiPageID | 30621 (xsd:integer) |
| dbo:wikiPageLength | 27744 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124615103 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Primitive_recursive_function dbr:Prolog dbr:Pushdown_automaton dbr:Python_(programming_language) dbr:Habbo_Hotel dbr:Printf_format_string dbr:David_Hilbert dbr:Declarative_programming dbr:Dependent_type dbr:Algorithm dbr:Algorithmic_information_theory dbr:Almost_surely dbr:Perl dbr:Regular_expression dbr:Rewrite_system dbr:DNA_computing dbr:Universe dbr:VHDL dbr:Inner_loop dbr:Colloquial dbr:Common_Lisp dbr:Compiler dbr:Computability dbr:Computability_theory dbr:Computable_function dbr:Computer dbr:Context-free_grammar dbr:SQL dbr:Chemical_computer dbr:Esoteric_programming_language dbr:General-purpose_macro_processor dbr:Church–Turing_thesis dbr:Cities:_Skylines dbr:Epigram_(programming_language) dbr:General_recursive_function dbr:Multi-paradigm_programming_language dbr:Control_flow dbr:Conway's_Game_of_Life dbc:Turing_machine dbr:Rule_110 dbr:Leopold_Kronecker dbr:Lisp_(programming_language) dbr:Analytical_engine dbr:M4_(computer_language) dbr:Machine_that_always_halts dbr:Simply_typed_lambda_calculus dbr:Smalltalk dbr:Computer_program dbr:Z3_(computer) dbr:Functional_programming dbr:Theoretical_computer_science dbr:Total_functional_programming dbr:C++ dbr:C_(programming_language) dbr:C_Sharp_(programming_language) dbr:Timeout_(computing) dbr:TypeScript dbr:Linear_bounded_automaton dbr:Logic_programming dbr:Ada_(programming_language) dbr:Alan_Turing dbr:Dwarf_Fortress dbr:ENIAC dbr:Fortran dbr:Pascal_(programming_language) dbr:Cellular_automaton dbr:Digital_physics dbr:Formal_grammar dbr:Formal_language dbr:Goto dbr:Emulation_(computing) dbr:Procedural_programming dbr:Recursion dbr:Regular_language dbr:Gödel's_incompleteness_theorem dbr:Halting_problem dbr:Haskell_(programming_language) dbr:JavaScript dbr:Java_(programming_language) dbr:TeX dbr:Template_(C++) dbr:Smn_theorem dbr:Abstract_machine dbc:Programming_language_theory dbc:Theory_of_computation dbr:Charles_Babbage dbr:Chomsky_hierarchy dbr:LOOP_(programming_language) dbr:Lambda_calculus dbr:Hierarchical_and_recursive_queries_in_SQL dbr:System_F dbr:Direct3D dbr:Automata_theory dbr:Post–Turing_machine dbr:Instruction_set dbr:Konrad_Zuse dbr:Kurt_Gödel dbr:Microsoft_Excel dbr:Microsoft_PowerPoint dbr:Minecraft dbr:New_Scientist dbr:Object_Pascal dbr:OpenGL dbr:Opus_Magnum_(video_game) dbr:Cantor's_diagonal_argument dbr:Category_theory dbr:R_(programming_language) dbr:Recursively_enumerable_set dbr:XSLT dbr:Process_calculus dbr:Model_of_computation dbr:Turing_machine dbr:Universal_Turing_machine dbr:Virtualization dbr:Von_Neumann_architecture dbr:Loop_(computing) dbr:Programming_language dbr:Finite-state_machine dbr:Structured_program_theorem dbr:PLSQL dbr:Object-oriented_programming_language dbr:Rice's_theorem dbr:Turing_tarpit dbr:Charity_(programming_language) dbr:Universal_computer dbr:Z4_(computer) dbr:Turing_oracle dbr:Functional_language dbr:Mathematical_recreation dbr:AI-completeness dbr:Computability_theory_(computation) |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Cite_book dbt:Cite_journal dbt:Cite_magazine dbt:Cite_web dbt:Cn dbt:Colend dbt:For dbt:Main_article dbt:Refbegin dbt:Refend dbt:Reflist dbt:See_also dbt:Short_description dbt:Snd dbt:Unreferenced_section dbt:Use_dmy_dates dbt:Cols dbt:Alan_Turing |
| dct:subject | dbc:Turing_machine dbc:Programming_language_theory dbc:Theory_of_computation |
| rdf:type | owl:Thing yago:Abstraction100002137 yago:ArtificialLanguage106894544 yago:Cognition100023271 yago:Communication100033020 yago:Concept105835747 yago:Content105809192 yago:Idea105833840 yago:Language106282651 yago:ProgrammingLanguage106898352 yago:PsychologicalFeature100023100 yago:WikicatProgrammingLanguageConcepts yago:WikicatProgrammingLanguages |
| rdfs:comment | Mit Turing-Vollständigkeit eines Systems wird seine universelle Programmierbarkeit beschrieben. Für die Adjektivform Turing-vollständig wird synonym häufig auch turingmächtig verwendet. Der Name ist abgeleitet vom englischen Mathematiker Alan Turing, der das Modell der universellen Turingmaschine eingeführt hat. (de) La Turing equivalenza è la proprietà dei che hanno lo stesso potere computazionale di una macchina di Turing universale (MdTu). Un modello che ha lo stesso potere computazionale di una MdTu si dice Turing equivalente o Turing completo. (it) 튜링 완전(turing completeness)이란 어떤 프로그래밍 언어나 추상 기계가 튜링 기계와 동일한 계산 능력을 가진다는 의미이다. 이것은 튜링 기계로 풀 수 있는 문제, 즉 계산적인 문제를 그 프로그래밍 언어나 추상 기계로 풀 수 있다는 의미이다. 제한 없는 크기의 기억 장치를 갖는 기계를 만드는 것이 불가능하므로, 진정한 의미의 튜링 완전 기계는 아마도 물리적으로 불가능할 것이다. 그러나, 제한 없이 기억 장치의 크기를 늘려갈 수 있다고 가정할 수 있는 물리적인 기계 혹은 프로그래밍 언어에 대해서는, 느슨하게 튜링 완전하다고 간주한다. 이런 맥락에서, 요즘 나온 컴퓨터들은 튜링 완전하다고 여겨지고 있다. (ko) チューリング完全（チューリングかんぜん、英語: Turing-complete）とは、計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全あるいは計算完備であるという。 チャーチ＝チューリングのテーゼによれば「計算可能関数」は、それを計算しようとする計算モデルがチューリング完全であれば計算できる。 一般的なプログラミング言語の背景にある計算モデルの多くはチューリング完全である。一見単純な機能しか持たない言語がチューリング完全な例としては、Lazy K、Brainfuckなどがある。究極的に単純な計算モデルとしては「がチューリング完全であると証明されている。 チューリング完全かどうかという事は、計算可能性理論の問題である。計算複雑性の分野の問題である時間や記憶容量の消費量については考えない。表計算における数式の処理などで、繰り返し処理をどうやっても実現できなければそれはチューリング完全ではない。 (ja) In de berekenbaarheidstheorie wordt een programmeertaal, of een ander systeem om bewerkingen mee uit te drukken, turingvolledig (vaker: turingcompleet) genoemd als het de uitdrukkingskracht heeft van een universele turingmachine. Dat betekent ruwweg dat elke berekening of gegevensbewerking die geprogrammeerd kan worden, ook in dit systeem geprogrammeerd kan worden. Het woord verwijst naar de wiskundige Alan Turing, die de turingmachine als algemene maatstaf van berekenbaarheid heeft uitgevonden. (nl) Turingkomplett är ett begrepp som lanserades av den brittiske matematikern Alan Turing (1912–1954). Ett programspråk anses vara turingkomplett då man kan beräkna samtliga beräkningsbara problem i det, givet tillräcklig tid och tillräckligt minnesutrymme. En maskin anses vara turingkomplett när den kan utföra de operationer som behövs för att kunna beräkna alla beräkningsbara problem som finns. Denna maskin är då en turingmaskin. I teorin kan en maskin som är turingkomplett exekvera samtliga programvaror för andra turingkompletta maskiner, förutsatt att programvaran skrivs om för den aktuella maskinens hårdvara, eller körs i en emulator. (sv) 在可计算性理论，如果一系列操作数据的规则（如指令集、编程语言、细胞自动机）可以用来模拟任何图灵机，那么它是图灵完备的。这意味着这个系统也可以识别其他数据处理规则集，图灵完备性被用作表达这种数据处理规则集的一种属性。如今，几乎所有编程语言都是具有图灵完备性的。这个词以引入图灵机概念的数学家艾伦·图灵命名。 还有一个相关概念是图灵等价 – 如果P可以模拟Q并且Q可以模拟P，则两台计算机P和Q称为等效计算机。 邱奇－图灵论题认为任何可以通过算法计算其值的函数都可以由图灵机计算，因此，如果任何真实世界的计算机都可以模拟图灵机，则其对图灵机是图灵等价的。 通用图灵机可用于模拟任何图灵机，且可以扩展现实世界计算机的计算方面。 如果某物是图灵完备的，则它可以用于模拟某些图灵完备的系统。例如，一个指令式编程具有条件表达式（例如，“ if”和“ goto”语句，或者“branch if zero”的指令；请参见单一指令计算机）并且具有更改任意指令的能力，则他为图灵完备的。 注意，虽然任何物理系统都不可能进行无限的迭代展开，但如果忽略了这一限制，则绝大多数物理系统都将是图灵完备的。 (zh) في نظرية الحاسوبية، يقال عن نظام قواعد التعامل مع البيانات (مثل مجموعة التعليمات لكمبيوتر، لغة البرمجة، أوخلايا ذاتية السلوك) بأنها كاملة حسب تورنغ أو عامة حسابيا إذا كان يمكن استخدامها لمحاكاة أي آلة تورنغ وحيدة الشريط. يستقى هذا المفهوم من عالم الرياضيات الإنجليزي آلان تورنغ. المثال التقليدي هو حساب لامدا. (ar) En la teoria d'ordinadors reals i imaginaris, dels llenguatges de programació i d'altres sistemes lògics, un sistema Turing complet és aquell que té un poder computacional equivalent a la màquina universal de Turing. En altres paraules, el sistema i la màquina universal de Turing poden emular-se entre si. Hi ha la hipòtesi que l'Univers és Turing complet (vegeu implicacions filosòfiques en la Tesi de Church-Turing i en Física digital). (ca) Turingovská úplnost je pojem z oboru teorie vyčíslitelnosti: Turingovsky kompletní, turingovsky úplný nebo turingovsky ekvivalentní (anglicky Turing-complete) je stroj (počítač), programovací jazyk, úloha nebo , který má stejnou výpočetní sílu jako Turingův stroj. Tato třída je důležitá proto, že není znám žádný způsob řešení úlohy, která je těžší (podle Churchovy–Turingovy teze žádné konečné zařízení víc spočítat nedokáže). Dá se tedy říct, že turingovsky kompletní stroj je tak univerzální, jak je jen možné (to ovšem neříká nic o efektivitě). Speciálně lze sestrojit univerzální Turingův stroj, který dokáže simulovat libovolný jiný Turingův stroj (zadaný na vstupu). (cs) Στη θεωρία υπολογισιμότητας, ένα σύστημα κανόνων διαχείρισης δεδομένων (όπως οι ομάδες εντολών του υπολογιστή, ή η γλώσσα προγραμματισμού ή ένα κυψελοειδές αυτόματο), λέγεται ότι είναι "Τούρινγκ {Turing} πλήρες" ή "υπολογιστικά καθολικό" αν μπορεί να χρησιμοποιηθεί για να προσομοιώσει οποιαδήποτε μηχανή Τούρινγκ. Αυτό σημαίνει, ότι αυτό το σύστημα είναι σε θέση να αναγνωρίσει ή να αποφασίσει άλλα σύνολα κανόνων χειρισμού δεδομένων. Αυτή η "πληρότητα Turing", χρησιμοποιείται ως ένας τρόπος έκφρασης της ισχύος ενός τέτοιου κανόνα διαχείρισης δεδομένων. Η δύναμη έκφρασης αυτών των "γραμματικών", καταγράφεται στην "". Πρακτικά, σχεδόν όλες οι γλώσσες προγραμματισμού, είναι σήμερα "Τούρινγκ πλήρεις". Η ονομασία της έννοιας αυτής είναι φόρος τιμής στον Άγγλο μαθηματικό και επιστήμονα πληροφορική (el) Turing kompleteco estas esprimo uzita en komputebleca teorio por priskribi abstraktajn maŝinojn, kutime nomitajn aŭtomatojn. Tia aŭtomato estas Turing-kompleta, se ĝi povas esti uzata por emuli Turing-maŝinon. Ĝi ankaŭ nomiĝas komputile universala. (eo) En la teoría de computadoras reales y virtuales, de los lenguajes de programación y de otros sistemas lógicos, un sistema Turing completo es aquel que tiene un poder computacional equivalente a la máquina de Turing universal. En otras palabras, el sistema y la máquina universal de Turing pueden emularse entre sí. Está la hipótesis de que el Universo es Turing completo (ver implicaciones filosóficas en la Tesis de Church-Turing y en Física digital). (es) En informatique et en logique, un système formel est dit complet au sens de Turing ou Turing-complet (par calque de l’anglais Turing-complete) s’il possède un pouvoir expressif au moins équivalent à celui des machines de Turing. Dans un tel système, il est donc possible de programmer n'importe quelle machine de Turing. Cette notion est rendue pertinente par la thèse de Church, qui postule l’existence d’une notion naturelle de calculabilité. Ainsi, le pouvoir expressif des machines de Turing coïncide avec celui des fonctions récursives, du lambda calcul, ou encore des machines à compteurs. (fr) In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Turing machine (devised by English mathematician and computer scientist Alan Turing). This means that this system is able to recognize or decide other data-manipulation rule sets. Turing completeness is used as a way to express the power of such a data-manipulation rule set. Virtually all programming languages today are Turing-complete. (en) Kompletność Turinga – cecha systemu przetwarzającego dane lub języka programowania, polegająca na tym, że można za jego pomocą rozwiązać identyczną klasę problemów obliczeniowych, jak na uproszczonym modelu programowalnego komputera zwanego maszyną Turinga. W praktyce oznacza to, że jeśli dany język, maszyna lub inny system potrafi wykonać lub wyrazić każdy algorytm, określany jest mianem zupełnego, przy czym nie jest wymagane, by algorytm ten realizowany był prosto, wydajnie bądź efektywnie. (pl) Полнота по Тьюрингу — характеристика исполнителя (множества вычисляющих элементов) в теории вычислимости, означающая возможность реализовать на нём любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных). (ru) Na teoria da computação, a completude de Turing ou Turing-completo (do inglês: Turing-completeness; batizado em memória de Alan Turing), também chamado computacionalmente universal, é um conjunto de regras para manipulação de dados (semelhante a uma linguagem de programação, um autómato celular, um conjunto de instruções) que pode ser usado para resolver qualquer problema de computação (simula a lógica de qualquer algoritmo de computador). este é completo ou universal se e somente se puder ser usado para controlar a máquina de Turing (a máquina digital primitiva e universal), e assim podendo controlar qualquer computador. Um exemplo clássico é o cálculo lambda (um sistema formal que estuda funções recursivas computáveis). (pt) У теорії алгоритмів набір правил маніпуляції даними (набір інструкцій, мова програмування чи клітинний автомат) вважається повним за Тюрінгом тоді і тільки тоді, коли цей набір може моделювати однострічкову машину Тюрінга. Класичними системами, що теж описуються простими правилами та є Тюрінг-повними, є контекстно-залежні граматики, рекурсивні функції та лямбда-числення. У теорії алгоритмів існує близький термін: Тюрінг-еквівалентність — два комп'ютери P та Q називаються Тюрінг-еквівалентними, якщо P може імітувати Q та Q може імітувати P. (uk) |
| rdfs:label | كمال تورنغ (ar) Turing complet (ca) Turingovská úplnost (cs) Turing-Vollständigkeit (de) Πληρότητα Τούρινγκ (el) Turing kompleteco (eo) Turing completo (es) Turing-complet (fr) Turing equivalenza (it) 튜링 완전 (ko) チューリング完全 (ja) Turingvolledigheid (nl) Kompletność Turinga (pl) Turing completude (pt) Полнота по Тьюрингу (ru) Turing completeness (en) Turingkomplett (sv) Повнота за Тюрінгом (uk) 圖靈完備性 (zh) |
| rdfs:seeAlso | dbr:Church–Turing_thesis |
| owl:sameAs | freebase:Turing completeness yago-res:Turing completeness wikidata:Turing completeness dbpedia-ar:Turing completeness dbpedia-bg:Turing completeness dbpedia-ca:Turing completeness dbpedia-cs:Turing completeness dbpedia-da:Turing completeness dbpedia-de:Turing completeness dbpedia-el:Turing completeness dbpedia-eo:Turing completeness dbpedia-es:Turing completeness dbpedia-fa:Turing completeness dbpedia-fi:Turing completeness dbpedia-fr:Turing completeness http://ia.dbpedia.org/resource/Turing_complete dbpedia-it:Turing completeness dbpedia-ja:Turing completeness dbpedia-ko:Turing completeness dbpedia-nl:Turing completeness dbpedia-nn:Turing completeness dbpedia-no:Turing completeness dbpedia-pl:Turing completeness dbpedia-pt:Turing completeness dbpedia-ru:Turing completeness dbpedia-simple:Turing completeness dbpedia-sr:Turing completeness dbpedia-sv:Turing completeness dbpedia-uk:Turing completeness dbpedia-zh:Turing completeness https://global.dbpedia.org/id/t9KD |
| prov:wasDerivedFrom | wikipedia-en:Turing_completeness?oldid=1124615103&ns=0 |
| foaf:homepage | http://wiki.c2.com |
| foaf:isPrimaryTopicOf | wikipedia-en:Turing_completeness |
| is dbo:wikiPageRedirects of | dbr:Non-Turing-complete_programming_language dbr:Turing_complete dbr:Turing_equivalence_(theory_of_computation) dbr:Turing-Complete dbr:Turing-complete_device dbr:Turing-complete_language dbr:Turing-complete_programming_language dbr:Turing-completeness dbr:Turing-powerful dbr:Turing_Complete dbr:Turing_complete_language dbr:Turing_completion dbr:Turing-complete dbr:Minimum_capability dbr:Computational_universality dbr:Computationally_universal dbr:List_of_turing_complete_video_games |
| is dbo:wikiPageWikiLink of | dbr:Casio_FX-602P_series dbr:Primitive_recursive_function dbr:Programming_paradigm dbr:Prolog dbr:Elementary_cellular_automaton dbr:Encryption dbr:List_of_atheists_in_science_and_technology dbr:MUD dbr:Non-Turing-complete_programming_language dbr:1941_in_science dbr:Befunge dbr:Brainfuck dbr:History_of_computing_hardware dbr:Paul_Graham_(programmer) dbr:Reversible_cellular_automaton dbr:Rhombille_tiling dbr:David_Morgan-Mar dbr:Decentralized_autonomous_organization dbr:Device_independent_file_format dbr:Inductive_programming dbr:Interpreter_(computing) dbr:List_of_programming_languages dbr:Potential_applications_of_carbon_nanotubes dbr:Crash_Bandicoot dbr:Cryptography dbr:Analytical_Engine dbr:Maximus_(BBS) dbr:General-purpose_macro_processor dbr:General-purpose_programming_language dbr:One-instruction_set_computer dbr:Turing_machine_equivalents dbr:Church–Turing_thesis dbr:Gisbert_Hasenjaeger dbr:Gottfried_Wilhelm_Leibniz dbr:Epsilon_(text_editor) dbr:Rule_110 dbr:Lisp_(programming_language) dbr:MOEA_Framework dbr:Manchester_Baby dbr:StarkWare_Industries dbr:Complexity dbr:Computer_program dbr:Hardware_security dbr:Physical_symbol_system dbr:Malbolge dbr:Turing_complete dbr:Mechanical_computer dbr:C_preprocessor dbr:Thue_(programming_language) dbr:Tiger_Electronics dbr:Timeline_of_scientific_discoveries dbr:Type_system dbr:Document_Structuring_Conventions dbr:Cryptoeconomics dbr:HP_33s dbr:List_of_CIL_instructions dbr:Prolog_syntax_and_semantics dbr:Adaptive_grammar dbr:Cuneiform_(programming_language) dbr:Curry–Howard_correspondence dbr:Datalog dbr:Ethereum dbr:Ethereum_Classic dbr:Carbon_nanotube_computer dbr:Cellular_automaton dbr:Church–Turing–Deutsch_principle dbr:History_of_computer_science dbr:Legacy_of_Alan_Turing dbr:Specification_and_Description_Language dbr:Turing_equivalence_(theory_of_computation) dbr:Quine_(computing) dbr:Hans_Hermes dbr:Hindley–Milner_type_system dbr:TeX dbr:Counter_machine dbr:A_New_Kind_of_Science dbr:Chinese_room dbr:John_Horton_Conway dbr:Lambda_calculus dbr:Binary_combinatory_logic dbr:BlooP_and_FlooP dbr:Code_golf dbr:Mobile_membranes dbr:Read-only_Turing_machine dbr:Register_machine dbr:Phyz dbr:Post–Turing_machine dbr:Konrad_Zuse dbr:Meson_(software) dbr:Microsoft_Small_Basic dbr:Minimum_message_length dbr:Nervos_Network dbr:Casio_FX-502P_series dbr:Casio_FX-603P dbr:Random-access_machine dbr:Recursion_(computer_science) dbr:XSLT dbr:The_Cathedral_and_the_Bazaar dbr:Matthew_Cook dbr:Model_of_computation dbr:Norman_Margolus dbr:Turing_machine dbr:Server_Side_Includes dbr:Universal_Turing_machine dbr:List_of_things_named_after_Alan_Turing dbr:List_of_unsolved_problems_in_mathematics dbr:Programming_language dbr:NP-completeness dbr:Natural_computing dbr:Structured_program_theorem dbr:Simple-As-Possible_computer dbr:Turing_reduction dbr:Peptide_computing dbr:Turing_tarpit dbr:Wolfram's_2-state_3-symbol_Turing_machine dbr:Src:Card dbr:Turing-Complete dbr:Turing-complete_device dbr:Turing-complete_language dbr:Turing-complete_programming_language dbr:Turing-completeness dbr:Turing-powerful dbr:Turing_Complete dbr:Turing_complete_language dbr:Turing_completion dbr:Turing-complete dbr:Turing_equivalence dbr:Minimum_capability dbr:Computational_universality dbr:Computationally_universal dbr:List_of_turing_complete_video_games |
| is rdfs:seeAlso of | dbr:Chinese_room |
| is foaf:primaryTopic of | wikipedia-en:Turing_completeness |