A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.

Property Value
dbo:abstract
  • آلة تورنغ هي نموذج نظري بسيط يحاكي طريقة عمل الحاسوب. سميت بهذا الاسم نسبة لعالم الرياضيات الإنجليزي آلان تورنغ الذي أوجد هذا النموذج سنة 1936م. هذا النموذج يعطي تعريفا رياضيا دقيقا للمصطلح خوارزم Algorithm, أهمية هذا النموذج تكمن في بساطته مقارنة بجهاز الحاسوب المعقد وبالرغم من ذلك فهو قادر على تنفيذ كل خوارزمية قابلة للتنفيذ بواسطة أي حاسوب متطور. لذلك يمكن معرفة إذا كانت عملية معينة قابلة للتنفيذ بواسطة الحاسوب أم لا عن طريق فحصها بواسطة آلة تورنغ. من هنا فإن لآلة تورنغ استعمال واسع في مجال دراسة قدرة الحاسوب والعمليات التي يمكنه أو لا يمكنه تنفيذها، وهو ما يسمى علم قابلية الحساب.يعتبر نموذج آلة التورينغ نموذج رياضياً بسيطاً للحاسوب وينمذج المقدرة الحسابية لحاسوب ذي وظائف عمومية وهو أيضاً من أهم اللغات الصورية إذ يقبل أوسع مجموعة منها وهي اللغات القابلة للعد عمودياً والتي يمكن توليدها بنماذج قواعدية من النوع صفر. يتألف النموذج الأساسي لآلة التورينغ من تحكم منته وشريط دخل منته من جهة واحدة هي جهة اليسار وغير منته من جهة اليمين ومقسم إلى عدة خلايا كل منها يحمل رمزاً واحداً من مجموعة منتهية تسمى "رموز الشريط" ورأس يسمى رأس القراءة والكتابة الذي يمر في كل مرة على خلية واحدة من الشريط. تحتوي الخلايا الn اليسارية من شريط الدخل (n عدد منته)في الحالة الابتدائية رموز الدخلفي حين تحتوي الخلايا المتبقة من الشريط رمزاً فارغاً. تقوم آلة التورينغ في الحركة الواحدة واعتماداً على رمز الدخل المقروء من شريط الدخل وحالة التحكم المنتهي بالعمليات التالية: * تغيير حالة التحكم المنتهي. * كتابة رمز شريط في الخلية المقروءة. * التحرك خلية واحدة إلى اليسار أو إلى اليمين أو عدم التحرك بتاتا . (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. 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 als 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)
  • Turingův stroj (TS) je teoretický model počítače popsaný matematikem Alanem Turingem.Skládá se z procesorové jednotky, tvořené konečným automatem, programu ve tvaru pravidel přechodové funkce a pravostranně nekonečné pásky pro zápis mezivýsledků. Využívá se pro modelování algoritmů v teorii vyčíslitelnosti. 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)
  • A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed. The machine operates on an infinite memory tape divided into discrete "cells". The machine positions its "head" over a cell and "reads" or "scans" the symbol there. Then, as per the symbol and the machine's own present state in a "finite table" of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allow symbol erasure or no writing), then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head), then (iii) (as determined by the observed symbol and the machine's own state in the table) either proceeds to a subsequent instruction or halts the computation. The Turing machine was invented in 1936 by Alan Turing, who called it an "a-machine" (automatic machine). With this model, Turing was able to answer two questions in the negative: (1) 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); similarly, (2) 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)
  • 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)
  • Eine Turingmaschine ist ein wichtiges Rechnermodell der theoretischen Informatik. Eine Turingmaschine modelliert die Arbeitsweise eines Computers auf besonders einfache und mathematisch gut zu analysierende Weise. Sie ist benannt nach dem Mathematiker Alan Turing, der sie 1936 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. (de)
  • Turingen makina konputaziorako gailu abstraktoak dira, Alan Turing matematikari eta filosofoak 1937 urtean asmatuak. Hasiera batean, konputazioaren mugak ikertzeko garatu zituen Turingek. Funtsean, egoera batetik bestera igarotzen den sistema bat da, informazioa irakurri ondoren eta, egoera eta informazioa zein diren, ekintza bat burutu ondoren. (eu)
  • 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)
  • 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)
  • 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, è 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. È 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. La MdT come modello di calcolo è stata introdotta nel 1936 da Alan Turing per dare risposta all'Entscheidungsproblem (problema di decisione) proposto da Hilbert nel suo programma di fondazione formalista della matematica. (it)
  • チューリングマシン (英: Turing Machine) は、アラン・チューリングが「計算可能性」に関する議論のために提示した抽象機械である。 (ja)
  • 이론 전산학에서, 튜링 기계(영어: Turing machine)는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이다. 상당히 간단해 보이지만 이 기계는 적당한 규칙과 기호를 입력한다면 일반적인 컴퓨터의 알고리즘을 수행할 수 있으며 컴퓨터 CPU의 기능을 설명하는데 상당히 유용하다. 1936년 앨런 튜링은 계산하는 기계를 대표할 수 있는 가상의 장치를 만들었고이 장치에 영어 단어인 automatic의 a를 따서 "a-기계"라는 이름을 붙였다. 이 기계가 바로 나중에 창시자인 앨런 튜링의 이름을 따서 튜링 기계라 불리게 되었다. 1948년 "똑똑한 기계"라는 글에서 앨런 튜링은 자신의 "a-기계"를 간결히 정의하였다. 1936년 논문 "계산 가능한 수와 결정성 문제에의 응용"을 언급하며 튜링기계(이 글에서는 논리적 계산 기계라는 표현을 사용한다.)를 다음과 같이 기술하였다. (ko)
  • Maszyna Turinga – stworzony przez Alana Turinga matematyczny model obliczeń, który definiuje abstrakcyjną maszynę służącą 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 uiterst eenvoudig mechanisme dat symbolen manipuleert en ondanks deze eenvoud kan men hiermee de logica van elke mogelijke computer simuleren. Hoewel technisch realiseerbaar (zo lang we willekeurige hoeveelheden band kunnen aanleveren) zijn deze machines niet bedoeld voor praktische computertechnologie, maar als een gedachte-experiment rond de limieten van mechanische berekeningen; ze worden dus niet echt gebouwd. (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. 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)
  • 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)
  • 图灵机(英語:Turing machine),又称确定型图灵机,是英国数学家艾倫·图灵于1936年提出的一种將人的計算行為抽象掉的,其更抽象的意义为一种计算模型,可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。 (zh)
  • Маши́на Тю́рінга — математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму. Названа на честь англійського математика Алана Тюрінга, який запропонував це поняття у 1936. Аналогічну конструкцію машини згодом і незалежно від Тюрінга ввів американський математик Еміль Пост. Основна ідея, що лежить в основі машини Тюрінга, дуже проста. Машина Тюрінга — це абстрактна машина (автомат), що працює зі стрічкою, що складається із окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок і яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ із комірки, на яку вказує голівка та, на основі зчитаного символу та внутрішнього стану, робиться наступний крок. При цьому, машина може змінити свій стан, записати інший символ у комірку або пересунути голівку на одну комірку ліворуч або праворуч. (uk)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 30403 (xsd:integer)
dbo:wikiPageLength
  • 71455 (xsd:integer)
dbo:wikiPageRevisionID
  • 985495165 (xsd:integer)
dbo:wikiPageWikiLink
dbp:id
  • p/t094460 (en)
dbp:title
  • Turing machine (en)
dbp:wikiPageUsesTemplate
dct:subject
rdf:type
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)
  • Turingen makina konputaziorako gailu abstraktoak dira, Alan Turing matematikari eta filosofoak 1937 urtean asmatuak. Hasiera batean, konputazioaren mugak ikertzeko garatu zituen Turingek. Funtsean, egoera batetik bestera igarotzen den sistema bat da, informazioa irakurri ondoren eta, egoera eta informazioa zein diren, ekintza bat burutu ondoren. (eu)
  • チューリングマシン (英: 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.Skládá se z procesorové jednotky, tvořené konečným automatem, programu ve tvaru pravidel přechodové funkce a pravostranně nekonečné pásky pro zápis mezivýsledků. Využívá se pro modelování algoritmů v teorii vyčíslitelnosti. Jeden ze způsobu vyjádření Churchovy-Turingovy teze říká, že ke každému algoritmu existuje ekvivalentní Turingův stroj. (cs)
  • Eine Turingmaschine ist ein wichtiges Rechnermodell der theoretischen Informatik. Eine Turingmaschine modelliert die Arbeitsweise eines Computers auf besonders einfache und mathematisch gut zu analysierende Weise. Sie ist benannt nach dem Mathematiker Alan Turing, der sie 1936 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. (de)
  • Η Μηχανή Τούρινγκ είναι μια υποθετική συσκευή η οποία χειρίζεται σύμβολα σύμφωνα με ένα σύνολο κανόνων. Παρά την απλότητά της, μια Μηχανή Τούρινγκ μπορεί να προσαρμοστεί ώστε να προσομοιώνει την λογική οποιουδήποτε αλγορίθμου, και είναι ιδιαίτερα χρήσιμη στο να εξηγεί τις λειτουργίες μιας κεντρικής μονάδας επεξεργασίας στο εσωτερικό του υπολογιστή. Ο Τούρινγκ έδωσε έναν περιληπτικό ορισμό του πειράματος στην έκθεση του, "Ευφυή μηχανήματα". Έγραψε ότι η μηχανή Τούρινγκ, που εδώ ονομάζεται μια Λογική Υπολογιστική Μηχανή, αποτελείται από: (el)
  • A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed. (en)
  • 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)
  • 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)
  • 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)
  • 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, è 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)
  • 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)
  • Maszyna Turinga – stworzony przez Alana Turinga matematyczny model obliczeń, który definiuje abstrakcyjną maszynę służącą 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 (pl)
  • 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)
  • Маши́на Тю́рінга — математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму. Названа на честь англійського математика Алана Тюрінга, який запропонував це поняття у 1936. Аналогічну конструкцію машини згодом і незалежно від Тюрінга ввів американський математик Еміль Пост. (uk)
  • 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)
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)
  • チューリングマシン (ja)
  • Macchina di Turing (it)
  • 튜링 기계 (ko)
  • Turingmachine (nl)
  • Maszyna Turinga (pl)
  • Máquina de Turing (pt)
  • Машина Тьюринга (ru)
  • Turingmaskin (sv)
  • Машина Тюрінга (uk)
  • 图灵机 (zh)
rdfs:seeAlso
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:knownFor of
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is rdfs:seeAlso of
is foaf:primaryTopic of