Turing machine (original) (raw)

About DBpedia

Maŝinoj de Turing estas ekstreme simplaj simbol-manipulantaj aparatoj, kiuj — malgraŭ sia simpleco — povas esti adaptitaj por simuli la logikon de ajna komputilo, kiu eble povus esti foje konstruata (kvankam eble tre malefike). Ili estis priskribitaj en 1936 fare de Alan Turing. Maŝino de Turing, kiu kapablas simuli ajnan alian maŝinon de Turing, estas nomata universala maŝino de Turing (aŭ simple universala maŝino).

thumbnail

Property Value
dbo:abstract La màquina de Turing és un model computacional introduït per Alan Turing en el treball "On computable numbers, with an application to the Entscheidungsproblem", publicat per la Societat Matemàtica de Londres, en el qual s'estudiava la qüestió plantejada per David Hilbert sobre si les matemàtiques són decidibles, és a dir, si hi ha un mètode definit que pugui aplicar-se a qualsevol sentència matemàtica i que resolgui si és certa o no. Turing va construir un model formal de computador, la màquina de Turing, un dispositiu que manipula símbols sobre una tira de cinta d'acord amb una taula de regles i va demostrar que existien problemes que una màquina no podia resoldre. Malgrat la seva simplicitat, la màquina de Turing pot ser adaptada per simular la lògica de qualsevol algorisme de computador i és particularment útil en l'explicació de les funcions d'una CPU dins d'un computador. Originalment va ser definida com una «màquina automàtica» en 1936, a la revista de Londres. La màquina de Turing no està dissenyada com una tecnologia de computació pràctica, sinó com un dispositiu hipotètic que representa una màquina de computació, i van ajudar els científics a entendre els límits del càlcul mecànic. Turing va donar una definició succinta de l'experiment en el seu assaig de 1948, «Màquines intel·ligents». Referint-se a la seva publicació de 1936, Turing va escriure que la màquina de Turing, aquí anomenada una màquina de computació lògica, consistia en: Una màquina de Turing que sigui capaç de simular qualsevol altra màquina de Turing és anomenada com una màquina universal de Turing (UTM, o simplement una màquina universal). Una definició més matemàticament orientada, amb una semblant naturalesa "universal", va ser presentada per Alonzo Church, el treball sobre el càlcul lambda s'entrellaça amb el de Turing en una teoria formal de la computació coneguda com la tesi de Church-Turing. La tesi assenyala que les màquines de Turing capturen, de fet, la noció informal d'un mètode eficaç en la lògica i les matemàtiques i proporcionen una definició precisa d'un algoritme o 'procediment mecànic'. Estudiant les seves propietats abstractes, la màquina de Turing produeix moltes perspectives en les ciències de la computació i en la teoria de la complexitat. (ca) آلة تورنغ هي نموذج نظري بسيط يحاكي طريقة عمل الحاسوب. سميت بهذا الاسم نسبة لعالم الرياضيات الإنجليزي آلان تورنغ الذي أوجد هذا النموذج سنة 1936م. هذا النموذج يعطي تعريفا رياضيا دقيقا للمصطلح خوارزم Algorithm, أهمية هذا النموذج تكمن في بساطته مقارنة بجهاز الحاسوب المعقد وبالرغم من ذلك فهو قادر على تنفيذ كل خوارزمية قابلة للتنفيذ بواسطة أي حاسوب متطور. لذلك يمكن معرفة إذا كانت عملية معينة قابلة للتنفيذ بواسطة الحاسوب أم لا عن طريق فحصها بواسطة آلة تورنغ. من هنا فإن لآلة تورنغ استعمال واسع في مجال دراسة قدرة الحاسوب والعمليات التي يمكنه أو لا يمكنه تنفيذها، وهو ما يسمى علم قابلية الحساب.يعتبر نموذج آلة التورينغ نموذج رياضياً بسيطاً للحاسوب وينمذج المقدرة الحسابية لحاسوب ذي وظائف عمومية وهو أيضاً من أهم اللغات الصورية إذ يقبل أوسع مجموعة منها وهي اللغات القابلة للعد عمودياً والتي يمكن توليدها بنماذج قواعدية من النوع صفر. يتألف النموذج الأساسي لآلة التورينغ من تحكم منته وشريط دخل منته من جهة واحدة هي جهة اليسار وغير منته من جهة اليمين ومقسم إلى عدة خلايا كل منها يحمل رمزاً واحداً من مجموعة منتهية تسمى «رموز الشريط» ورأس يسمى رأس القراءة والكتابة الذي يمر في كل مرة على خلية واحدة من الشريط. تحتوي الخلايا الn اليسارية من شريط الدخل (n عدد منته)في الحالة الابتدائية رموز الدخلفي حين تحتوي الخلايا المتبقة من الشريط رمزاً فارغاً. تقوم آلة التورينغ في الحركة الواحدة واعتماداً على رمز الدخل المقروء من شريط الدخل وحالة التحكم المنتهي بالعمليات التالية: * تغيير حالة التحكم المنتهي. * كتابة رمز شريط في الخلية المقروءة. * التحرك خلية واحدة إلى اليسار أو إلى اليمين أو عدم التحرك بتاتا. (ar) Turingův stroj (TS) je teoretický model počítače popsaný matematikem Alanem Turingem, který se používá pro modelování algoritmů v teorii vyčíslitelnosti. Skládá se z řídicí jednotky s konečným počtem stavů, konečné množiny pravidel, která definují přechodovou funkci, a pravostranně nekonečné pásky pro vstup a zápis mezivýsledků. Jeden ze způsobu vyjádření Churchovy–Turingovy teze říká, že ke každému algoritmu existuje ekvivalentní Turingův stroj. Od výpočetní síly Turingova stroje se odvozuje turingovská úplnost: turingovsky úplné jsou právě ty programovací jazyky nebo počítače, které mají stejnou výpočetní sílu jako Turingův stroj. (cs) Η Μηχανή Τούρινγκ είναι μια υποθετική συσκευή η οποία χειρίζεται σύμβολα σύμφωνα με ένα σύνολο κανόνων. Παρά την απλότητά της, μια Μηχανή Τούρινγκ μπορεί να προσαρμοστεί ώστε να προσομοιώνει την λογική οποιουδήποτε αλγορίθμου, και είναι ιδιαίτερα χρήσιμη στο να εξηγεί τις λειτουργίες μιας κεντρικής μονάδας επεξεργασίας στο εσωτερικό του υπολογιστή. Η μηχανή του Τούρινγκ εφευρέθηκε το 1936 από τον Άλαν Τούρινγκ. Η μηχανή Τούρινγκ δεν προορίζεται σαν μια τεχνολογία υπολογιστών αλλά κυρίως σαν μια υποθετική κατασκευή που αντιπροσωπεύει μια υπολογιστική μηχανή. Οι μηχανές Τούρινγκ βοηθούν τους επιστήμονες να καταλάβουν τα όρια του μηχανικού υπολογισμού. Ο Τούρινγκ έδωσε έναν περιληπτικό ορισμό του πειράματος στην έκθεση του, "Ευφυή μηχανήματα". Έγραψε ότι η μηχανή Τούρινγκ, που εδώ ονομάζεται μια Λογική Υπολογιστική Μηχανή, αποτελείται από: ....απεριόριστη χωρητικότητα μνήμης, σε μορφή μιας άπειρης ταινίας η οποία είναι χωρισμένη σε τετράγωνα, πάνω στο καθένα από οποία μπορεί να εκτυπωθεί ένα σύμβολο. Κάθε στιγμή, υπάρχει ένα σύμβολο στη μηχανή και ονομάζεται το σκαναριζόμενο σύμβολο. Η μηχανή μπορεί να μεταβάλλει το σκαναριζόμενο σύμβολο και η συμπεριφορά της είναι εν μέρει αποφαση αυτού του συμβόλου, αλλά τα σύμβολα σε άλλα σημεία της ταινίας δεν επηρεάζουν την συμπεριφορά της. Μια μηχανή Τούρινγκ που μπορεί να προσομοιώσει μια οποιαδήποτε άλλη μηχανή Τούρινγκ λέγεται Καθολική Μηχανή Τούρινγκ (ή απλά καθολική μηχανή). Ένας πιο μαθηματικός ορισμός με παρόμοια "καθολική" φύση τέθηκε από τον Αλόνζο Τσερτς, του οποίου η εργασία πάνω στο λογισμό λάμδα συνυφαίνεται με αυτή του Τούρινγκ σε μια τυπική θεωρία υπολογισμού που είναι γνωστή ως η . Η θέση λέει ότι οι μηχανές Τούρινγκ όντως εμπεριέχουν την ανεπίσημη έννοια της αποδοτικής μεθόδου στη λογική και τα μαθηματικά, και δίνουν έναν ακριβή ορισμό ενός αλγορίθμου ή μιας μηχανικής διαδικασίας. (el) Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert. Bei diesem Rechnermodell werden nach festgelegten Regeln Manipulationen von Zeichen vorgenommen. Die Turingmaschine ist benannt nach dem britischen Mathematiker Alan Turing, der sie 1936/37 einführte. Turingmaschinen machen die Begriffe des Algorithmus und der Berechenbarkeit mathematisch fassbar, das heißt, sie formalisieren diese Begriffe. Im Gegensatz zu einem physischen Computer ist eine Turingmaschine damit ein mathematisches Objekt und kann mit mathematischen Methoden untersucht werden. Eine Turingmaschine repräsentiert einen Algorithmus bzw. ein Programm. Eine Berechnung besteht dabei aus schrittweisen Manipulationen von Symbolen bzw. Zeichen, die nach bestimmten Regeln auf ein Speicherband geschrieben und auch von dort gelesen werden. Ketten dieser Symbole können verschieden interpretiert werden, unter anderem als Zahlen. Damit beschreibt eine Turingmaschine eine Funktion, welche Zeichenketten, die anfangs auf dem Band stehen, auf Zeichenketten, die nach „Bearbeitung“ durch die Maschine auf dem Band stehen, abbildet. Eine Funktion, die anhand einer Turingmaschine berechnet werden kann, wird Turing-berechenbar oder auch einfach berechenbar genannt. Turingmaschinen spielen auch eine bedeutende Rolle bei der Akzeptanz von formalen Sprachen.So entsprechen die Sprachen, die von Turingmaschinen akzeptiert werden, den mit Typ-0-Grammatiken definierbaren Sprachen. Eine Sprache oder ein Computersystem heißen Turing-vollständig, wenn es alle Operationen ausführen kann, die eine universelle Turingmaschine ausführen kann. (de) Maŝinoj de Turing estas ekstreme simplaj simbol-manipulantaj aparatoj, kiuj — malgraŭ sia simpleco — povas esti adaptitaj por simuli la logikon de ajna komputilo, kiu eble povus esti foje konstruata (kvankam eble tre malefike). Ili estis priskribitaj en 1936 fare de Alan Turing. Maŝino de Turing, kiu kapablas simuli ajnan alian maŝinon de Turing, estas nomata universala maŝino de Turing (aŭ simple universala maŝino). (eo) Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una CPU dentro de un computador. Originalmente fue definida por el matemático inglés Alan Turing como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Society​. La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico.​​ Turing dio una definición sucinta del experimento en su ensayo de 1948, «Máquinas inteligentes». Refiriéndose a su publicación de 1936, Turing escribió que la máquina de Turing, aquí llamada una máquina de computación lógica, consistía en: ... una ilimitada capacidad de memoria obtenida en la forma de una cinta infinita marcada con cuadrados, en cada uno de los cuales podría imprimirse un símbolo. En cualquier momento hay un símbolo en la máquina; llamado el símbolo leído. La máquina puede alterar el símbolo leído y su comportamiento está en parte determinado por ese símbolo, pero los símbolos en otros lugares de la cinta no afectan el comportamiento de la máquina. Sin embargo, la cinta se puede mover hacia adelante y hacia atrás a través de la máquina, siendo esto una de las operaciones elementales de la máquina. Por lo tanto cualquier símbolo en la cinta puede tener finalmente una oportunidad.​ Una máquina de Turing que es capaz de simular cualquier otra máquina de Turing es llamada una máquina universal de Turing (UTM, o simplemente una máquina universal). Una definición más matemáticamente orientada, con una similar naturaleza "universal", fue presentada por Alonzo Church, cuyo trabajo sobre el cálculo lambda se entrelaza con el de Turing en una teoría formal de la computación conocida como la tesis de Church-Turing. La tesis señala que las máquinas de Turing capturan, de hecho, la noción informal de un método eficaz en la lógica y las matemáticas y proporcionan una definición precisa de un algoritmo o 'procedimiento mecánico'. La importancia de la máquina de Turing en la historia de la computación es doble: primero, la máquina de Turing fue uno de los primeros (si no el primero) modelos teóricos para las computadoras, viendo la luz en 1936. Segundo, estudiando sus propiedades abstractas, la máquina de Turing ha servido de base para mucho desarrollo teórico en las ciencias de la computación y en la teoría de la complejidad. Una razón para esto es que las máquinas de Turing son simples, y por tanto amenas al análisis. Dicho esto, cabe aclarar que las máquinas de Turing no son un modelo práctico para la computación en máquinas reales, las cuales precisan modelos más rápidos como los basados en RAM. (es) Turing-en makina edo Turing makina bat definitzen duen konputaziozko modelo matematikoa da, erregela - taula baten arabera zinta tira baten gainean sinboloak manipulatzen dituena. Sinplea bada ere, Turing makina edozein konputazio-algoritmo simulatzeko egokitua izan daiteke. Turing makina ordenagailu batek egindako datu-manipulazio guztia kontrolatzen duen prozesamendu unitate zentral (PUZ) baten adibide orokor bat da, makina kanonikoarekin datuak biltzeko memoria sekuentziala erabiliz. Zehazkiago, alfabeto baten kate baliodunen azpimultzo arbitrarioren bat zerrendatzeko gai den makina — automata — bat da. Kateak modu mugikorrean zerrendatu daitekeen multzo baten zati dira. Turing-en makinak luzera infinituko zinta bat du, non irakurtzeko eta idazteko eragiketak egin ditzakeen. (eu) Mesin Turing adalah model komputasi teoretis yang ditemukan oleh Alan Turing, berfungsi sebagai model ideal untuk melakukan perhitungan matematis. Walaupun model ideal ini diperkenalkan sebelum komputer nyata dibangun, model ini tetap diterima kalangan ilmu komputer sebagai model komputer yang sesuai untuk menentukan apakah suatu fungsi dapat selesaikan oleh komputer atau tidak (menentukan computable function). Mesin Turing terkenal dengan ungkapan " Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa dilakukan oleh komputer." Sebuah mesin turing terdiri atas barisan sel tersusun berupa pita yang dapat bergerak maju mundur, komponen aktif baca/tulis pita yang memiliki status perhitungan serta dapat mengubah/menulisi sel aktif yang ada di pita tadi, dan suatu kumpulan instruksi bagaimana komponen baca/tulis ini harus melakukan modifikasi terhadap sel aktif pada pita, serta bagaimana menggerakkan pita tersebut. Pada setiap langkah dalam komputasi, mesin ini akan dapat mengubah isi dari sel yang aktif, mengubah status dari komponen baca/tulis, dan mengubah posisi pita ke kiri atau ke kanan. (in) En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur. Ce modèle a été imaginé par Alan Turing en 1936, en vue de donner une définition précise au concept d’algorithme ou de « procédure mécanique ».Il est toujours largement utilisé en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité. À l'origine, le concept de machine de Turing, inventé avant l'ordinateur, était censé représenter une personne virtuelle exécutant une procédure bien définie, en changeant le contenu des cases d'un ruban infini, en choisissant ce contenu parmi un ensemble fini de symboles. D'autre part, à chaque étape de la procédure, la personne doit se placer dans un état particulier parmi un ensemble fini d'états. La procédure est formulée en termes d'étapes élémentaires du type : « si vous êtes dans l'état 42 et que le symbole contenu sur la case que vous regardez est « 0 », alors remplacer ce symbole par un « 1 », passer dans l'état 17, et regarder maintenant la case adjacente à droite ». La thèse de Church postule que tout problème de calcul fondé sur une procédure algorithmique peut être résolu par une machine de Turing. Cette thèse n'est pas un énoncé mathématique, puisqu'elle ne suppose pas une définition précise des procédures algorithmiques. En revanche, il est possible de définir une notion de « système acceptable de programmation » et de démontrer que le pouvoir de tels systèmes est équivalent à celui des machines de Turing (ils sont Turing-complets). (fr) チューリングマシン (英: Turing machine) は、アラン・チューリングが「計算可能性」に関する議論のために提示した抽象機械である。 (ja) A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algorithm. The machine operates on an infinite memory tape divided into discrete cells, each of which can hold a single symbol drawn from a finite set of symbols called the alphabet of the machine. It has a "head" that, at any point in the machine's operation, is positioned over one of these cells, and a "state" selected from a finite set of states. At each step of its operation, the head reads the symbol in its cell. Then, based on the symbol and the machine's own present state, the machine writes a symbol into the same cell, and moves the head one step to the left or the right, or halts the computation. The choice of which replacement symbol to write and which direction to move is based on a finite table that specifies what to do for each combination of the current state and the symbol that is read. The Turing machine was invented in 1936 by Alan Turing, who called it an "a-machine" (automatic machine). It was Turing's Doctoral advisor, Alonzo Church, who later coined the term "Turing machine" in a review. With this model, Turing was able to answer two questions in the negative: * Does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g., freezes, or fails to continue its computational task)? * Does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol? Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the uncomputability of the Entscheidungsproblem ('decision problem'). Turing machines proved the existence of fundamental limitations on the power of mechanical computation. While they can express arbitrary computations, their minimalist design makes them unsuitable for computation in practice: real-world computers are based on different designs that, unlike Turing machines, use random-access memory. Turing completeness is the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete if the limitations of finite memory are ignored. (en) ( 인공지능의 정도를 판별하는 테스트에 대해서는 튜링 테스트 문서를 참고하십시오.) 수학 또는 이론 전산학에서 튜링 기계(영어: Turing machine)는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이다. 상당히 간단해 보이지만 이 기계는 적당한 규칙과 기호를 입력한다면 일반적인 컴퓨터의 알고리즘을 수행할 수 있으며 컴퓨터 CPU의 기능을 설명하는데 상당히 유용하다. 1936년 앨런 튜링은 계산하는 기계를 대표할 수 있는 가상의 장치를 만들었고이 장치에 영어 단어인 automatic의 a를 따서 "a-기계"라는 이름을 붙였다. 이 기계가 바로 나중에 창시자인 앨런 튜링의 이름을 따서 튜링 기계라 불리게 되었다. 1948년 "똑똑한 기계"라는 글에서 앨런 튜링은 자신의 "a-기계"를 간결히 정의하였다. 1936년 논문 "계산 가능한 수와 결정성 문제에의 응용"을 언급하며 튜링기계(이 글에서는 논리적 계산 기계라는 표현을 사용한다.)를 다음과 같이 기술하였다. (ko) In informatica, una macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite. In altre parole, si tratta di un modello astratto che definisce una macchina in grado di eseguire algoritmi e dotata di un nastro potenzialmente infinito su cui può leggere e/o scrivere dei simboli. Introdotta nel 1936 da Alan Turing come modello di calcolo per dare risposta all'Entscheidungsproblem (problema di decisione) proposto da Hilbert nel suo programma di fondazione formalista della matematica, è un potente strumento teorico che viene largamente usato nella teoria della calcolabilità e nello studio della complessità degli algoritmi, in quanto è di notevole aiuto agli studiosi nel comprendere i limiti del calcolo meccanico; la sua importanza è tale che oggi, per definire in modo formalmente preciso la nozione di algoritmo, si tende a ricondurlo alle elaborazioni effettuabili con macchine di Turing. (it) Maszyna Turinga – stworzony przez Alana Turinga abstrakcyjny model urządzenia służącego do wykonywania algorytmów. Maszyna składa się z bloku sterowania, głowicy odczytującej i zapisującej oraz nieskończenie długiej taśmy. W każdej komórce taśmy może mieścić się jeden symbol. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z Q stanów. Zależnie od kombinacji stanu maszyny i symbolu napotkanego na taśmie maszyna zapisuje nową wartość w polu, zmienia stan, a następnie może przesunąć się o jedno pole w prawo lub w lewo. Taka operacja nazywana jest rozkazem. Maszyna Turinga jest sterowana listą zawierającą dowolną liczbę takich rozkazów. Czasem dopuszcza się też stan M+1, który oznacza zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga może być traktowana jako jej program. (pl) In de informatica is de turingmachine een model van berekening en berekenbaarheid, ontwikkeld door de wiskundige Alan M. Turing in zijn beroemde artikel On computable numbers, with an application to the Entscheidungsproblem uit 1936-37. De turingmachine is een eenvoudig mechanisme dat symbolen manipuleert. Ondanks deze eenvoud kan men hiermee de logica van elke mogelijke computer simuleren. Hoewel technisch realiseerbaar (zo lang we willekeurige hoeveelheden band kunnen aanleveren) is deze machine niet bedoeld voor praktische computertechnologie, maar als een gedachte-experiment rond de limieten van mechanische berekeningen; ze wordt dus niet echt gebouwd. (nl) En Turingmaskin är en teoretisk modell för att utföra beräkningar. Den utvecklades av matematikern Alan Turing år 1936. Syftet med Turingmaskinen är att betrakta algoritmiska lösningars gränser. En Turingmaskin konstrueras för att lösa ett givet problem, medan den universella Turingmaskinen kan lösa vilket problem som helst. Man kan alltså tänka sig Turingmaskinen som ett datorprogram som utför ett visst program, medan den universella Turingmaskinen kan tänkas som programmerbar. Enligt Church-Turings hypotes kan alla tänkbara beräkningsprocesser utföras av en Turingmaskin. Med andra ord är det den mest kraftfulla beräkningsmekanismen som existerar. Denna tes är inte i strikt matematisk mening bevisad, men allmänt accepterad som sann. Teorierna som Alan Turing skapade, samt den teoretiska Turingmaskinen, har haft en stor betydelse i utvecklingen och konstruktionen av de första datorerna. Alla moderna datorer kan dessutom simuleras med en Turingmaskin. Alan Turings teorier har också en viktig roll inom den matematiska logiken. (sv) A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em 1936).Num sentido preciso, é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento (memória, estados e transições), e não a sua implementação física. Numa máquina de Turing pode-se modelar qualquer computador digital. Turing também se envolveu na construção de máquinas físicas para quebrar os códigos secretos das comunicações alemãs durante a Segunda Guerra Mundial, tendo utilizado alguns dos conceitos teóricos desenvolvidos para o seu modelo de computador universal. (pt) Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать всех исполнителей (с помощью задания правил перехода), каким-либо образом реализующих процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен. То есть всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга. (ru) Маши́на Тю́рінга — математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму. Названа на честь англійського математика Алана Тюрінга, який запропонував це поняття у 1936. Аналогічну конструкцію машини згодом і незалежно від Тюрінга ввів американський математик Еміль Пост. Основна ідея, що лежить в основі машини Тюрінга, дуже проста. Машина Тюрінга — це абстрактна машина (автомат), що працює зі стрічкою, що складається із окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок і яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ із комірки, на яку вказує голівка та, на основі зчитаного символу та внутрішнього стану, робиться наступний крок. При цьому, машина може змінити свій стан, записати інший символ у комірку або пересунути голівку на одну комірку ліворуч або праворуч. (uk) 图灵机（英語：Turing machine），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种將人的計算行為抽象化的，其更抽象的意义为一种计算模型，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。 (zh)
dbo:thumbnail wiki-commons:Special:FilePath/Turing_Machine_Model_Davey_2012.jpg?width=300
dbo:wikiPageExternalLink http://www.theannotatedturing.com/ http://demonstrations.wolfram.com/TuringMachineCausalNetworks/ https://archive.org/details/introductiontoth00sips http://www.cs.princeton.edu/theory/complexity/ https://archive.org/details/computabilitylog0000bool_r8y9 http://www.machinedeturing.com/ang_default.asp http://www.nature.com/news/2007/071024/full/news.2007.190.html http://www.wolframscience.com/nksonline/page-707 http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf http://forum.wolframscience.com/showthread.php%3Fs=&threadid=1472 http://researchprofiles.herts.ac.uk/portal/en/publications/on-undecidability-results-of-real-programming-languages(d3f3aac0-d9da-4756-a421-b4f9ae0cf95f).html http://cs.nyu.edu/pipermail/fom/2007-October/012132.html http://cs.nyu.edu/pipermail/fom/2007-October/012140.html http://cs.nyu.edu/pipermail/fom/2007-October/012145.html http://cs.nyu.edu/pipermail/fom/2007-October/012156.html http://cs.nyu.edu/pipermail/fom/2007-October/012163.html http://research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf https://archive.org/details/mathematicaltour00pete https://archive.org/details/turingcomputer00stra https://web.archive.org/web/20050308141040/http:/www.imt.ro/Romjist/Volum1/Vol1_3/turing.htm https://www.newscientist.com/article/dn12826-simplest-universal-computer-wins-student-25000.html http://plato.stanford.edu/entries/turing-machine/
dbo:wikiPageID 30403 (xsd:integer)
dbo:wikiPageLength 74184 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1124751125 (xsd:integer)
dbo:wikiPageWikiLink dbr:Bekenstein_bound dbr:Pushdown_automaton dbr:Robin_Gandy dbr:Roger_Penrose dbr:Entscheidungsproblem dbr:Nondeterministic_Turing_machine dbr:Nondeterministic_finite_automaton dbr:Hartley_Rogers,_Jr. dbr:David_Hilbert dbr:Deterministic_finite_automaton dbr:Algorithm dbr:Percy_Ludgate dbr:Peter_van_Emde_Boas dbc:Educational_abstract_machines dbr:Unbounded_nondeterminism dbr:Vannevar_Bush dbr:Decidability_(logic) dbr:EDVAC dbr:Input/output_automaton dbr:Interactivity dbr:Systems_of_Logic_Based_on_Ordinals dbr:LIFO_(computing) dbr:Computability dbr:Computable_function dbr:Computer dbr:Computer_algorithm dbr:Mathematics dbr:Memory_allocation dbr:Genetix dbr:Louis_Couffignal dbr:Oracle_machine dbr:Out_of_memory dbr:Church–Turing_thesis dbr:Claude_Shannon dbr:Enumeration dbr:George_Stibitz dbr:Modified_Harvard_architecture dbr:Concurrency_(computer_science) dbr:Conway's_Game_of_Life dbc:Turing_machine dbr:Andrew_Hodges dbr:Arithmetical_hierarchy dbr:Batch_processing dbr:Leonardo_Torres_y_Quevedo dbr:Analytical_engine dbr:Logarithm dbr:Logic dbr:Simon_and_Schuster dbr:Stanford_Encyclopedia_of_Philosophy dbr:Stephen_Cole_Kleene dbr:Stephen_Hawking dbr:Stephen_Kleene dbr:Stephen_Wolfram dbr:Completeness_(logic) dbr:Computation dbr:Computational_complexity_theory dbr:Computer_science dbr:Zohar_Manna dbr:Partial_function dbr:Theory_of_computation dbr:Busy_beaver dbc:1936_in_computing dbc:1937_in_computing dbr:Tuple dbr:Turing's_proof dbr:Heinrich_Behmann dbr:Langton's_ant dbr:Linear_bounded_automaton dbr:Turing_switch dbr:Multi-track_Turing_machine dbr:JACM dbr:Unrestricted_grammar dbr:Alan_Turing dbr:Alonzo_Church dbr:Alphabet_(formal_languages) dbr:Finite_set dbr:First-order_logic dbr:Non-deterministic_Turing_machine dbr:Oxford_University_Press dbr:Pascal_(programming_language) dbr:Central_processing_unit dbr:Church-Turing_thesis dbr:Discrete_mathematics dbr:Goto dbr:Enumerator_(in_theoretical_computer_science) dbr:Wolfram_Demonstrations_Project dbr:Quantum_Turing_machine dbr:Halting_problem dbr:Hao_Wang_(academic) dbr:Harvard_architecture dbr:Hilbert's_problems dbr:Jack_Copeland dbr:Jan_van_Leeuwen dbr:Jeffrey_Ullman dbr:Counter_machine dbr:Turmite dbr:The_Emperor's_New_Mind dbr:Assembly_language dbr:ANSI_C dbc:English_inventions dbc:Formal_methods dbc:Theoretical_computer_science dbr:Abstract_machine dbc:Abstract_machines dbc:Automata_(computation) dbc:Computability_theory dbc:Formal_languages dbc:Models_of_computation dbr:Charles_Babbage dbr:Charles_Petzold dbr:Chinese_room dbr:Alan_Turing:_The_Enigma dbc:Alan_Turing dbr:John_Hopcroft dbr:King's_College,_Cambridge dbr:Lambda_calculus dbr:Black_box dbr:BlooP_and_FlooP dbr:Effective_method dbr:Register_machine dbr:Digital_infinity dbr:Diophantine_equation dbr:Automatic_Computing_Engine dbr:Automaton dbr:Martin_Davis_(mathematician) dbr:Marvin_Minsky dbr:Post–Turing_machine dbr:Konrad_Zuse dbr:Kurt_Gödel dbr:Cantor's_diagonal_argument dbr:Random-access_machine dbr:Random-access_memory dbr:Random-access_stored-program_machine dbr:Read-only_right_moving_Turing_machines dbr:Recursively_enumerable_set dbr:Chaitin's_constant dbr:World_War_II dbr:Universal_Turing_machine dbr:Von_Neumann_architecture dbr:Imperative_programming dbr:List_of_things_named_after_Alan_Turing dbr:Programming_language dbr:Stored-program_computer dbr:Finite-state_machine dbr:Multi-tape_Turing_machine dbr:Turing_tarpit dbr:Unorganized_machine dbr:Turing_machine_examples dbr:Turing_completeness dbr:Relays dbr:Electronic_computer dbr:Computer_storage dbr:J._B._Rosser dbr:Turing's_Thesis dbr:Turing_computable dbr:State_transition_system dbr:SIGACT_News dbr:Emil_Post dbr:Taylor_L._Booth dbr:Effective_calculability dbr:Mathematical_model_of_computation dbr:Maurice_d'Ocagne dbr:R._E._Stearns dbr:Consistency_proof dbr:NDFA_to_DFA_conversion_algorithm dbr:Recursion_theory dbr:Howard_Aiken dbr:Gödel,_Escher,_Bach:_An_Eternal_Golden_Braid dbr:Gödel_number dbr:M._H._A._Newman dbr:Binary_search dbr:Omega_(computer_science) dbr:On_Computable_Numbers,_with_an_Application_to_the_Entscheidungsproblem dbr:File:Turing_machine_2b.svg dbr:File:Busy_Beaver_3_State.png dbr:File:Lego_Turing_Machine.jpg dbr:File:Model_of_a_Turing_machine.jpg dbr:File:Moves_of_a_3-state_Busy_Beaver.jpg dbr:File:State_diagram_3_state_busy_beaver_2B.svg dbr:File:Turing_Machine_Model_Davey_2012.jpg dbr:File:Turing_machine_2a.svg dbr:File:Turingmachine.jpg dbr:Mathematical_Theory_of_Computation dbr:Rolf_Herken
dbp:id p/t094460 (en)
dbp:title Turing machine (en)
dbp:wikiPageUsesTemplate dbt:Springer dbt:= dbt:Authority_control dbt:CNone dbt:Citation_needed dbt:Citation_style dbt:Cite_book dbt:Cite_journal dbt:Commons_category dbt:Curlie dbt:Dubious dbt:For dbt:Further dbt:Harvtxt dbt:Main dbt:Other_uses dbt:Quote dbt:Reflist dbt:See_also dbt:Short_description dbt:Unreferenced_section dbt:Whom dbt:Isbn dbt:Turing dbt:Mathematical_logic dbt:Divcol dbt:CEmpty dbt:Divcol-end dbt:Alan_Turing dbt:Formal_languages_and_grammars dbt:Automata_theory
dct:subject dbc:Educational_abstract_machines dbc:Turing_machine dbc:1936_in_computing dbc:1937_in_computing dbc:English_inventions dbc:Formal_methods dbc:Theoretical_computer_science dbc:Abstract_machines dbc:Automata_(computation) dbc:Computability_theory dbc:Formal_languages dbc:Models_of_computation dbc:Alan_Turing
gold:hypernym dbr:Machine
rdf:type owl:Thing dbo:Software yago:Ability105616246 yago:Abstraction100002137 yago:Cognition100023271 yago:Creativity105624700 yago:Invention105633385 yago:Know-how105616786 yago:Method105660268 yago:PsychologicalFeature100023100 yago:WikicatEnglishInventions yago:WikicatFormalMethods
rdfs:comment Maŝinoj de Turing estas ekstreme simplaj simbol-manipulantaj aparatoj, kiuj — malgraŭ sia simpleco — povas esti adaptitaj por simuli la logikon de ajna komputilo, kiu eble povus esti foje konstruata (kvankam eble tre malefike). Ili estis priskribitaj en 1936 fare de Alan Turing. Maŝino de Turing, kiu kapablas simuli ajnan alian maŝinon de Turing, estas nomata universala maŝino de Turing (aŭ simple universala maŝino). (eo) チューリングマシン (英: Turing machine) は、アラン・チューリングが「計算可能性」に関する議論のために提示した抽象機械である。 (ja) ( 인공지능의 정도를 판별하는 테스트에 대해서는 튜링 테스트 문서를 참고하십시오.) 수학 또는 이론 전산학에서 튜링 기계(영어: Turing machine)는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이다. 상당히 간단해 보이지만 이 기계는 적당한 규칙과 기호를 입력한다면 일반적인 컴퓨터의 알고리즘을 수행할 수 있으며 컴퓨터 CPU의 기능을 설명하는데 상당히 유용하다. 1936년 앨런 튜링은 계산하는 기계를 대표할 수 있는 가상의 장치를 만들었고이 장치에 영어 단어인 automatic의 a를 따서 "a-기계"라는 이름을 붙였다. 이 기계가 바로 나중에 창시자인 앨런 튜링의 이름을 따서 튜링 기계라 불리게 되었다. 1948년 "똑똑한 기계"라는 글에서 앨런 튜링은 자신의 "a-기계"를 간결히 정의하였다. 1936년 논문 "계산 가능한 수와 결정성 문제에의 응용"을 언급하며 튜링기계(이 글에서는 논리적 계산 기계라는 표현을 사용한다.)를 다음과 같이 기술하였다. (ko) Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать всех исполнителей (с помощью задания правил перехода), каким-либо образом реализующих процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен. То есть всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга. (ru) 图灵机（英語：Turing machine），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种將人的計算行為抽象化的，其更抽象的意义为一种计算模型，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。 (zh) آلة تورنغ هي نموذج نظري بسيط يحاكي طريقة عمل الحاسوب. سميت بهذا الاسم نسبة لعالم الرياضيات الإنجليزي آلان تورنغ الذي أوجد هذا النموذج سنة 1936م. هذا النموذج يعطي تعريفا رياضيا دقيقا للمصطلح خوارزم Algorithm, أهمية هذا النموذج تكمن في بساطته مقارنة بجهاز الحاسوب المعقد وبالرغم من ذلك فهو قادر على تنفيذ كل خوارزمية قابلة للتنفيذ بواسطة أي حاسوب متطور. لذلك يمكن معرفة إذا كانت عملية معينة قابلة للتنفيذ بواسطة الحاسوب أم لا عن طريق فحصها بواسطة آلة تورنغ. من هنا فإن لآلة تورنغ استعمال واسع في مجال دراسة قدرة الحاسوب والعمليات التي يمكنه أو لا يمكنه تنفيذها، وهو ما يسمى علم قابلية الحساب.يعتبر نموذج آلة التورينغ نموذج رياضياً بسيطاً للحاسوب وينمذج المقدرة الحسابية لحاسوب ذي وظائف عمومية وهو أيضاً من أهم اللغات الصورية إذ يقبل أوسع مجموعة منها وهي اللغات القابلة للعد عمودياً والتي يمكن توليدها ب (ar) La màquina de Turing és un model computacional introduït per Alan Turing en el treball "On computable numbers, with an application to the Entscheidungsproblem", publicat per la Societat Matemàtica de Londres, en el qual s'estudiava la qüestió plantejada per David Hilbert sobre si les matemàtiques són decidibles, és a dir, si hi ha un mètode definit que pugui aplicar-se a qualsevol sentència matemàtica i que resolgui si és certa o no. Turing va construir un model formal de computador, la màquina de Turing, un dispositiu que manipula símbols sobre una tira de cinta d'acord amb una taula de regles i va demostrar que existien problemes que una màquina no podia resoldre. (ca) Turingův stroj (TS) je teoretický model počítače popsaný matematikem Alanem Turingem, který se používá pro modelování algoritmů v teorii vyčíslitelnosti. Skládá se z řídicí jednotky s konečným počtem stavů, konečné množiny pravidel, která definují přechodovou funkci, a pravostranně nekonečné pásky pro vstup a zápis mezivýsledků. Jeden ze způsobu vyjádření Churchovy–Turingovy teze říká, že ke každému algoritmu existuje ekvivalentní Turingův stroj. (cs) Η Μηχανή Τούρινγκ είναι μια υποθετική συσκευή η οποία χειρίζεται σύμβολα σύμφωνα με ένα σύνολο κανόνων. Παρά την απλότητά της, μια Μηχανή Τούρινγκ μπορεί να προσαρμοστεί ώστε να προσομοιώνει την λογική οποιουδήποτε αλγορίθμου, και είναι ιδιαίτερα χρήσιμη στο να εξηγεί τις λειτουργίες μιας κεντρικής μονάδας επεξεργασίας στο εσωτερικό του υπολογιστή. Ο Τούρινγκ έδωσε έναν περιληπτικό ορισμό του πειράματος στην έκθεση του, "Ευφυή μηχανήματα". Έγραψε ότι η μηχανή Τούρινγκ, που εδώ ονομάζεται μια Λογική Υπολογιστική Μηχανή, αποτελείται από: (el) Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert. Bei diesem Rechnermodell werden nach festgelegten Regeln Manipulationen von Zeichen vorgenommen. Die Turingmaschine ist benannt nach dem britischen Mathematiker Alan Turing, der sie 1936/37 einführte. (de) Turing-en makina edo Turing makina bat definitzen duen konputaziozko modelo matematikoa da, erregela - taula baten arabera zinta tira baten gainean sinboloak manipulatzen dituena. Sinplea bada ere, Turing makina edozein konputazio-algoritmo simulatzeko egokitua izan daiteke. (eu) Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una CPU dentro de un computador. Turing dio una definición sucinta del experimento en su ensayo de 1948, «Máquinas inteligentes». Refiriéndose a su publicación de 1936, Turing escribió que la máquina de Turing, aquí llamada una máquina de computación lógica, consistía en: (es) Mesin Turing adalah model komputasi teoretis yang ditemukan oleh Alan Turing, berfungsi sebagai model ideal untuk melakukan perhitungan matematis. Walaupun model ideal ini diperkenalkan sebelum komputer nyata dibangun, model ini tetap diterima kalangan ilmu komputer sebagai model komputer yang sesuai untuk menentukan apakah suatu fungsi dapat selesaikan oleh komputer atau tidak (menentukan computable function). Mesin Turing terkenal dengan ungkapan " Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa dilakukan oleh komputer." (in) En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur. Ce modèle a été imaginé par Alan Turing en 1936, en vue de donner une définition précise au concept d’algorithme ou de « procédure mécanique ».Il est toujours largement utilisé en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité. (fr) A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algorithm. The Turing machine was invented in 1936 by Alan Turing, who called it an "a-machine" (automatic machine). It was Turing's Doctoral advisor, Alonzo Church, who later coined the term "Turing machine" in a review. With this model, Turing was able to answer two questions in the negative: (en) In informatica, una macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite. In altre parole, si tratta di un modello astratto che definisce una macchina in grado di eseguire algoritmi e dotata di un nastro potenzialmente infinito su cui può leggere e/o scrivere dei simboli. (it) Maszyna Turinga – stworzony przez Alana Turinga abstrakcyjny model urządzenia służącego do wykonywania algorytmów. Maszyna składa się z bloku sterowania, głowicy odczytującej i zapisującej oraz nieskończenie długiej taśmy. W każdej komórce taśmy może mieścić się jeden symbol. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z Q stanów. Zależnie od kombinacji stanu maszyny i symbolu napotkanego na taśmie maszyna zapisuje nową wartość w polu, zmienia stan, a następnie może przesunąć się o jedno pole w prawo lub w lewo. Taka operacja nazywana jest rozkazem. Maszyna Turinga jest sterowana listą zawierającą dowolną liczbę takich rozkazów. Czasem dopuszcza się też stan M+1, który oznacza zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga może być traktowana jako (pl) In de informatica is de turingmachine een model van berekening en berekenbaarheid, ontwikkeld door de wiskundige Alan M. Turing in zijn beroemde artikel On computable numbers, with an application to the Entscheidungsproblem uit 1936-37. (nl) A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em 1936).Num sentido preciso, é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento (memória, estados e transições), e não a sua implementação física. Numa máquina de Turing pode-se modelar qualquer computador digital. (pt) En Turingmaskin är en teoretisk modell för att utföra beräkningar. Den utvecklades av matematikern Alan Turing år 1936. Syftet med Turingmaskinen är att betrakta algoritmiska lösningars gränser. En Turingmaskin konstrueras för att lösa ett givet problem, medan den universella Turingmaskinen kan lösa vilket problem som helst. Man kan alltså tänka sig Turingmaskinen som ett datorprogram som utför ett visst program, medan den universella Turingmaskinen kan tänkas som programmerbar. (sv) Маши́на Тю́рінга — математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму. Названа на честь англійського математика Алана Тюрінга, який запропонував це поняття у 1936. Аналогічну конструкцію машини згодом і незалежно від Тюрінга ввів американський математик Еміль Пост. (uk)
rdfs:label Turing machine (en) آلة تورنغ (ar) Màquina de Turing (ca) Turingův stroj (cs) Turingmaschine (de) Μηχανή Τούρινγκ (el) Maŝino de Turing (eo) Máquina de Turing (es) Turingen makina (eu) Machine de Turing (fr) Mesin Turing (in) Macchina di Turing (it) チューリングマシン (ja) 튜링 기계 (ko) Turingmachine (nl) Maszyna Turinga (pl) Máquina de Turing (pt) Turingmaskin (sv) Машина Тьюринга (ru) Машина Тюрінга (uk) 图灵机 (zh)
rdfs:seeAlso dbr:Algorithm dbr:Turing_machine_equivalents
owl:sameAs freebase:Turing machine yago-res:Turing machine http://d-nb.info/gnd/4203525-9 dbpedia-commons:Turing machine wikidata:Turing machine dbpedia-als:Turing machine dbpedia-ar:Turing machine dbpedia-be:Turing machine dbpedia-bg:Turing machine http://bs.dbpedia.org/resource/Turingova_mašina dbpedia-ca:Turing machine http://ckb.dbpedia.org/resource/مەکینەی_تیورینگ dbpedia-cs:Turing machine dbpedia-da:Turing machine dbpedia-de:Turing machine dbpedia-el:Turing machine dbpedia-eo:Turing machine dbpedia-es:Turing machine dbpedia-et:Turing machine dbpedia-eu:Turing machine dbpedia-fa:Turing machine dbpedia-fi:Turing machine dbpedia-fr:Turing machine dbpedia-he:Turing machine dbpedia-hr:Turing machine dbpedia-hu:Turing machine http://hy.dbpedia.org/resource/Թյուրինգի_մեքենա http://ia.dbpedia.org/resource/Machina_de_Turing dbpedia-id:Turing machine dbpedia-it:Turing machine dbpedia-ja:Turing machine dbpedia-ka:Turing machine dbpedia-ko:Turing machine dbpedia-la:Turing machine dbpedia-lb:Turing machine dbpedia-lmo:Turing machine http://lt.dbpedia.org/resource/Tiuringo_mašina http://lv.dbpedia.org/resource/Tjūringa_mašīna dbpedia-mk:Turing machine http://ml.dbpedia.org/resource/ടൂറിങ്_മെഷീൻ dbpedia-nl:Turing machine dbpedia-no:Turing machine dbpedia-oc:Turing machine dbpedia-pl:Turing machine dbpedia-pt:Turing machine dbpedia-ro:Turing machine dbpedia-ru:Turing machine dbpedia-sh:Turing machine dbpedia-simple:Turing machine dbpedia-sk:Turing machine dbpedia-sl:Turing machine dbpedia-sq:Turing machine dbpedia-sr:Turing machine dbpedia-sv:Turing machine dbpedia-th:Turing machine http://tl.dbpedia.org/resource/Makinang_Turing dbpedia-tr:Turing machine dbpedia-uk:Turing machine dbpedia-vi:Turing machine dbpedia-zh:Turing machine https://global.dbpedia.org/id/cP3Q
prov:wasDerivedFrom wikipedia-en:Turing_machine?oldid=1124751125&ns=0
foaf:depiction wiki-commons:Special:FilePath/Turing_machine_2b.svg wiki-commons:Special:FilePath/Busy_Beaver_3_State.png wiki-commons:Special:FilePath/Lego_Turing_Machine.jpg wiki-commons:Special:FilePath/Model_of_a_Turing_machine.jpg wiki-commons:Special:FilePath/Moves_of_a_3-state_Busy_Beaver.jpg wiki-commons:Special:FilePath/State_diagram_3_state_busy_beaver_2B.svg wiki-commons:Special:FilePath/Turing_Machine_Model_Davey_2012.jpg wiki-commons:Special:FilePath/Turing_machine_2a.svg wiki-commons:Special:FilePath/Turingmachine.jpg
foaf:isPrimaryTopicOf wikipedia-en:Turing_machine
is dbo:knownFor of dbr:Alan_Turing
is dbo:wikiPageDisambiguates of dbr:TM dbr:Machine_(disambiguation) dbr:Turing_machine_(disambiguation)
is dbo:wikiPageRedirects of dbr:K-string_Turing_machine_with_input_and_output dbr:Turing_Machine dbr:Turing_Machine_simulator dbr:The_Turing_Machine dbr:Universal_computation dbr:Universal_computer dbr:Universal_computing_machine dbr:Turing-computable_function dbr:Turing_Machines dbr:Turing_machines dbr:Turing_table dbr:A-machine dbr:Deterministic_Turing_machine
is dbo:wikiPageWikiLink of dbr:Primitive_recursive_function dbr:Probabilistic_Turing_machine dbr:Proof_of_impossibility dbr:Propositional_formula dbr:Pushdown_automaton dbr:Pāṇini dbr:Quantum_complexity_theory dbr:Robert_Rosen_(biologist) dbr:Robin_Gandy dbr:RoboMind dbr:Roger_Penrose dbr:Entscheidungsproblem dbr:Enumerator_(computer_science) dbr:List_of_acronyms:_T dbr:List_of_atheists_in_science_and_technology dbr:List_of_computability_and_complexity_topics dbr:List_of_computer_scientists dbr:List_of_eponyms_(L–Z) dbr:List_of_fictional_computers dbr:Mortality_(computability_theory) dbr:NP_(complexity) dbr:Neural_Turing_machine dbr:Nondeterministic_Turing_machine dbr:Metamathematics dbr:Monrobot_XI dbr:Pascal's_mugging dbr:Wang_B-machine dbr:Prof:_Alan_Turing_Decoded dbr:1936_in_science dbr:1937_in_science dbr:Beatrice_Worsley dbr:Bio-inspired_computing dbr:Brainfuck dbr:Decider_(Turing_machine) dbr:DeepMind dbr:Deterministic_finite_automaton dbr:Algorithm dbr:Algorithmic_learning_theory dbr:Algorithmic_probability dbr:Arbitrary-precision_arithmetic dbr:History_of_artificial_intelligence dbr:History_of_computing_hardware dbr:History_of_the_function_concept dbr:John_Searle dbr:List_of_pioneers_in_computer_science dbr:Peano_axioms dbr:Reversible_cellular_automaton dbr:DLOGTIME dbr:DNA_computing dbr:DSPACE dbr:Universality_probability dbr:Dehaene–Changeux_model dbr:Dehn_function dbr:Description_number dbr:Deterministic_system_(philosophy) dbr:EXPSPACE dbr:Incompressibility_method dbr:Index_of_computing_articles dbr:Index_of_philosophy_articles_(R–Z) dbr:Indistinguishability_obfuscation dbr:JFLAP dbr:L/poly dbr:Number dbr:Quantum_computing dbr:List_of_mathematical_logic_topics dbr:The_Pattern_on_the_Stone dbr:K-string_Turing_machine_with_input_and_output dbr:Proof_of_knowledge dbr:Proper_complexity_function dbr:Timeline_of_computing_hardware_before_1950 dbr:1-bit_computing dbr:1000_Blank_White_Cards dbr:107_(number) dbr:Combinatory_logic dbr:Computability dbr:Computability_theory dbr:Computable_function dbr:Computer dbr:Context-free_grammar dbr:Counter-machine_model dbr:Analysis_of_algorithms dbr:Mathematical_constant dbr:Mathematical_logic dbr:Esoteric_programming_language dbr:General_purpose_analog_computer dbr:Generic-case_complexity dbr:Genetix dbr:Novikov_self-consistency_principle dbr:Oracle_machine dbr:Perceptrons_(book) dbr:Turing_machine_equivalents dbr:Trakhtenbrot's_theorem dbr:Timeline_of_algorithms dbr:Timeline_of_mathematical_logic dbr:Church–Turing_thesis dbr:Co-NP dbr:Edward_F._Moore dbr:Emil_Leon_Post dbr:From_Here_to_Infinity_(book) dbr:Function_(mathematics) dbr:Gamma dbr:General_recursive_function dbr:Genius_of_Britain dbr:Glossary_of_artificial_intelligence dbr:Boyer–Moore_majority_vote_algorithm dbr:Configuration_graph dbr:Connectionism dbr:Constructible_function dbr:Constructive_set_theory dbr:Conway's_Game_of_Life dbr:Creative_and_productive_sets dbr:Crossing_sequence_(Turing_machines) dbr:Erik_J._Larson dbr:Rule_110 dbr:Mimic_function dbr:Transition_function dbr:1936_in_the_United_Kingdom dbr:Lenore_Blum dbr:Leonardo_Torres_y_Quevedo dbr:Lossless_compression dbr:Manchester_Baby dbr:Blum–Shub–Smale_machine dbr:Cache-oblivious_algorithm dbr:Steve_Omohundro dbr:Structured_programming dbr:Stuart_Hameroff dbr:Claudio_Baiocchi dbr:Complexity dbr:Complexity_and_Real_Computation dbr:Complexity_class dbr:Component_(graph_theory) dbr:Computable_analysis dbr:Computable_topology dbr:Computably_enumerable_set dbr:Computation dbr:Computational_complexity dbr:Computational_linguistics dbr:Computational_resource dbr:Computational_theory_of_mind dbr:Z3_(computer) dbr:Zero-knowledge_proof dbr:Zillions_of_Games dbr:Empirical_modelling dbr:Functionalism_(philosophy_of_mind) dbr:Hardware_acceleration dbr:Hardware_security dbr:Krivine_machine dbr:PH_(complexity) dbr:PR_(complexity) dbr:Post_correspondence_problem dbr:P′′ dbr:Malament–Hogarth_spacetime dbr:Quantum_supremacy dbr:Spectrum_of_a_sentence dbr:Succinct_game dbr:TM dbr:Theory_of_computation dbr:Markov_algorithm dbr:P/poly dbr:BPP_(complexity) dbr:Busy_beaver dbr:Actual_infinity dbr:Adian–Rabin_theorem dbr:Thought dbr:Thought_experiment dbr:Time_complexity dbr:Time_evolution dbr:Tree_stack_automaton dbr:Turing's_proof dbr:Turing_Machine dbr:Turing_Machine_simulator dbr:Darwin_machine dbr:Datapath dbr:Walter_Pitts dbr:Warren_Sturgis_McCulloch dbr:Doctor_in_a_cell dbr:Fuzzy_logic dbr:Gödel_numbering dbr:Gödel_numbering_for_sequences dbr:DTM dbr:June_1912 dbr:Lamplighter_group dbr:Langton's_ant dbr:Large_countable_ordinal dbr:Linear_bounded_automaton dbr:Linear_speedup_theorem dbr:Log-space_transducer dbr:Logics_for_computability dbr:Minds,_Machines_and_Gödel dbr:Neuromorphic_engineering dbr:P-complete dbr:Turing_switch dbr:Multi-track_Turing_machine dbr:Unrestricted_grammar dbr:Recursively_enumerable_language dbr:ANTIC dbr:Abstract_state_machine dbr:Alan_Turing dbr:Algorithm_characterizations dbr:Alonzo_Church dbr:Curry–Howard_correspondence dbr:Danny_Hillis dbr:Fallibilism dbr:Finite-state_transducer dbr:Flex_(lexical_analyser_generator) dbr:Normal_number dbr:Norman_Shapiro dbr:Number_theory dbr:PGF/TikZ dbr:PSPACE dbr:Cellular_automaton dbr:Cellular_neural_network dbr:Church's_thesis_(constructive_mathematics) dbr:Church–Turing–Deutsch_principle dbr:Formal_grammar dbr:Formal_language dbr:Goodstein's_theorem dbr:Goto dbr:Hilbert's_tenth_problem dbr:History_monoid dbr:History_of_computer_science dbr:History_of_logic dbr:History_of_programming_languages dbr:History_of_software dbr:History_of_the_Church–Turing_thesis dbr:Iterated_logarithm dbr:Kolmogorov_complexity dbr:Tessellation dbr:Unary_numeral_system dbr:Legacy_of_Alan_Turing dbr:Proof_by_contradiction dbr:List_of_people_considered_father_or_mother_of_a_field dbr:Mathematical_problem dbr:Quantum_Turing_machine dbr:RE_(complexity) dbr:R_(complexity) dbr:Reading_(computer) dbr:Recurrent_neural_network dbr:Reduction_(complexity) dbr:Regular_language dbr:Gödel's_incompleteness_theorems dbr:Halting_problem dbr:Hans_Hermes dbr:Hao_Wang_(academic) dbr:Hilary_Putnam dbr:Jack_Copeland dbr:Taylor_Booth_(mathematician) dbr:Counter_(digital) dbr:Counter_automaton dbr:Counter_machine dbr:Hypercomputation dbr:Turmite dbr:The_Emperor's_New_Mind dbr:Arnold_Schönhage dbr:AC0 dbr:AI-complete dbr:AIXI dbr:A_New_Kind_of_Science dbr:A_Universe_of_Consciousness dbr:Abstract_machine dbr:Ackermann_function dbr:Advice_(complexity) dbr:Chinese_room dbr:Chomsky_hierarchy dbr:John_Lucas_(philosopher) dbr:Justin_Leiber dbr:Lambda_calculus dbr:Binary_combinatory_logic dbr:Black-box_obfuscation dbr:Symbol_grounding_problem dbr:Cognitive_architecture dbr:Effective_method dbr:Termination_analysis dbr:Mobile_membranes dbr:Read-only_Turing_machine dbr:Recursive_language dbr:Register_machine dbr:Regulated_rewriting dbr:Digital_infinity dbr:Automata-based_programming dbr:Automata-based_programming_(Shalyto's_approach) dbr:Automata_theory dbr:Boolean_circuit dbr:Boolean_satisfiability_problem dbr:Philosophy_of_mathematics dbr:Polynomial_hierarchy dbr:Post–Turing_machine dbr:Solomonoff's_theory_of_inductive_inference dbr:Ciphertext_indistinguishability dbr:Circuit_complexity dbr:Greek_letters_used_in_mathematics,_science,_and_engineering dbr:Group_theory dbr:The_Turing_Machine dbr:Minimum_message_length dbr:Oblivious_RAM dbr:Castration dbr:Rainbow_Honor_Walk dbr:Random-access_machine dbr:Random-access_stored-program_machine dbr:Randomized_algorithm
is rdfs:seeAlso of dbr:Computing_Machinery_and_Intelligence dbr:Computer_science
is foaf:primaryTopic of wikipedia-en:Turing_machine