Turing machine Definition and 33 Threads

( 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...

Continue reading ...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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

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...

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...

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...

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...

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?

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...

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

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...

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?

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

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...

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...

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...

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.

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...

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...

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

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...