What is Turing: Definition and 66 Discussions

Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical computer science, providing a formalisation of the concepts of algorithm and computation with the Turing machine, which can be considered a model of a general-purpose computer. Turing is widely considered to be the father of theoretical computer science and artificial intelligence.Born in Maida Vale, London, Turing was raised in southern England. He graduated at King's College, Cambridge, with a degree in mathematics. Whilst he was a fellow at Cambridge, he published a proof demonstrating that some purely mathematical yes–no questions can never be answered by computation and defined a Turing machine, and went on to prove the halting problem for Turing machines is undecidable. In 1938, he obtained his PhD from the Department of Mathematics at Princeton University. During the Second World War, Turing worked for the Government Code and Cypher School (GC&CS) at Bletchley Park, Britain's codebreaking centre that produced Ultra intelligence. For a time he led Hut 8, the section that was responsible for German naval cryptanalysis. Here, he devised a number of techniques for speeding the breaking of German ciphers, including improvements to the pre-war Polish bombe method, an electromechanical machine that could find settings for the Enigma machine. Turing played a crucial role in cracking intercepted coded messages that enabled the Allies to defeat the Nazis in many crucial engagements, including the Battle of the Atlantic. Due to the problems of counterfactual history, it is hard to estimate the precise effect Ultra intelligence had on the war. However, Professor Jack Copeland has estimated that this work shortened the war in Europe by more than two years and saved over 14 million lives.After the war, Turing worked at the National Physical Laboratory, where he designed the Automatic Computing Engine (ACE), one of the first designs for a stored-program computer. In 1948, Turing joined Max Newman's Computing Machine Laboratory, at the Victoria University of Manchester, where he helped develop the Manchester computers and became interested in mathematical biology. He wrote a paper on the chemical basis of morphogenesis and predicted oscillating chemical reactions such as the Belousov–Zhabotinsky reaction, first observed in the 1960s. Despite these accomplishments, he was never fully recognised in his home country during his lifetime because much of his work was covered by the Official Secrets Act.
Turing was prosecuted in 1952 for homosexual acts; the Labouchere Amendment of 1885 had mandated that "gross indecency" was a criminal offence in the UK. He accepted chemical castration treatment, with DES, as an alternative to prison. Turing died in 1954, 16 days before his 42nd birthday, from cyanide poisoning. An inquest determined his death as a suicide, but it has been noted that the known evidence is also consistent with accidental poisoning.
In 2009, following an Internet campaign, British Prime Minister Gordon Brown made an official public apology on behalf of the British government for "the appalling way he was treated". Queen Elizabeth II granted Turing a posthumous pardon in 2013. The "Alan Turing law" is now an informal term for a 2017 law in the United Kingdom that retroactively pardoned men cautioned or convicted under historical legislation that outlawed homosexual acts. Turing has an extensive legacy with statues of him, many things named after him including an annual award for computer science innovations. He appears on the current Bank of England £50 note, which was released to coincide with his birthday. A 2019 BBC series, as voted by the audience, named him the greatest person of the 20th century.

View More On Wikipedia.org
  1. fresh_42

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

  2. PainterGuy

    Is Alan Turing given too much credit when it comes to computers?

    Hi, Is Alan Turing given too much credit when it comes to computers? He is presented as someone who played a pivotal role with the realization of a computer. What Turing did as an answer to Hilbert's problem was a great achievement from mathematical point of view. Alan Turing was mathematician...
  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. fresh_42

    Explore Alan Turing's Computable Numbers & Generate Pi with Python

    I found this article about Alan Turing and his concept of Turing machines on the AMS website. Since we often get questions about countability and computability I thought it is worth sharing. https://blogs.ams.org/featurecolumn/2021/12/01/alan-turing-computable-numbers/ It also contains a Python...
  5. BillTre

    Turing Prize goes to Pixar Computer Graphics Pioneers

    Here is a NY Times article on this. They were recognized for their work on three-dimensional computer graphics and get $1,000,000. Besides Hollywood special effects, their techniques are used in video games, and virtual reality (more useful now in the age of social distancing).
  6. GlenLaRocca

    Turing Test: Respectful Criticism and Cultural Differences

    Summary: Turing I have great respect for nearly all of Turing's work but as for the Turing Test I have a lot of problems. My life has taken me through many layers of the socio-economic spectrum, and I have learned a few things about my fellow humans that Turing may not have had the...
  7. 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...
  8. 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...
  9. W

    Comp Sci Problem on undecidable problems

    I should first note that I am not a compsci student, and have not learned the "formal" way of using "Languages" to solve such problems. All I have are the two definitions provided above. Thanks! 1b) This is the Halting problem: Undecidable 1c) I have a feeling that this is decidable, since if...
  10. 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...
  11. G

    I Can Turing Machines Understand Infinity?

    I had a conversation with someone once upon a time (it was quite a while back actually), and we came to the question of whether or not Turing machines could ever understand infinity. We agreed that we as humans are intimate with the extant and divisible infinities mainly through our...
  12. binbagsss

    Mathematical Biology- Neumann BCs, Turing Analysis

    This is probably a stupid question but I have Neumann BC boundary : ## \nabla u . \vec{n} =0## (same for ##v##)conditions for the following reaction-diffusion system on a [0,L_1]x[0,L_2]x...x...[0,L_n] n times in n dimensional space so ##u=u(x_1,...,x_n,t)## is a scalar I believe? so that ##...
  13. 2

    Is this a Turing-complete machine?

    Say a Turing machine is simulated by the following rules: A number of states can be defined. Each state is defined by : specifying what the head writes in the current cell in case of each symbol of the alphabet specifying where the head moves (left or right) in case of each symbol of the...
  14. 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...
  15. cobalt124

    I Enumerate all 1-state Turing Machines

    Hi, using the definition of a TM from https://en.wikipedia.org/wiki/Busy_beaver a 1-state TM would have: one "operational" state a, plus the Halt State h a tape alphabet of 0,1 a tape initially all zeros Given this the possible 5-tuples a 1-state TM transition table could have are: (current...
  16. nomadreid

    I Extension of Turing computable

    The short version: If you had an infinite amount of time, would the standard proof for the insolubility of the halting problem still work? The longer version: A simple proof that there are non-computable functions can be easily seen by the fact that there are only countable number of Turing...
  17. G

    Turing Machines: Classifying for Decidable Problems

    It's been a while since I've done this, but the question spurred on. Is there any sort of named class that a machine that can decide on all Turing decidable problems would belong to? Edit: Actually, I guess it would be Turing if you could program it to decide on a particular problem.
  18. 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...
  19. 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...
  20. 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...
  21. 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...
  22. 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...
  23. 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?
  24. B

    Symbol in Alan Turing's On Computable Numbers

    In Alan Turing's On Computable Numbers, he explains in his second paragraph the general notion of computable numbers. In doing so, he writes "In [symbol][symbol] 9, 10 I give some arguments...". I will include a screenshot of these symbols in this post. Do any of you know what these symbols...
  25. J

    Numerically solving system of four PDEs

    Hi Forum, I'm trying to use Mathematica to graphically explore a system of four PDEs, as defined in Yang et al. (2002). Spatial Resonances and Superposition Patterns in a Reaction-Diffusion Model with Interacting Turing Modes. Physical Review Letters 88(20). The equations are: \frac{\partial...
  26. 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!
  27. 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??
  28. 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...
  29. 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...
  30. J

    Help plotting interacting Turing modes

    Hello, everybody. I'm trying to replicate plots from Yang et al. 2002. Spatial resonances and superposition patterns in a reaction-diffusion model with interacting Turing modes. Phys. Rev. 88(20) using Mathematica, to explore specifically under what parameter values the pattern of...
  31. D

    Can Turing Machines Be Represented by Polynomial-Sized Circuits?

    How do you show that every polynomial-time turing machine has a family of equivalent polynomial-sized circuits?
  32. 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...
  33. P

    Why Turing Machines are important

    Can someone explain to me, one with extremely limited knowledge of the concept of Turing Machines, what these hypothetical machines help us understand or accomplish in computer science?
  34. Jim Kata

    Turing Completeness Lambda Calculus

    I have been kind of trying to teach myself some ideas from CS. What does Turing completeness mean exactly? For example, Lambda Calculus is Turing complete. What does that mean and how do you prove that?
  35. nomadreid

    Probabilitstic versus non-deterministic Turing machines

    Although this question is more theoretical than most of the threads in this rubric, it still seems to me to fit the description "Computer Science". If I am wrong, perhaps someone would tell me where the question belongs. The question is as follows: After reading the descriptions of...
  36. 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...
  37. 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...
  38. 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...
  39. A

    Set cardinality, Turing encoding, and inductive proofs

    I'm going to construct an ordered set, and I'd like to ask some questions about it; and in particular consider coding problems about this set and sets in general (Turing tape encoding). Start with: A={ } And, allow a mutable temporary set, initialized with: T={ } and an iterator: set n=0 For...
  40. P

    MHB Remembering Alan Turing: A Pioneering Computer Scientist

  41. zoobyshoe

    Reexamining The Death of Alan Turing

    Alan Turing, of Turing Test fame, would be 100 today. (Google has a clever animation to celebrate.) In conjunction with that anniversary, this story was posted which questions the usual story of his death: http://www.bbc.co.uk/news/science-environment-18561092
  42. 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?
  43. 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...
  44. C

    Turing Machines & Undecidability

    Homework Statement I have a question regarding undecidable languages. Let L1 = { M | M is an encoding of a Turing machine that accepts any input} and L2 = { M | M is an Turing machine with at most 100 states}. Is L1 intersect L2 decidable? Homework Equations The Attempt at a...
  45. J

    How Can Prime Numbers Encode Turing Programs?

    Homework Statement Assign a code number n(P) to every Turing program P. Homework Equations N/A The Attempt at a Solution Let pi denote the ith prime number. Let Q = {q0,q1,...} be internal states, let {B,1} denote tape symbols and let {L,R} denote direction symbols. Assign a code...
  46. J

    Assigning Godel Numbers to Turing Programs

    I am working through a computability theory textbook and right now the author is discussing assigning Godel numbers to each Turing Program. To do this, he suggests assigning each internal state, each of the elements of {1,B} and each of the elements of {L,R} a number. Then using these numbers...
  47. 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.
  48. R

    Nonlinear Analysis of Reaction Diffusion Equations for Turing Pattern Selection

    So if I have a general reaction diffusion equation and perform a liner stability analysis on it I would only get the domains in which Turing Instability occurs but not which pattern I would get (stripes , spots etc.). So I need to use a nonlinear analysis. One technique people use is a...
  49. 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...
  50. J

    Alan Turing and his homosexuality

    I remember I watched a documentary where they mentioned Alan Turing, a British logician, was considered a security risk once his homosexuality became open. I exactly remember they used the word "security risk". Why was he considered a security risk? I have been to Wikipedia and seems answers...