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

1
vote
2answers
76 views

Are there any known noncomputability proofs that do not rely on the halting problem?

I have looked around and thought of this for a while, and I have not found or been able to construct any proof that a problem is not decidable, without said proof being fundamentally equivalent to ...
1
vote
1answer
62 views

an strange set $ \Xi_A =$ {$ n \in N | \exists k^2 \in A $ s.t $ k^2 \leq n$} is decidable ?, an Interview questions?

We are some student that had an Interview for M.sc Entrance Exam. This interview has two part and one multiple choice question. We see 1 strange question that some definition is so strange for us, we ...
-1
votes
1answer
38 views

Show that every recursively enumerable set is accepted by a Turing machine with only two non accepting states and one accepting state.

A recursively enumerable set is a set where you can write a program that will output each element in the set: E1, E2, E3... it's okay if this program never stops. For more info look here : ...
0
votes
1answer
40 views

Application of wavelet analysis in computer science

I am doing research in computer science (data mining), do you think wavelet analysis is useful for me?
0
votes
1answer
43 views

Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ [closed]

Suppose A is a arbitrary subset of Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ with respect to $ n \in A \Longleftrightarrow n \in A_n $ and $A_n$ is finte, which of them is True? a) A and ...
0
votes
0answers
24 views

Non-deterministic multiplication algorithms

Are there any algorithms for non-deterministic Turing machines that can compute the decision problem $mn=x$ (where $m=O(n),x=O(n^2)$) faster than the equivalent deterministic algorithm? Equivalently, ...
12
votes
4answers
2k views

How large is the set of all Turing machines?

How large is the set of all Turing machines? I am confident it is infinitely large, but what kind of infinitely large is its size?
0
votes
0answers
138 views

Showing that Turing-recognizable languages are closed under union

I'm reading "Theory of Computation" by Michael Sipser and I've encountered a solution (provided by the book) that I don't understand. The question: Show that the collection of Turing-recognizable ...
3
votes
0answers
79 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
41 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
50 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
79 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
277 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
67 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
136 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
882 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
66 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
56 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
50 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
39 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
80 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
90 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
147 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
50 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
39 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
211 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
114 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
81 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
38 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
26 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
84 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
31 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
73 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
50 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
23 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
167 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
59 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
39 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 ...
1
vote
1answer
62 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
42 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
32 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
122 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}$ ...