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

0
votes
0answers
7 views

DTM that halts on a minimum one input

I am trying to show that this is Turing Recognizable. The language A, that is a DTM that halts on a minimum of one input. My justification is that of course it is because, you just need to check ...
1
vote
1answer
22 views

How to simulate a 3-stack automaton with a 2-stack automaton?

Since a 2-stack automaton is Turing-equivalent, it is possible to simulate a 3-stack automaton with just a 2-stack automaton. But how so? How it is normally done?
0
votes
0answers
9 views

Generalizing equal turing machine problem

I know that $EQ_{TM} = \{<M_1,M_2> | L(M_1)=L(M_2)\} \notin RE \cup CO-RE$ Can I generalize and say that $L' = \{<M> | L(M) = C \} \notin RE \cup CO-RE$ Where C is the language of any ...
0
votes
0answers
9 views

Turing Machine Membership problem and how to prove its undecidable

ATM = {$<m, w>$ | M is a Turing Machine that accepts string w}. How can I prove that ATM is undecidable? Here's what I have so far: Any decidable problem is accepted by a Turing Machine. It ...
46
votes
3answers
2k views

Are there any Turing-undecidable problems whose undecidability is independent of the Halting problem?

To be more specific, does there exist a decision problem $P$ such that given an oracle machine solving $P$, the Halting problem remains undecidable, and given an oracle machine solving the Halting ...
-1
votes
0answers
19 views

given a language L proof via direct reduction ATM < L.

Regarding my previous question: Direct Reduction, Turing machine and a DFA here agaian: > L ={ < M , D >| M is s TM and D is a DFA so that L(M) = L(D)} ...
0
votes
0answers
9 views

inverse proof of closed under union

I am being posed the following question: given are languages $L_1, L_2, L_3 $ and $ L_4$. $L_1$ is a decidable language and $L_2$ and $L_4$ are both recognizable languages. Considering $L_1 = L_2 ...
0
votes
0answers
30 views

Direct Reduction, Turing machine and a DFA

I have been reading and I am trying to understand the reduction when it comes to truing machine. This is how I understand it: it means that it reduces problem A into problem C. But I am not quite sure ...
1
vote
0answers
17 views

Prove that exists undecidable subset of $\{1\}*$

Hello my dear friends! I have following problem: Prove that exists undecidable subset of $\{1\}*$ The problem is that I don't know how to start. In real I don't what does it mean undecidable set ?
0
votes
0answers
16 views

Prove that language $X$ is not decidable

$$X =\{\langle M, w\rangle \mid\text{$M$ has one tape and never modifies portion of the}$$ $$\text{tape that contains the input $w$}\}$$ And my proposition: Let $@$ will be character such that there ...
1
vote
1answer
18 views

prove that language is not deciable by reduction

I show you my approach to one problem, and try to assess it. Show that following language is not decidable: $L=\{\langle M\rangle|\text{M is Turing Machine and M has one or more unreachable state} \}$ ...
1
vote
0answers
22 views

prove that language is not decidable (string and reverse)

Prove that $T=\{\langle M\rangle\mid M \text{ is TM that accepts $w^R$ iff it accepts $w$}\} $ is not decidable. I have no idea how to start. Help me, please
0
votes
1answer
17 views

Deterministic Turing machine for a duplicate concatenation of a string

What's the best approach for building a deterministic Turing machine for the language $$L = \{vv : v \in \{a,b\}^+ \}$$ where there is no midpoint marker in the string? How can we determine where ...
4
votes
1answer
49 views

What breaks the Turing Completeness of simply typed lambda calculus?

On the Wikipedia page about Turing Completeness, we can read that: Although (untyped) lambda calculus is Turing-complete, simply typed lambda calculus is not. I am curious as to what exactly ...
5
votes
0answers
61 views

What Constitutes a Pattern

Mathematics is often referred to as the "study of patterns." What I'm wondering is whether there is somehow a technical way to describe a pattern. For the length of this question let's assume that ...
0
votes
1answer
19 views

Turing machine that accepts even length strings

Can someone help me with some tips on how to create a turing machine that only accepts even length strings with an input alphabet of {0,1}?
9
votes
2answers
1k views

Show that the question “Is there life beyond earth?” is decidable

I was given a question to prove that there exists a turing machine that solves the question Is there life beyond earth? and is decidable. I actually don't understand how to show a turing ...
1
vote
0answers
22 views

Why does a certain turing machine only accept regular languages?

why does a single tape turing machine, which can not write on the part of its tape containing the input, only accept regular languages? I am asking this because this question is being opposed to me ...
0
votes
2answers
55 views

Example of recursively enumerable languages that under intersection are $\emptyset$

I am trying to think about an example of a recursively enumerable languages $L_1,L_2 \in RE $ and $L_1,L_2 \notin R $ that satisfy: $L_1 \cap L_2 \in R $ I know that it will be probably something to ...
3
votes
1answer
69 views

Is it possible to show that a particular theorem or its negation is provable, without knowing which of the two is true?

I've been thinking about this for a while: as far as we know, is it possible that for a particular statement $\sigma$ of $\textsf{ZFC}$, we can prove that $(\textsf{ZFC} \vdash \sigma) \vee ...
0
votes
1answer
20 views

Languages in coNP

if a language $L \in$ coNP, i.e. it's complement is in NP, then does L have a deterministic turing machine that decides it? i think that this is false, but am unsure how to show it? my guess is using ...
0
votes
0answers
16 views

determining whether a turing machine

For $i\in \mathbb{N}$, define $L_i :=${$ ⟨M⟩ |$ On input $101$ M halts after at most i steps} For any fixed i the language $L_i$ is decidable as if there is no end state up to the i$^{th}$ position ...
0
votes
0answers
23 views

To prove a language is not recursive

Prove the language $$L_1=\{\sigma\in\{0,1\}^*|\sigma \text{ codes a TM which accepts at least one word }\}$$ is not recursive. I think it has something to do with $$L=\{\sigma\in\{0,1\}^*|\sigma ...
0
votes
0answers
26 views

Simple Turing machine problems [duplicate]

I'm trying to go over some review problems regarding Turing Machine recognizability, and am still pretty confused about the following problems. This is the only information we are given in the problem ...
0
votes
1answer
109 views

Turing Machine recognizability

I'm trying to go over some review problems regarding Turing Machine recognizability, and am still pretty confused about the following problems. This is the only information we are given in the problem ...
4
votes
2answers
56 views

Can you solve the halting problem for a single, non-universal Turing machine?

So, I'm familiar with the halting problem and its proof. However, I also understand that the proof is for any universal machine $U$; that is, the set ...
2
votes
1answer
43 views

Designing a Turing Machine - low level transitions

I couldn't figure out how to proceed with this question. Preparing for the finals, can someone explain how to do this step by step? Design a TM, write low level transitions for $\{a^i b^j :i ≤ j ≤ ...
0
votes
2answers
259 views

Why are every finite language decidable?

I don't understand why every finite language is decidable. For example, if I have an infinite set of strings L over an alphabet E, why is there a Turing Machine M that decides L? I understand the ...
1
vote
1answer
29 views

Let $LOOP_{TM}$ be descriptor language of all touring machines that won't halt for any input. Show reduction of $HALT_{TM}$ to $LOOP_{TM}$

Question from Homework that I'm having difficult to answer on: Let $LOOP_{TM} = \{\langle M\rangle \mid \text{M is a TM that does not halt on any input w}\}$ Let $LOOP_{TM}$ be descriptor ...
2
votes
1answer
17 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
31 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
16 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
34 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
1answer
54 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
64 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
25 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
22 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
28 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
35 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
62 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
86 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
42 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
71 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
59 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
35 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
28 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
23 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
115 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 ...