This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.

learn more… | top users | synonyms

3
votes
0answers
65 views

Do there exist a pair of 'orthogonal' non-halting Turing machines?

I'll explain what I mean by orthogonal, which is probably a poor choice of words on my part. Given two Turing machines $\lambda $ and $\tau$,and two inputs $i$ and $j$. lets say $\tau(i) \preceq ...
2
votes
0answers
39 views

Find Pi number using Turing Machine

What is the most convenient and fast way to find first $n$ binary digits of $\pi$ using Turing Machine?
0
votes
0answers
45 views

Design a Two-Tape Turing Machine which generate Palindrome

For e.g I have a String on a tape, $Blank|1|0|1|0|Blank$. Now I have to Use two tape and Reverse this string into second tape. First tape =$Blank|1|0|1|0|Blank$. ...
3
votes
2answers
71 views

NP-Complete and Poly Time Reduction Problems [closed]

I Took Some Priminlairity Learning Method on Complexity Theory. I get trouble with some definition. anyone could help me, Why the mentioned statement is True? if a Problem A can be reducible to ...
2
votes
1answer
264 views

Construct a Turing-Machine for Factorial(unary)

I am designing a turing machine which calculates the factorial of any given input for example, $3! = 3.2.1$, on tape it will look like this $Blank|1|1|1|Blank$ What I have done so far is that, I made ...
-2
votes
1answer
66 views

some Graph and NP Theory Problems [closed]

my instructor solve the following problem, that which of the following is into a NP Class? ...
4
votes
0answers
125 views

Designing a turing machine for primality check.

I am designing some turing machines, so far I have made Binary Addition and subtraction. Now I've been thinking that what if turing machine can check if the number is prime or not. Lets suppose we ...
0
votes
1answer
31 views

Construct a Turing Machine M' such that if M accepts a then M' accepts a and if M doesnot then M' does not halt

Give a TM $M$. Construct a Turing Machine $M'$ such that 1)if $M$ accepts $a$ then $M'$ accepts $a$ and 2)if $M$ does not accept then $M'$ does not halt. I am thinking about a 2-tape TM, with ...
3
votes
1answer
780 views

Designing a Turing machine for Binary Multiplication

I need help designing a turing machine that will compute the following $$f(x,y) = x\times y$$ How to approach this problem in binary base? This is a assignment so I don't want anyone to solve it ...
3
votes
1answer
61 views

Axioms defining a Turing machine

I have found the following characterisation in axiomatical terms of a Turing machine: $Q_0(q)\rightarrow T(q)$ $S_0(x)\rightarrow S(x)$ $C(x)\rightarrow S(x)$ $Q_0(q)\land T(qx)\land ...
2
votes
1answer
54 views

Designing a Turing machine for $a^n$ $b^{2n}$ $a^n$

I am new to theory of automata, and i have a little knowledge of designing a turing machine, I am stuck in this question which is given to us as an assignment, $\{$$a^n$ $b^{2n}$ $a^n$ : ...
0
votes
1answer
45 views

How to prove that One Way infinite tape Turing Machine is Turing Complete?

I have always worked in 2 way infinite tape and most probably I think that was the first represented as Turing Machine. How can I emulate One-way Turing Machine to Two way Turing Machine.
0
votes
0answers
36 views

Turing machine notation question.

I'm a bit confused on some of the notation being used for turing machines in one of our exercises in class. The question gives us a string α ϵ {0,1}* and the function int(α) that changes a binary ...
1
vote
1answer
29 views

Turing machine recognizing language $L=\{a^ib^{i-j}c^j|i>j\ge1\}$

I am having some trouble with designing a Turing machine that recognizes the language: $L=\{a^ib^{i-j}c^j\big|i>j\ge1\}$ For example, word accepted by TM: $w=aaaaabbccc$ To be more precise, I ...
0
votes
1answer
32 views

Does stay put TM recognizes same languages as standard TM

I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or ...
1
vote
2answers
78 views

turing machine with exactly 42 states / state that is visited at least 42 times

I am trying to solve the following problems: Proof wether the following problems are decidable/undecidable: Given turing machine M: Does M have exactly 42 states? Given turing machine M: Does M ...
3
votes
0answers
81 views

Show that minimal CFG is undecidable (Sipser 5.36)

Question: Say that a CFG (context-free grammar) is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{\text{CFG}}$ = $\{\, \langle G \rangle$ | $G$ is a ...
3
votes
1answer
140 views

Using Extended Rice's Theorem to Prove Decidability

I have a Turing Machine M. Let L be the set of all strings representing the encoding of M that has input alphabet {1,2}, where M accepts infinitely many strings that start with 1 and finitely many ...
1
vote
1answer
49 views

two way infinite turing machine?

A Single tape turing machine is generally unbounded to right and starts from left. Read/write head moves to right from left after consuming a symbol. But what if we make left side unbounded too and ...
2
votes
1answer
37 views

Can a halting turing machine write any combination on a tape before halting?

Assume, a halting turing machine uses $n$ items of the tape. Can it write every possible combination on this $n$ items before halting ? We start with a blank tape. Example $n=2$ , alphabet $0,1$ ...
0
votes
0answers
22 views

program which it's power is equal to LBA

Can anyone give an opinion about this matter: what is the smallest program which it's power is equal to LBA Turing machine(Linear bounded automata are acceptors for the class of context-sensitive ...
0
votes
1answer
154 views

Help understanding a 'reversing a string' Turing Machine

I am having a bit of a confusion understanding some transitions in a Turing Machine. Its an example from Introduction to Languages and the Theory of Computation by John C. Martin. I've attached the ...
0
votes
1answer
101 views

How to design a turing machine that recognizes any language?

here I have a problem. Design a turing machine that recognizes the language of all strings of even length over alphabet {a, b}. soln: Let turing machine is $Tm =(Q, \Sigma, \Gamma, \delta, q_0 , ...
1
vote
0answers
75 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
0
votes
0answers
37 views

Turing's Corrections on his 1936 paper On computable Numbers

On Turing's proof of the "Lemma 1" (If $\ S_{1}\,$ appears on the tape in some complete configuration of$\ M\,$,then$\ Un(M)\,$is provable) He states that we are unable to deduce$\ F^{n+1} \to ...
0
votes
0answers
24 views

is it in fact impossible to construct a machine which can know if a macine ever prints a character?

In $\S\ 8$ of his paper "On computable numbers, with an application to the Entscheidungsproblem" Turing uses his proof that $\mathfrak{D}$ (a machine which given the S.D. of another machine ...
0
votes
0answers
82 views

could a machine $\mathfrak{D^+}$ be made to produce $\beta$ so the diagonal argument could be used on computable numbers?

I was reading Turing's paper "On computable numbers, with an application to the Entscheidungsproblem" and while reading $\S\ 8$ (his proof that computable numbers are enumerable) and his proof that ...
0
votes
0answers
28 views

Designing a turing Machine belonging to a language

Im trying to learn the concept of turing machines.I have understood the basic stuff like its a simple mathematical model of a computer and its parts.Now im asked to create a turing machine. ...
1
vote
1answer
71 views

Is my Turing Machine (Transition Function) correct for finding if a string is of even or odd length?

I've been asked to create a formal Turing Machine (by means of a transition function) to which takes a string $a^n \in$ {a}* and decides whether it is an even or odd length. What I have made is the ...
0
votes
0answers
27 views

Show that L4 is decidable (i.e., recursive), by describing a Turing machine that decides L4.

L4 = {<M, w> | M is a turing machine, w is a string, and M never moves it's head left on input w} I know that M is allowed to move to the head to the left ...
1
vote
1answer
48 views

Is universality decidable?

Is there a turing machine which can take any other TM T as input and decide whether T is a universal turing machine?
0
votes
1answer
22 views

Multitape Turing machine with multiple non-blank tapes

A multitape Turing machine is defined to have input only appear on one tape, with the rest of the tapes blank. Are there any formulations of a Turing machine that allow other tapes to be not blank? ...
0
votes
1answer
140 views

Relationship between the Turing Machine and RAM Models

Could you tell me which is the relationship between the Turing Machine and RAM Models??
0
votes
1answer
54 views

Recursively enumerable sets: the halting set

Wikipedia on the Halting Problem: The conventional representation of decision problems is the set of objects possessing the property in question. The halting set $K := \{ (i, x) ~|~ \textrm{program ...
1
vote
0answers
36 views

Dual Turing Machine Simulation

(1) Define a Turing Machine that simulates a Dual Turing Machine (DTM)?. A dual Turing Machine is defined as a Turing Machine with 2 heads and 2 tapes. At every step, the DTM can read from either ...
2
votes
1answer
61 views

Zermelo–Fraenkel Set Theory

So I'll try keeping this real short and simple. Assume that language $L$ is defined as $\{ x\in \{0,1\}^* \}$ (finite binary strings) such that $x$ encodes a proof in ZFC that 4 is a prime number. I ...
0
votes
1answer
39 views

Simple Turing Machine

Having a bit of trouble designing a turing-machine which recognizes the following language. The alphabet is $\Sigma$ = {a,b,c}. $$ L_2 = \{wcw^R | w \epsilon \{a,b\}^*\} $$ The part which messes ...
0
votes
1answer
28 views

cubic integral roots

I am trying to find the integral roots (if they exist) of the following polynomial. Additionally, it would be helpful if someone could explain an algorithmic approach to solving this. $$ f(x) = 2x^3 ...
0
votes
2answers
120 views

If all infinite r.e. languages have an infinite recursive subset, then do co-r.e. languages not have such subsets?

If all infinite r.e. languages have an infinite recursive subset, then can we take it to be true that co-r.e. languages do not have such subsets by complemence?
2
votes
1answer
25 views

Turing machine that goes left on first symbol

I have a turing machine with transitions given by the following table I'm inputting the string aaaa. So if I look at the first symbol "a" in state A, it says to replace it with an X, go into state ...
2
votes
0answers
66 views

How to find the shortest path of a graph in a turing machine

I'm reading about Turing machine and I saw some examples as: Let $M_{1}$ a Turing Machine and the language $B = \{w\#w \vert w \in \{0,1\}^{*}\}$, We want $M_{1}$ to accept if its input is a member of ...
0
votes
0answers
23 views

If we create a partition of $E_{TM}$ by listing its elements, are the subsets undecidable?

Consider the set $E_{TM} = \{ <M>$ | M is a TM such that $L(M) = \emptyset\}$ The set of all Turing Machines in countable. Thus $E_{TM}$ is countable. Suppose we list all elements of $E_{TM}$ ...
3
votes
0answers
132 views

Whats the connection between Turing machine and First order logic?

Today in my Computing class i came across the theorem which states that., If language $L$ and $\Sigma^*\setminus L$ are recursively enumerable then L is recursive (total turing machine). Which looks ...
3
votes
1answer
63 views

Is there a recursive injective and surjective function f:N→PRF?

It is well known and easy to see that it is possible to effectively number Turing Machine codes. That is, there is an injective and surjective recursive mapping $g:\mathbb N\to {\rm TM}$: each Turing ...
1
vote
0answers
32 views

BusyBeaver growth: “simple” proof

I just try to prove that $BB(n)$ (BusyBeaver-Function) grows faster than any other computable function. Maybe someone can check the proof? $f(n)$ is a computable function which grows to infinity: ...
3
votes
1answer
153 views

Challenge on Some Language and PDA

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
1
vote
7answers
219 views

Text books on computability

I collected the following "top eight" text books on computability (in alphabetical order): Boolos et al., Computability and Logic Cooper, Computability Theory Davis, Computability and unsolvability ...
2
votes
0answers
88 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on ...
1
vote
1answer
29 views

Gathering nonconsecutive 1's by a Turing machine

S. Barry Cooper comments his output convention for $\mathbb{N}\rightarrow\mathbb{N}$ Turing machines like this: Outputting $n$ as $n$ possibly nonconsecutive $1$'s is very natural. [...] We can ...
0
votes
1answer
25 views

Non-Deterministic Polynomial Time Algorithm

My understanding is that for problems where there are an exponential number of possible solutions, a non-deterministic turing machine (NTM) is able to solve it in polynomial time because an NTM can ...