| 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)
|
| 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)
|
