| p:abstract
| - Turing machines are extremely basic abstract symbol-manipulating devices which, despite their simplicity, can be adapted to simulate the logic of any computer algorithm (as we understand them). They were described in 1936 by Alan Turing. Though technically feasible, Turing machines were not intended as a practical computing technology, but a thought experiment about the limits of mechanical computation; thus they were not actually constructed. Studying their abstract properties yields many insights into computer science and complexity theory.
A Turing machine that is able to simulate any other Turing machine is called a Universal Turing machine (UTM, or simply a universal machine). A more mathematically-oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church-Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective method in logic and mathematics, and provide a precise definition of an algorithm or 'mechanical procedure'. (en)
- La máquina de Turing es un modelo computacional introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing construyó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. La máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo. (es)
- Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Informatik.
Das Modell wurde im Rahmen des von David Hilbert im Jahr 1920 formulierten Hilbertprogramms, speziell zur Lösung des so genannten Entscheidungsproblems, in der Schrift "On Computable Numbers, with an Application to the Entscheidungsproblem" vorgestellt. Alan Turing beabsichtigte, mit der Turingmaschine ein Modell des mathematisch arbeitenden Menschen zu schaffen.
Das Besondere an einer Turingmaschine ist, dass sie mit nur drei Operationen (Lesen, Schreiben und Kopf bewegen) die Probleme lösen kann, die auch von einem Computer gelöst werden könnten. Sämtliche mathematische Grundfunktionen wie Addition und Multiplikation lassen sich mit diesen drei Operationen simulieren. Darauf aufbauend kann man schließlich komplexere Programme simulieren. Eine Funktion, die so durch eine Turingmaschine berechnet werden kann, nennt man eine turingberechenbare Funktion.
Die Church-Turing-These stellt schließlich die Behauptung auf, dass eine Turingmaschine gerade die von Menschen berechenbaren mathematischen Funktionen lösen kann. Daraus darf jedoch nicht gefolgert werden, dass eine Turingmaschine alle mathematischen Funktionen lösen kann. So kann etwa anhand des Halteproblems gezeigt werden, dass es mathematische Funktionen gibt, die nicht von Turingmaschinen (und daher gemäß Church-Turing-These auch nicht von Menschen) berechnet werden können. (de)
- Turingin kone on teoreettinen malli sille miten tietokone toimii. Mallin kehitti matemaatikko Alan Turing vuonna 1936 määritelläkseen tarkasti käsitteen algoritmi. Turingin kone muistuttaa varhaista mekaanista tietokonetta, vaikkakaan yhtään ohjelmoitavaa tietokonetta ei vielä ollut sen keksimishetkellä rakennettu. Turingin kone on tarkoitettu algoritmisen ratkaisun mahdollisuuksien rajojen tarkkailuun.
Turingin kone, joka pystyy simuloimaan mitä tahansa muuta Turingin konetta siihen ladattavien ohjeiden mukaan, on nimeltään universaali Turingin kone.
Turingin koneen voi käsittää tietokoneohjelmana, joka toimii tietyn syötteen mukaan, ja universaalikoneen ohjelmoitavana tietokoneena. (fi)
- Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise au concept d'algorithme ou « procédure mécanique ».
Ce modèle est toujours largement utilisé en informatique théorique, en particulier pour résoudre les problèmes de complexité algorithmique et de calculabilité, on lui adjoint pour cela un oracle.
La thèse Church-Turing postule que tout problème de calcul basé 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 de procédure algorithmique. 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 (Turing-complet).
À 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 tableau infini, en choisissant ce contenu parmi un ensemble fini de symboles. D'autre part, la personne doit mémoriser un état particulier parmi un ensemble fini d'états. La procédure est formulée en termes d'étapes très simples, 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 une case(droite ou gauche) ». (fr)
- Una macchina di Turing (termine spesso abbreviato con MdT) è una macchina formale, cioè un sistema formale che può descriversi come un meccanismo ideale, ma in linea di principio realizzabile concretamente, che può trovarsi in stati ben determinati, opera su stringhe in base a regole ben precise e costituisce un modello di calcolo. Essa ha la particolarità di essere retta da regole di natura molto semplice, ovvero di potersi descrivere come costituita da meccanismi elementari molto semplici; inoltre è possibile presentare a livello sintetico le sue evoluzioni mediante descrizioni meccanicistiche piuttosto intuitive. D'altra parte essa ha la portata computazionale (potere computazionale) che si presume essere la massima: si dimostra infatti che essa è equivalente, ossia in grado di effettuare le stesse elaborazioni di tutti gli altri modelli di calcolo di più ampia portata. Tra questi modelli di calcolo ricordiamo le funzioni ricorsive di Jacques Herbrand e Kurt Gödel, il lambda calcolo di Alonzo Church e Stephen Kleene, la logica combinatoria di Moses Schönfinkel e Haskell Curry, gli algoritmi di Markov, i sistemi di Thue, i sistemi di Post, le macchine di Hao Wang e le macchine a registri elementari o RAM astratte di Marvin Minsky.
Di conseguenza si è consolidata la convinzione che per ogni problema calcolabile esista una MdT in grado di risolverlo: questa è la cosiddetta congettura di Church-Turing, la quale postula in sostanza che per ogni funzione calcolabile esista una macchina di Turing equivalente, ossia che l'insieme delle funzioni calcolabili coincida con quello delle funzioni ricorsive.
La MdT come modello di calcolo è stato 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.
Per le sue caratteristiche, il modello della MdT è un efficace strumento teorico che viene largamente usato nella teoria della calcolabilità e nello studio della complessità degli algoritmi. Per definire in modo formalmente preciso la nozione di algoritmo oggi preferenzialmente si sceglie di ricondurlo alle elaborazioni effettuabili con macchine di Turing. (it)
- チューリングマシン (Turing Machine) は計算模型のひとつ。すなわち、計算機を数学的に議論するための、単純化・理想化された仮想機械である。 (ja)
- 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 ze technisch realiseerbaar zijn, zijn ze niet bedoeld voor praktische computertechnologie maar als een gedachte-experiment rond de limieten van mechanische berekeningen; ze worden dus niet echt gebouwd. (nl)
- En turingmaskin er en tenkt, formelt beskrevet maskin som utfører ordre etter en helt bestemt oppskrift eller en tabell. Maskinen er en idealisert og formell beskrivelse av en datamaskin, og hvilke beregninger eller oppgaver en datamaskin kan utføre. Maskinen er idealisert i den forstand at den har uendelig stor lagringsplass (hukommelse), og den gjør aldri feil på grunn av sine fysiske mekanismer. Det var Alan Turing som først beskrev en slik maskin i sin avhandling On Computable Numbers i 1936.
En turingmaskin består av et lese/skrive-hode som kan lese/skrive tegn fra/til ruter på en papirstrimmel. Maskinen har mange, men et endelig antall tilstander som beskriver hva som skal gjøres når et bestemt tegn leses. For hvert tegn som leses, gjøres to ting: maskinen skriver eventuelt et nytt tegn til strimmelen, og endrer tilstanden. Maskinen har en start-tilstand og en slutt-tilstand. «Resultatet» av beregningene står til slutt på strimmelen.
Alan Turing brukte en formell beskrivelse av en slik maskin for å bevise setninger innen matematikken. Siden har interessen rundt hans abstrakte maskiner (de ble først senere kalt turingmaskiner) vokst i forbindelse med fremveksten av datamaskiner, og hva datamaskiner egentlig kan utføre av beregninger. Det ser ut til at ingen maskin kan være «kraftigere» enn en turingmaskin i den forstand at den kan utføre andre oppgaver som turingmaskinen ikke klarer. (no)
- Maszyna Turinga - stworzony przez Alana Turinga abstrakcyjny model komputera służący do wykonywania algorytmów. Każdy algorytm wyrażalny na maszynie Turinga można wyrazić w rachunku lambda i odwrotnie. Ponieważ jednak maszyny Turinga rozszerza się bardzo trudno, zaś rachunek lambda bardzo łatwo, w praktyce są one o wiele mniej popularne jako rzeczywiste modele obliczeń. Są za to używane często do udowadniania nierozstrzygalności różnych problemów.
Maszyna Turinga składa się z nieskończenie długiej taśmy podzielonej na pola. Taśma może być nieskończona jednostronnie lub obustronnie. Każde pole może znajdować się w jednym z N stanów. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z M stanów. Zależnie od kombinacji stanu maszyny i pola 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ą ilość takich rozkazów. Liczby N i M mogą być dowolne, byle skończone. Czasem dopuszcza się też stan (M+1)-szy, który oznacza zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga może być traktowana jako jej program.
Maszyna Turinga A posiadająca zdolność symulacji działania dowolnej innej maszyny Turinga B (opisanej jako dane wejściowe dla maszyny A) na dowolnych danych wejściowych dla maszyny B, nazywana jest uniwersalną maszyna Turinga. Praktycznym przybliżeniem realizacji uniwersalnej Maszyny Turinga jest komputer, będący w stanie wykonać dowolny program na dowolnych danych. Należy podkreślić, że komputery nie są uniwersalnymi maszynami Turinga w sensie pierwotnej definicji, ponieważ ilość danych, które mogą przechowywać i przetwarzać jest skończona, tak więc dla każdego komputera istnieje tylko skończona ilość programów, które może wykonać. Mimo, że ilość ta jest niewyobrażalnie wielka i w praktyce często wystarczająca, to bez względu na rozmiar pamięci, zawsze będzie istnieć program, którego maszyna nie będzie w stanie wykonać, ponieważ jego kod (opis) po prostu nie mieści się w tej pamięci.
Można rozważać bardzo wiele różnych wariantów maszyny Turinga. Na przykład nie ma potrzeby pozwalać na pozostanie maszyny na tym samym polu, ponieważ maszyna musi albo zakończyć obliczenia przez zapętlenie, albo po nie więcej niż N*M krokach dane pole opuścić i wystarczy wtedy przyjąć dla danej kombinacji początkowej stany podczas opuszczania pola.
Istnieją też maszyny Turinga wielotaśmowe lub niedeterministyczne (gdzie jednej parze (symbol, stan) może odpowiadać kilka instrukcji) oraz wielowymiarowe (prostą dwuwymiarową maszyną Turinga jest mrówka Langtona).
W informatyce dowodzi się równoważności wielu różnych wariantów maszyny Turinga. Np. (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 à 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 II Guerra Mundial, tendo utilizado alguns dos conceitos teóricos desenvolvidos para o seu modelo de computador universal. (pt)
- Машина Тьюринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча–Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом
реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен. (ru)
- En turingmaskin är en abstrakt mekanism, en teoretisk modell, för att utföra beräkningar, som utvecklades av Alan Turing år 1936. Turingmaskinen konstruerades till den enklast möjliga mekanismen som är kapabel att utföra icke-triviala beräkningar, och spelar en central roll i teorierna för beräkningsbarhet och beräkningskomplexitet, samt allmänt inom den matematiska logiken.
En turingmaskin kan konstrueras för att lösa ett givet problem (en specifik turingmaskin), men det går också att konstruera en universell turingmaskin som är kapabel att läsa en kodad beskrivning av en specifik turingmaskin med dess indata, och sedan utföra denna maskins beräkning.
Church-Turings hypotes säger att varje tänkbar beräkningsprocess kan utföras av en turingmaskin, och alltså att det rent principiellt inte finns någon mer kraftfull beräkningsmekanism. Denna tes är inte i strikt matematisk mening bevisad, men allmänt accepterad som sann. Argument som talar för tesen är bland andra att andra försök till teoretiska modeller av beräkningsprocesser, som till exempel Churchs lambdakalkyl, rekursionsteori och post-maskiner, kan visas vara ekvivalenta med turingmaskiner. Alla dagens datorer kan också betraktas som turingmaskiner: de kan med andra ord simuleras av en sådan.
Teorierna om turingmaskiner fick stor betydelse för konstruktionerna av de första datorerna, till exempel Z3 . (sv)
- 杜林机（英语：Turing Machine，又称确定型杜林机）是英国数学家阿兰·杜林于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。 (zh)
|
| rdfs:comment
| - Turing machines are extremely basic abstract symbol-manipulating devices which, despite their simplicity, can be adapted to simulate the logic of any computer algorithm (as we understand them). They were described in 1936 by Alan Turing. Though technically feasible, Turing machines were not intended as a practical computing technology, but a thought experiment about the limits of mechanical computation; thus they were not actually constructed. (en)
- La máquina de Turing es un modelo computacional introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. (es)
- Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Informatik. (de)
- Turingin kone on teoreettinen malli sille miten tietokone toimii. Mallin kehitti matemaatikko Alan Turing vuonna 1936 määritelläkseen tarkasti käsitteen algoritmi. Turingin kone muistuttaa varhaista mekaanista tietokonetta, vaikkakaan yhtään ohjelmoitavaa tietokonetta ei vielä ollut sen keksimishetkellä rakennettu. Turingin kone on tarkoitettu algoritmisen ratkaisun mahdollisuuksien rajojen tarkkailuun. (fi)
- Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise au concept d'algorithme ou « procédure mécanique ». Ce modèle est toujours largement utilisé en informatique théorique, en particulier pour résoudre les problèmes de complexité algorithmique et de calculabilité, on lui adjoint pour cela un oracle. (fr)
- Una macchina di Turing (termine spesso abbreviato con MdT) è una macchina formale, cioè un sistema formale che può descriversi come un meccanismo ideale, ma in linea di principio realizzabile concretamente, che può trovarsi in stati ben determinati, opera su stringhe in base a regole ben precise e costituisce un modello di calcolo. (it)
- チューリングマシン (Turing Machine) は計算模型のひとつ。すなわち、計算機を数学的に議論するための、単純化・理想化された仮想機械である。 (ja)
- 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)
- En turingmaskin er en tenkt, formelt beskrevet maskin som utfører ordre etter en helt bestemt oppskrift eller en tabell. Maskinen er en idealisert og formell beskrivelse av en datamaskin, og hvilke beregninger eller oppgaver en datamaskin kan utføre. Maskinen er idealisert i den forstand at den har uendelig stor lagringsplass (hukommelse), og den gjør aldri feil på grunn av sine fysiske mekanismer. (no)
- Maszyna Turinga - stworzony przez Alana Turinga abstrakcyjny model komputera służący do wykonywania algorytmów. Każdy algorytm wyrażalny na maszynie Turinga można wyrazić w rachunku lambda i odwrotnie. Ponieważ jednak maszyny Turinga rozszerza się bardzo trudno, zaś rachunek lambda bardzo łatwo, w praktyce są one o wiele mniej popularne jako rzeczywiste modele obliczeń. Są za to używane często do udowadniania nierozstrzygalności różnych problemów. (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 à sua implementação física. (pt)
- Машина Тьюринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. (ru)
- En turingmaskin är en abstrakt mekanism, en teoretisk modell, för att utföra beräkningar, som utvecklades av Alan Turing år 1936. Turingmaskinen konstruerades till den enklast möjliga mekanismen som är kapabel att utföra icke-triviala beräkningar, och spelar en central roll i teorierna för beräkningsbarhet och beräkningskomplexitet, samt allmänt inom den matematiska logiken. (sv)
- 杜林机（英语：Turing Machine，又称确定型杜林机）是英国数学家阿兰·杜林于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。 (zh)
|
![[RDF Data]](http://dbpedia.org/statics/sw-cube.png)
