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

Must an algorithm terminate?

I am confused. Sometimes i read about terminating and not terminating algorithms. I almost always read these things in the context of turing machines. This means to me: There are algorithms which ...
0
votes
1answer
37 views

How could I design a turing machine that prints all natural numbers on its tape in order?

How one could implement a turing machine that prints all natural numbers of its tape in order. Two consecutive numbers are separated on the tape with the symbol #. The tape should look like this: ...
0
votes
0answers
39 views

How could I modify a Turing machine that attempts to move the head past the leftmost square(crash) on some inputs so that it doesn't crash at all?

Suppose that M is a TM that crashes on some inputs. How would I modify M so that the new machine accepts the same language but does not crash on any input ?
-1
votes
1answer
62 views

Show that every finite subset of $\{0,1\}^*$ is recursive [closed]

How can I show that every finite subset of $\{0,1\}^*$ is recursive ?
0
votes
1answer
113 views

Read-only Turing machine recognizes only regular languages?

Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages. According to wiki : A read-only Turing machine or ...
0
votes
0answers
27 views

Does 3-SAT reduce to 3-CNF-SAT?

I know that SAT goes to 3-SAT and SAT is reducible to CNF-SAT and CNF-SAT is reducible to 3-CNF-SAT but is 3-SAT reducible to 3-CNF-SAT? They are not the same thing though right because cnf makes it ...
0
votes
0answers
40 views

Design a Turing Machine to compute the function

I'm tasked with designing a Turing Machine able to run in this Turing machine simulator With the function: f(x) = { x : x < 3 x + 3 : x ≥ 3 Where input: ...
1
vote
1answer
57 views

Is a Turing machine on an arbitrary (finite) alphabet equivalent to one on {0, 1}?

Brief context: I'm trying to understand why a Universal Turing Machine exists, on a tape with alphabet $\{0, 1\}$. I think I can see that a $3$-tape Turing machine can represent a Universal Turing ...
0
votes
1answer
23 views

State Change in a Turing Machine(Computer of Integer Function)

Im trying to learn how TM can be used as a computer of integer functions. I have this problem The text books gives the construction as follows I understand that intially the R/W head will be ...
0
votes
1answer
8 views

Moves in a Turing Machine

In a Turing Machine i understand that δ(q,x) is a transition function that results in a Change in ID. What does δ(q, Xj) =(P, y, L) mean.I understand that L stands for move left.Is P the new state ...
0
votes
1answer
17 views

Intersection of Turing Machines Languages

Given a Turing Machine A and a Turing Machine B, how can I know if the intersection of the Languages of both Turing Machines is non empty? L(A) $\cap$ L(B) $\neq$ 0
0
votes
1answer
77 views

Proof that a certain language is Turing Decidable

$$L_1 = \{\langle R,S \rangle \mid \text{$R$ and $S$ are regular expressions and }L(R) \subseteq L(S)\}$$ $$L_2 = \{\langle M\rangle\mid \text{$M$ is a DFA that accepts $w^r$ whenever it accepts $w$} ...
2
votes
1answer
224 views

Construct a deterministic Turing machine that decides the language $L=\{w\in\{a, b\}\mid w\text{ contains an occurrence of }ab\}$

So we are asked to construct a deterministic Turing machine. I have constructed a Turing machine, but I'm not sure if it's correct. Here is my Turing machine: For the question above, I'm just ...
0
votes
2answers
27 views

difference between A* and 2^A*

let A be any input alphabet then what is the difference between A* (kleen closure of A) and 2^A* ?
0
votes
1answer
39 views

Prove that the class of Turing Decidable Languages is strictly larger than class of Context Free Languages

Prove that the class of Turing decidable languages is strictly larger than the class of context free languages. (Give a language that is Turing decidable, but which violates the pumping lemma for ...
-1
votes
1answer
67 views

Draw a Turing machine that recognizes $\{w \in\{0,1\}^*\,|\,w\text{ contains even number of 1's}\}$

Draw a Turing machine that recognizes the language $\{w \in \{0,1\}^*|w \text{ contains even number of 1's}\}$ This is where I am at:
3
votes
1answer
44 views

Abstract machines that compute primitive recursive functions

What it the simplest (least powerful) abstract machine that can compute primitive recursive sets, i.e. sets whose characteristic or indicator function is primitive recursive? ...
0
votes
1answer
66 views

Language decidability and Post's theorem

I have the following exercise on decidability: Show that the language $L$ is decidable if and only if there exist decidable languages $A$ and $B$ such that $L=\{x\;|\;(\exists y)[\langle x, ...
1
vote
1answer
38 views

How is $ BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $

I'm not able to understand how $BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $ Can any body explain this to me in simple terms. Any help on this is highly appreciated.
0
votes
1answer
46 views

Design Turing Machine

Design a single-tape Turing machine with input alphabet {0, 1} to decide the language $$\{ x\in\{0,1\}^* \mid \#(0,x)=2\cdot\#(1,x)\}.$$ Could someone give me clarification on how to approach and ...
0
votes
1answer
22 views

Need help in understanding proof “approach” and meaning for “1st order Theory of dense linear orders w/o endpoints is PSPACE complete”

So in my class we are giving a proof for 1st order Theory of dense linear orders w/o endpoints is PSPACE complete. The proof that it is in PSPACE is basically to reduce TQBF. Let $\phi = \exists ...
1
vote
0answers
27 views

Are languages that contain the empty string Turing-Decidable?

Given a language that is Turing-Decidable, if you add the empty string to the language then is the new language Turing-Decidable? I am very confused at this problem because from my understanding the ...
0
votes
0answers
21 views

Is a Turing Machine which must check every single possible string ever a decider?

When classifying a language, I've constructed a Turing Machine to recognize it. However, to do so the machine must check every single possible input string from an alphabet. Since this is an infinite ...
0
votes
0answers
26 views

What class of probability distributions do probabilistic turing machines induce?

What class of probability distributions is induced by the class of probabilistic turing machines? Is there a precise characterization?
0
votes
0answers
18 views

Turing machine that accept L = {ww} in linearithmic time

I was wondering if there is a way to design a deterministic turing machine that accept the language L = {ww} with a time complexity of O(n log(n))
0
votes
1answer
24 views

Why is there, for every language L in NP, a Turing machine with polynomial memory that also accepts L?

So my question is the title, but I also have a question about something else. If you have a problem, how can you determine the reason that it is in NP. So for example: given a directed graph with $N$ ...
1
vote
0answers
30 views

Reducability and decidability language

i am new to this course called Theory of Computation. And my teacher asked to solve this ... i dont know how to do it... please help Consider the langauge L_inf : A turing machine M belongs to L_inf ...
0
votes
0answers
49 views

What is the maximum amount of steps a Turing machine needs to take before you know it won't accept the input?

So for example, we take a Turing machine $M$ with alphabet $\{0,1\}$ and 10 states, where $q_0$ is the initial state and $q_F$ is the accepting state. For a certain algorithm or calculation $M$ is ...
1
vote
0answers
138 views

Turing machine ( exponentiation )

How do I design Turing machine for exponential function $a^x$? I found this explanation http://philpapers.org/archive/LEMATM , but its too complicated. Could someone tell me please, is there another ...
0
votes
0answers
52 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
33 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
36 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
58 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
83 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
60 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 ...
2
votes
1answer
69 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
223 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
130 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
74 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
50 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
36 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
26 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
89 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
175 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
13 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
55 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
87 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 ...