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

2
votes
0answers
9 views

Finding regular expressions for which a given Turing machine halts and accepts, halts and rejects, and diverges.

Consider the Turing machine M = (Q,Σ,Γ,δ,q,F) F = {t} Q = {q,r,s,t,v,x} Σ = {a,b,c} Γ = {B,a,b,c} δ = [q,a,q,a,R] [q,b,q,b,R] [q,c,v,b,R] [q,B,r,B,L] [r,a,s,B,L] [r,b,s,B,L] [r,c,s,B,L] ...
0
votes
2answers
21 views

Examples of undecidable languages contained in 1*?

I've been given the following question Show that there is an undecidable language contained in $1^*$. But I can't think of any undecidable languages that are contained! Can someone please lend a ...
0
votes
0answers
14 views

Is the problem of determining the complement of of a given language decidable?

By which I mean, given Turing machines M and N, is determining whether L(N) is the complement of L(M) decidable or not? My instinct is that it is undecidable, but I'm unsure of how to make a formal ...
0
votes
1answer
23 views

What is turing machine for $a^i b^j c^k$ where $i=j$ or $j=k$

I am trying to construct turing machine for $a^ib^jc^k$ where $i=j$ or $j=k$. Every time I come up with solution its getting fail for some other string.
0
votes
0answers
43 views

Turing Machine Halting problem

I have come across this halting problem question during my exam preparation and can't come up with a solid proof for the following question. Question: Let L be { Ti does not halt on input i} Show ...
3
votes
2answers
50 views

What's the significance of the Church-Turing Thesis?

My understanding is that the thesis is essentially a definition of the term "computable" to mean something that is computable on a Turing Machine. Is this really all there is to it? If so, what makes ...
1
vote
2answers
18 views

Computability: is there an alternative method to decide this language?

For my computability revision I am trying to decide the language, $$L = \{ \text{all binary strings containing the pattern 001 (not necessarily in consecutive places)} \}.$$ I believe that I can do ...
0
votes
1answer
20 views

$ E_{\text{TM}} = \{ \langle M \rangle \mid L(M) = \varnothing \} $ is undecidable.

In this proof, we need to convert the input from $ \langle M,w \rangle $ to $ M_{1} $ as $ E_{\text{TM}} $’s input is only a Turing Machine. However, I couldn’t understand the construction of $ M_{1} ...
0
votes
0answers
25 views

Show the following languages are not recursive

Show that the language $$L = \{ M : M \text{ is a Turing Machine that halts on input $M$ } \} $$ is not recursive. Show that the language $$ L = \{M : M \text{ is a Turing Machine such that $L(M)$ ...
0
votes
0answers
28 views

Problem with tracing computation from Turing Machine

Transition Function of TM M start_state: q final_state: qf R denotes move right L denotes move left S denotes stop I traced the computation but not sure if it is exactly correct my problem is ...
1
vote
1answer
46 views

determining recognizable or decidable (TM that accepts a TM)

I'm having an issue determining whether certain languages are decidable, recognizable or neither. The specific languages I'm referring to are of the following form L = {<M> | for every w, M accepts ...
0
votes
1answer
78 views

is differ between distributive lattice vs semi-lattice on Turing Degrees

We know a Posed Closed under suprema but not necessarily under infima is an upper semi-lattice. We now r.e set forms a distributive lattice. But my question is why following statement is hold? I ...
2
votes
1answer
39 views

How was the busy beaver candidate for 6 states calculated?

The current busy beaver candidate on 6 states, with the original binary alphabet configuration, produces about 10^18267 1's, according to the wiki page on Busy Beaver. I could not find any working ...
1
vote
2answers
64 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 ...
2
votes
1answer
57 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
34 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
23 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
41 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
20 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
35 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
54 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
36 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
24 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$. ...
0
votes
0answers
25 views

Design a Turing machine to check whether an input is prime or not. [duplicate]

This is an assignment, I need to make a primality checking turing machine, which check whether an input is prime or not. what i've done so far is that i made this logic which is, ...
3
votes
2answers
58 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
144 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
65 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
98 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
29 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 ...
2
votes
1answer
374 views

Designing a Turing machine for Binary Multiplication

I need help designing a turing machine that will compute the following f(x,y) = x*y How to approach this problem in binary base? This is a assignment so I don't ...
-5
votes
1answer
98 views

Some inference in Automaton and Decidable Problems [closed]

Anyone could correct me that the following inference is True: ( G is a Context Free Grammar) There is an algorithm that decides whether the complement of $L(G)$ (language generated by $G$) is empty ...
3
votes
1answer
60 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
44 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
34 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
31 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
28 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
68 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
67 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
124 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
33 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
16 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
55 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
59 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
53 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
34 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
23 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 ...