What is Turing machine: Definition and 40 Discussions

A Turing machine is a mathematical model of computation that defines an abstract machine that 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, based on 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) based on the observed symbol and the machine's own state in the table either proceeds to another 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:

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.

View More On Wikipedia.org
Recent contents Top users
  1. C

    Comp Sci Why is NTM Time Complexity Guessing Polynomial?

    ( Source: Introduction to the theory of computation, Michael Sipser, 3rd edition ) I know the computation of a non-deterministic Turing machine ( NTM ) which is a decider is defined to be the depth of its configuration tree. In the above example of showing that ## HAMPATH \in NP ##, where it's...
  2. fresh_42

    Insights P vs. NP conjecture and what is a Turing Machine (TM)?

    https://www.physicsforums.com/insights/p-vs-np-conjecture-calculations-and-meaning/
  3. T

    Have a Turing Machine? Can it solve linear algebraic equations?

    I don't understand the Turing Machine. Amazingly this hypothetical device, designed in the 1930s can do everything the most powerful computers can do today, but it would just take much longer. Has anybody ever built one just to solve a simple linear algebraic equation? How long would the tape...
  4. phoenix-anna

    Turing-recognizable infinite language, decidable subset

    Summary:: Show that every infinite Turning-recognizable language has an infinite decidable subset Sipser's Theory of Computation, third edition, chapter three contains and exercise that asks us to demonstrate this. I don't know how to do this; I have certain ideas. We could modify the...
  5. M

    MHB Is this a Gödel number of a Turing machine?

    Hey! :o We have the number \begin{align*}70&6737922567786324304462189150536772513339293263220644 \\ &=2^2\cdot 3\cdot 59^5\cdot 103\cdot 149^2\cdot 353\cdot 607\cdot 823^4\cdot 1409\cdot 1873^2\cdot 4201^3\end{align*} I want to check if this is a Gödel number of a Turing machine. From...
  6. M

    MHB Reducing States in Modified Turing Machines

    Hey! :o I am looking at the following: The Turing table of the following modified Turing machine is given: Change this into an ordinary "Turing machine" (i.e., one that either writes or moves the head). Give the appropriate Turing table. Give also the Turing table of an equivalent...
  7. L

    Design an Infinite NTM for Any Input String: Turing Machine Question

    Hey guys just wondering if I could get some help with this question. I am having trouble with it as I don't know what the input language is and therefore what inputs to handle. Heres the question: Design an NTM (normalised Turing machine) that never terminates, so that regardless of the input...
  8. ShayanJ

    A brain-like implementation of a Turing machine

    At first I should say that this thread involves many scientific fields and I don't think there is any correct section of PF to put it under so I just went with the engineering. One of the greatest mysteries(maybe the greatest) that science is trying to solve today, is the emergence of...
  9. evinda

    MHB Is this a possible Turing machine for computing $f_2$?

    Hello! (Wave) Let $f_1(x,y)=x+y$, $f_2(x,y)=xy$. I want to find a Turing machine that computes $f_1$ and describe one that computes $f_2$.A Turing machine can: read delete write The numbers are in binary form. We have to add the last element of $x$ to the last element of $y$ , then...
  10. FraserAC

    A What Are Advanced Dissertation Topics in Quantum Computing?

    Hi! I'm going on to the masters year of a theoretical physics course and I need some inspiration for my dissertation. Last year I did a one semester long project on quantum computation. (More specifically I discussed the general idea of a qubit, a simple method of realising a qubit using spin...
  11. M

    MHB Designing a Non-deterministic 2-Tape Turing Machine for a Specific Language

    Hey! :o I want to find a non-deterministic 2-tape Turing machine, that accepts the language L over $\Sigma=\{0,1\}$ in $n$ steps, with input of length $n$, $L=\{x1y \mid |y|=2|x|>0\}$. Should the Turing machine do the following? (Wondering) Each time that the machine reads 1 it should check...
  12. M

    MHB Non-deterministic 2-tape Turing Machine

    Hey! :o I want to find a non-deterministic $2$-tape Turing Machine, that accepts the language $L$ over $\Sigma=\{0,1,\#\}$ in linear time, $$L=\{x\#y \mid x,y \in \{0,1\}^\star, x \text{ is contained in } y\}$$ Does the Turing Machine look as follows? The tape $1$ contains the input $w$ and...
  13. G

    Language that cannot be decided by a TM using space O(log n)

    Homework Statement 1. Give a language L that cannot be decided by a TM using space O(log n) and time less than n on inputs of length n. The language L should be decidable by some TM. Assume the TM has a binary input alphabet. Homework Equations Undecidability, Turing Machines, Languages...
  14. K

    Computability in Classical Physics

    I was reading the book "Emperor's New Mind" by Roger Penrose which deals with understanding the nature of mind in the sense that it is algorithmic or not. In one of the chapters he explains that the deterministic world of the Newtonian Theory can still be non-computable. He explains this as...
  15. B

    [Theoretical computer science] Regular Turing Machine undecidable proof

    Hello the proof of the Spiser's book (introduction to theory of computation): PROOF We let R be a TM that decides REGULARTM and construct TM S to decide ATM. Then S works in the following manner. S = "On input (M, w), where M is a TM and w is a string: 1...
  16. M

    MHB Solving Recursive Sets with Turing Machines

    Hey! :o I have to show that a set is recursive if and only if the set and its complement is recursively enumerable. I have done the following: $\Rightarrow$ Let $A$ the recursive set, so there is a Turing machine $M$ that decides the set $A$. We construct a TM $M'$ that semi-decides the set...
  17. M

    How the original Turing machine broke the enigma

    I just saw The Imitation Game and was wondering how the original Turing machine broke the enigma. Could someone explain it to me?
  18. J

    MHB Formally describe a Turing machine which decides if an input is odd or even.

    Hi, I need to use a transition function to describe a Turing machine that decides if $ a^n ∈ {a}^∗$ is odd or even. I've got an example in my notes that erases any input and halts. But I am struggling to do one for the odd and even question. Thanks for any help!
  19. M

    MHB Relationship between the Turing Machine and RAM Models

    Hey! :o Could you tell me which is the relationship between the Turing Machine and RAM Models??
  20. mishima

    Help explain this Turing machine notation

    Below is an image from a website article discussing a Turing machine. It is supposed to represent a Turing machine, but I don't really follow the notation. I assume this is part of Wolfram's book, "New Kind of Science", which I do not have a copy of. I have only ever seen a Turing machine...
  21. trash

    Constructing a Turing Machine for the min function

    Homework Statement I'm trying to construct a Turing machine that after receiving two integers x,y gives back the smaller one (or any of them if they are equal).Homework Equations I cannot use anything besides zeros and ones (I have seen that some people make turing machine using letters to keep...
  22. S

    Can a Turing Machine Execute Multiple Programs?

    Hi: I read many articles about turing machine,but i still confused:confused: is a turing machine can only execute one program(hardwired) ? or it can execute many programs(like a conventional computer)? i asking about turing machine as shown in figure blew(not asking about universal TM...
  23. N

    Turing machine depth-first search algorithm

    Homework Statement On the tapes of Turing machine recorded the number of vertices (n) in the binary system, the length of the desired cycle - k (in binary), and the adjacency matrix of the graph. Required to construct a Turing machine, which checks for the cycles of k-length in the graph, and...
  24. M

    Turing machine problem to getting startet

    Good everning! I am currently working on problems related to turing machines. Lets say we have a turing machine T . Vi can see the Turing machine driving in state 1, state 2 and so forth. If we do this we can set it up as a table. see under. in my head it will look like this (R is a...
  25. A

    Philosophical: Is the universe a type of Turing machine?

    Here is a fun philosophical question I wonder about sometimes, given that my background is in computer science and not physics. In the field of computer science, a Turing Machine is considered to be able to carry out any computation. So, philosophically, could the universe be thought of as a...
  26. X

    What's the difference between Turing Machine and UTM?

    1 - I'm trying to see what's the difference between a Turing Machine and a universal Turing Machine. Aren't the same? 2 - If I have a Touring Machine that to solve a problem, for example, adding numbers, what is the purpose of a Universal Touring Machine?
  27. X

    Turing machine - polynomial time expression

    In the Turing Machine, the machine accepts a word if the computation terminates in the accepting state. The language accepted by the machine, L(M), has associated an alphabet Δ and is defined by L(M) = {w \in \Delta} This means that the machine understands the word w if w belongs to the...
  28. Loren Booda

    N-dimensional Universal Turing Machine?

    Can a Universal Turing Machine compute arbitrary, orthogonal sequences of integers in N dimensions for any N>0? Just an idea.
  29. W

    Troubleshooting X+y Turing Machine Example

    I am working out of Cutlands computability book and I am having trouble understanding the following example: "The function x+y is Turing-computable." Then the example lists the following specifications: q_1 1 B q_1 q_1 B R q_2 q_2 1 B q_3 q_2 B R q_2 I wanted to verify this worked...
  30. B

    Turing machine and quantum computers

    Can anyone help me...from Nielsen-Chuang "quantum computation and quantum information":how might we recognize that a process in nature computes a function not computable by a turing machine?
  31. B

    Turing machine, computable function.

    From Nielsen-Chuang:how might we recognize that a process in nature computes a function not computable by a turing machine?
  32. M

    Optimizing Turing Machine Functions: Finding the Minimum Cost and Enumeration

    Hello smart people, I am wondering if there is a process to convert a function to a Turing Machine. In other words, if I provide a list of input strings , and a corresponding output string for each input string, is there a way to find the minimum number of instructions to realize any function...
  33. T

    Programming Binary Addition with a Turing Machine

    hello, One can wonder what is the relation between the title of this thread and the subject of quantum mechanics, well, i was reading in a book about quantum computation and information and it was talking about computer science in some chapter where it shows a basic understanding of Turing...
  34. I

    Boolean expressions for Turing Machine

    Hello, I want to express Non-Deterministic Turing Machine constraint with boolean expression. The constraint is: "Cells which aren’t being read remain the same at time t+1". lets say H[i,j] means the read/write head at time i at cell j and S[i,j,k] means the symbol k at time i in cell j so the...
  35. daniel_i_l

    Can I Build a Mechanical Turing Machine Using Everyday Materials?

    As a summer project I was thinking of building an entirely mechanical Turing machine - possibly with Lego. Has anyone attempted this? Does anyone have any advice on how to design this? Thanks.
  36. C

    Turing Machine Help: Construct & Describe Work for Calculating Logic Expression

    Homework Statement I need to construct and describe work od Touring machine which will calculate the value of logical expression with Boolean operators AND and OR. The simbol of input track which match logic operator AND is *, and simbol od input track that match logic operator OR is +...
  37. C

    Complement of Universal Turing Machine - Does this exist?

    Complement of Universal Turing Machine - Does this exist?? I am kind of confused in terms of the creation of machine which does NOT (Universal Turing Machine). I mean I construct a TM which will simulate UTM and accept strings it rejects and rejects strings it accepts. So if L(UTM) defined as...
  38. T

    Solving the Two-Dimensional Turing Machine Problem

    Homework Statement A two-dimensional Turing machine has the usual finite-state control but a tape that is a two-dimensional grid of cells, infinite in all directions. The input is placed on one row of the grid, with the head at the left end of the input and the control in the start state, as...
  39. Loren Booda

    Turing machine applied to virtual reality

    How can one readily determine that the reality one experiences is real, not virtual - perhaps through Turing machine logic?
  40. 0

    Can a PTM simulate a one-tape Turing machine in O(T^2) time?

    This was a bonus problem that I missed on the last homework. A paper tape Turing machine (PTM) is a Turing machine whose tape alphabet is partially ordered, and if a is a symbol on a square of the tape, then b can only be written on that square if b is greater than a in the partial order...
Back
Top