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
44 views

Are elimination of lambda and closure expressions always possible?

As proofed the lambda calculus, which uses higher-order functions (passing functions as arguments), is turing complete. This makes me wonder if one of the following statements is true: Are ...
-1
votes
1answer
19 views

If Language $L_1$ is accepted by a Pushdown Automata and Language$ L_2$ by a Turing Machine, Is $L_1 \cup L_2$ accepted by a Pushdown Automata?

Let $L_1$ be a language recognized by a Pushdown automaton and let $L_2$ be another language recognized by a Turing machine. Is $L_1 \cup L_2$ recognized by a Pushdown automaton? Prove your answer.
0
votes
0answers
28 views

For what functions ($T_1, T_2: N \to N$) there is oracle B and language $L=L_b$ that $L \in ND-TIME(T_2)^B$ but $L \notin TIME(T_1)^B$

I had this question: For what functions ($T_1, T_2: N \to N$) there is oracle B and language $L=L_b$ that $L \in ND-TIME(T_2)^B$ but $L \notin TIME(T_1)^B$ Only one answer is the correct one: A. ...
1
vote
1answer
31 views

Recursive languages , please check whether my explain is correct?

Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows. $$L = \begin{cases} (0+1)^* & \text{if } P = NP \\ \phi & \text{otherwise} \end{cases}$$ Which of the following ...
2
votes
1answer
31 views

Is the random function not computable?

Some days ago I read about the Church-Turing Thesis and it establishes that any function can be described as an algorithm, so being defined as computable, and no function mismatches the Thesis. But, ...
1
vote
1answer
54 views

Busy Beaver simple nonhalting rule

Regarding the busy beaver function, what's a simple rule to prove that the machine runs forever in one direction? I believe there's something about the machine not backtracking far enough before it ...
3
votes
1answer
63 views

Do circular tapes exist in Turing Machines?

I've been looking for information about this topic without success. Have someone described Turing Machines over circular tapes instead lineal and infinite? Like the tape could be described with ...
1
vote
1answer
45 views

Alphabets of Turing Machine

I'm not completely sure about equivalence of two definitions of Turing machine. The first one states that Turing machine has a finite alphabet $\Sigma$, set of states and some rules. Turing machine ...
1
vote
1answer
62 views

Meaning of “existence” for an uncomputable function related to the Halting Problem

Take the set of all Turing Machines $TM$, we can divide this set in two: $P$, the set of all Turing Machines that will halt if starting from an empty tape, and $Q$, its complement: the set of all ...
0
votes
1answer
101 views

What is meant by “finite algorithm” in Turing's definition of the computable numbers?

In a comment thread on SlateStarCodex, I made a philosophical point the "realness" of the reals, in the process of which I attempted to summarize the definition of Turing-computable numbers: ...
5
votes
2answers
122 views

Is there a turing machine for which halting is equivalent to the Axiom of Choice or its negation?

As seen in "A Turing machine for which halting is outside ZFC", Gödel's incompletness theorem can that there a turing machines for which halting can not be decided. My question is, is there a turing ...
-1
votes
2answers
69 views

Can Incompleteness be Computable?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
0
votes
1answer
46 views

Prove $K_4-Cover$ is NP-Complete

I'm studying for a computational theory exam, and as part of my studying I'm trying to solve previous years' exams. I have come across this problem and I'm having some difficulty with it: Let $ G ...
1
vote
1answer
34 views

Is PA+ TM doesnt halts consistent?

Suppose there isnt a proof in PA whether some TM halts or not. Suppose further that TM doesnt halt and PA is consistent. Is PA+TM halts necesserely consistent? Is PA+TM doesnt halt necesserely ...
0
votes
0answers
24 views

Reduction to Halting problem

I have the following problem. Prove by reduction to the halting problem, that $L:=\left \{ <M> | L(M)=\emptyset \right \}$ is undecidable. L(M) is the defined as: $L(M) = \left \{ w \:| M ...
1
vote
2answers
74 views

Number of finite-state machines with $n$ states, output alphabet size $a$, and binary input

How many FSMs are there where the machine has $n$ states, reads a binary symbol at each time-step, and may or may not output a symbol from an alphabet of size $a$ after each transition?
4
votes
5answers
162 views

Where does this argument showing there are uncountably many TMs fail?

This argument comes up once every while on Lambda the Ultimate. I want to know where the flaw is. Take a countable number of TMs all generating different bitstreams. Construct a Cantor TM which runs ...
0
votes
0answers
10 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
41 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
15 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
62 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 ...
51
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 ...
0
votes
0answers
21 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
42 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
59 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
18 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
35 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
68 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
45 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
73 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
109 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
116 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
35 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
58 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
91 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
22 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
23 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
31 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
28 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
126 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
98 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
49 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
951 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
35 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
28 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
45 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
20 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
181 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
85 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 ...