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
1answer
16 views

how to a draw a turing machine that has the same number of a's ,b's and c's

how to a draw a turing machine that has the same number of a's ,b's and c's SOMELANGUAGE = {abc acb bac bca cab cba aabbcc aabcbc}
1
vote
3answers
27 views

Reducing a Decidability Problem to the Halting Problem

Let $L = \{(M, n): M$ halts on less than $n$ elements from a set S $\}$ I'm trying to come up with a generalization on how to solve these types of problems so I have not defined what S is. Since the ...
6
votes
0answers
33 views

An Undecidable but not Universal Turing Machine?

I have seen many examples of universal Turing machines, all of which are undecidable due to the undecidability of the halting problem. I have also seen proofs that certain really small Turing ...
0
votes
0answers
9 views

Proof of theorem about connection between nondeterministic and deterministic Turing machines complexity classes

I need source for proof of this theorem: Every $T(n)$ time nondeterministic Turing machine has an equivalent $2^{O(T(n))}$ deterministic Turing machine. I have book by Michel Sipser, ...
0
votes
1answer
27 views

Prove language is in $NP$ without using a reduction

I've been stuck on this question for hours, can't seem to figure this out. $L = \{\langle M, x, y \rangle\ |\ M$ is a non-deterministic Turing machine over $\{0,1\}$ and $x,y \in \{0,1\}^*$ and ...
0
votes
0answers
44 views

UPPER bounds of the busy beaver function?

I learned that the busy beaver function grows very rapidely indeed. The first 4 values are known. I would like to know if there is any UPPER bound known for $$\Sigma(n)$$ for some $n\ge 5$. ...
0
votes
0answers
21 views

A Turing machine that can read and determine if another turing machine is valid

Hey I have to write a turing program that will read in another turing program and determine if it is a valid turing program. The program to be read in would have each of its states represented by IO, ...
0
votes
1answer
11 views

path of non-deterministic and deterministic turing machines

So let's say that we have state 1 2 and 3. In both the non-deterministic and the deterministic turing machine, we only have one-way transitions between the state 1, 2 and 3. For example, if we can go ...
2
votes
1answer
20 views

What's the difference between a non-deterministic turing machine and a deterministic turing machine?

From what I understood, it seems that the difference is that a NTM can have 2 inputs for which there is a different output or direction. For example, state A for input 1 can result in output 0 and ...
0
votes
0answers
9 views

Do all turing machine have to reach the blank state to end up in an accepting state?

Like the turing machine above has to produce the same amount of as there are bs, otherwise it will get stuck in state 1, so why do they rewind with (B,B,R) to go to state 3 and then state 4?
0
votes
1answer
30 views

Turing Machine example question 0^2n followed by 1^n

I have a doubt regarding the turing machine example. L = {w | w contains exactly twice as many 0's as 1's} How will the turing machine solve this , how many states are considered and what is the ...
1
vote
2answers
84 views

Milton Green's lower bounds of the busy beaver function

Wikipedia states that Milton Green demonstrated in 1964, that the busy beaver function $\Sigma(n)$ has the lower bound $$\Sigma(2k)>3\uparrow^{k-2}3$$ I read the talk about the busy beaver ...
1
vote
1answer
57 views

Build a deterministic turing machine to decide L = { ww }

As the title says. w is in {a, b}^*.Note that I am not looking for the non-deterministic one. Use a Turing machine of one tape and "pointer". An idea: I thought that I would do something like ...
1
vote
1answer
21 views

Recursively Enumerable Languages and Turing Machines

L1 = { M | Turing Machine M terminates for at least 637 inputs} L2 = { M | Turing Machine M terminates for at most 636 inputs} One of them is recursively enumerable, which one?
1
vote
1answer
28 views

Showing a Problem Is Undecidable

How can I show that T is undecidable using only this information? $$T = \{\langle M, w, r\rangle \mid M \text{ accepts } w^r \text{ when it accepts } w.\}$$ So, what it's saying is that the machine ...
0
votes
1answer
31 views

Accepting/rejecting states in Turing Machine

In language decidability problems, a TM halts with a halting state, an accepting state or a rejecting state. My understanding is that when a TM machines halts on accepting state, it removes everything ...
0
votes
0answers
24 views

A turing machine which computes the same language as a “stay put” turing machine

Im not sure I really understand how stay put machines work. I know they are just like turing machines but with states. So they can "stay put". But what confuses me is when you define a FSA for a ...
1
vote
2answers
47 views

Decidability of Recursively Enumerable Languages

I'm having trouble with this problem, I know that every decidable language is recursively enumerable but that not every recursively enumerable language is decidable. What are the steps involved in ...
0
votes
1answer
28 views

Turing Machines and Decidability

I saw this question in a textbook on decidable languages, and I was wondering how you would go about solving this type of question: Assume L1 and L2 are decidable languages. Which of the following ...
1
vote
1answer
44 views

Show that the Turing machine will solve the self-halting problem

Suppose we have Turing machine $M^*$ that: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Show that you cannot construct $M^*$. ...
1
vote
1answer
31 views

Proof that such a Turing machine cannot be constructed…

Prove there can be no Turing machine $M^*$ that takes input $n$ and: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Intuitively I can see why ...
1
vote
1answer
22 views

What is the Church-Turing thesis?

Every source I look at online says something vague about Church's notion being equivalent to Turing's, but what exactly is the Church-Turing thesis? As I understand, it attempts to precisely define ...
1
vote
1answer
36 views

Prove $L$ = $\{\langle M \rangle$ | $M$ is a TM over $\{0,1\}$ and $\langle M \rangle \langle M \rangle \notin \mathcal{L}(M)\}$ is undecidable.

Was stuck on this for a bit so I need to know if I am on the right track. To show that $L$ is undecidable we will show that $\overline{L}$ is undecidable instead. Suppose $\overline{L}$ is decidable ...
1
vote
3answers
63 views

How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
2
votes
1answer
47 views

Are all constrtuctively describable functions continuous? Do they necessarily come with a topology?

In the paper "An injection from $\mathbb{N}^\mathbb{N}$ to $\mathbb{N}$" by @AndrejBauer, about the question whether there exists an injection $\mathbb{N}^\mathbb{N}\to\mathbb{N}$, we writes ...
2
votes
0answers
64 views

Prove that $\overline{L}$ is not recognizable by showing that $B_{TM} \le_m L$

$\textbf{Problem}:$ $L$ = $\{\langle M \rangle$ | $M$ is a Turing machine over $\{0, 1\}$ such that for some $x \in \{0,1\}^*$, $M$ does not halt on input $x\}$. $B_{TM}$ = $\{ \langle M \rangle$ | ...
0
votes
2answers
52 views

Turing machine true/false questions

There is a non-regular language that is recognized by a Turing Machine. I believe the answer to this is true, because Turing machines can "count" computations and ...
1
vote
1answer
56 views

Let $L_{UIUC}$ = $\{ \langle M \rangle$ : $L(M)$ contains the string $UIUC\}$. Prove that $L_{UIUC}$ is undecidable.

Been stumped as to why the following proof works. Note: I have taken this proof directly from here. Proof by reduction from $A_{TM}$. Suppose that $L_{UIUC}$ were decidable and let $R$ be a Turing ...
0
votes
1answer
38 views

What does it mean for a Turing machine $M$ to accept $\epsilon$

Suppose $B_{TM}$ = $\{ \langle M \rangle$ | $M$ is a Turing machine over $\{0, 1\}$ and $M$ accepts $\epsilon\}$. I do not understand what it means for $M$ to accept $\epsilon$. Can someone explain ...
3
votes
0answers
90 views

Proving a language is not recognizable

I have the following question that I just want to verify I have done correctly. Let $L$, $L_1$, $L_2$ $\subseteq \Sigma^*$ such that $L = L_1 \cup L_2$, and $L_2$ is decidable. Prove that if $L$ is ...
0
votes
0answers
103 views

A turing machine for binary addition

How would I write a turing machine which has configurations which does 2 bit binary addition?
1
vote
2answers
59 views

The halting problem for tapes that are or are not completely blank

Is it possible to construct a Turing machine that halts only if the tape is not completely blank? Also, is it possible to construct one to halt if the tape is completely blank? Intuitively, I think ...
2
votes
1answer
57 views

Designing a turing machine

Suppose you have a tape that has a block of $a$ strokes followed by a space, followed by a block of $b$ strokes, followed by a space, followed by a block of $c$ strokes, and otherwise blank. ...
1
vote
1answer
67 views

If $L_1 \cap L_2$ is decidable, prove/disprove that $L_1$ and/or $L_2$ are decidable

Question: Let $L_1$ and $L_2$ be languages over the alphabet $\Sigma$. If $L_1 \cap L_2$ is decidable, then $L_1$ is decidable or $L_2$ is decidable (or they both are). Definition of a decidable ...
1
vote
1answer
21 views

Interpreting probabilistic time turning machines

I was trying to understand better the definition of a strong PSRG and I came across this expression which I am trying to understand better: $$ Pr_{r \in \{0,1\}^l}[A(r) = "yes"]$$ Where r is a truly ...
1
vote
1answer
106 views

Number of possible configurations in a Turing Machine

While studying for an up-and-coming exam, I stumbled upon the following question: $$ L=\{\langle M \rangle,\langle w\rangle:M\text{ is single-tape and }M \text{ running on }w \text{ doesn't go over ...
1
vote
1answer
30 views

Languages in P that are not P-complete

Why aren't there any languages in P that are not P-complete?
2
votes
1answer
51 views

Prove that RE is closed under reduction

Prove that the class RE is closed under reduction. Definitions: A language $ A \subseteq \Sigma^*$ is called reducible to $ B \subseteq \Gamma^*$ ( denoted by $A \leq B$) if there is a computable ...
1
vote
1answer
36 views

Languages that are not comparable in $R$

I want to know if there are $2$ languages $A,B\in{R}$ such that there's no reduction between them. Namely, $2$ languages $A$ and $B$ $\in$ $R$ such that $A\not\le B$ and $B\not\le A$ Thanks a lot!
1
vote
1answer
120 views

prove Turing recognizable

This is actually an old exam question its not my homework; Let L = { : M is a TM with an input alphabet of {a,b} and M accepts at most one word, i.e. M either accepts no words or accepts exactly one ...
1
vote
0answers
42 views

Extended PDA vs TM

We studied in class that PDA is less powerful than TM. My question is: Extended PDA : for every $\alpha,\beta \in \Gamma \cup \{\epsilon\}$, $\sigma \in \Sigma \cup \{\epsilon\}$, $q,r \in Q$, $w ...
0
votes
0answers
18 views

reverse of language, decidability

Consider a language L(D) = {w: w and its reverse are in L(D)}. Does reverse of L(D) is the same language ? If so, then consider L = {: M is a DFA for L(D)}, does this make this a turing decidable ...
2
votes
1answer
41 views

Given a single taped deterministic turing machine what's the least amount of calculations needed in order to receive the language

Given a single taped deterministic turing machine what's the least amount of calculations needed in order to receive the language $L_k=${$0,1$}$^*0${$0,1$}$^{k-1}$. My intuition says that i'll need ...
1
vote
1answer
64 views

Solving the halting problem for *almost* all machines?

As I understand it, the proof of the halting problem’s undecidability is conceptually pretty simple. You postulate a machine $h(m, x)$ which (1) always halts and (2) returns 1 if $m$ halts with input ...
2
votes
1answer
41 views

Concrete universal turing machine

I read about universal turing machines in the internet, but I did not find a concrete listing of a universal turing machine and a descreption, how a specific turing machine has to be coded that the ...
1
vote
0answers
78 views

Oracle Turing machine - $E_{\text{TM}}$ and $PCP$.

$$E_{\text{TM}}=\{\langle M\rangle|M\text{ is a TM and $L(M)=\emptyset$}\}.$$ $E_{\text{TM}}$ is undecidable $$PCP=\{\langle P\rangle|P\text{ is an instance of the Post Correspondence Problem with a ...
2
votes
1answer
32 views

Reducing A$_\text{TM}$ to REGULAR$_\text{TM}$

We can solve A$_\text{TM}$ problem using REGULAR$_\text{TM}$. Assume $R$ is a Turing machine that decides REGULAR$_\text{TM}$. We construct $S$ to decide A$_\text{TM}$ as follows On input ...
0
votes
1answer
38 views

Assign Integer to Each Turing Machine

I have the following problem: suppose that we have an infinite set of symbols, $A = \{a_1, a_2, ...\}$ from which all Turing Machine input alphabets are chosen. Show how we could assign an integer to ...
2
votes
0answers
50 views

Blanks in the Tape of a Turing Machine

I used to have a lot of trouble with Turing Machines, primarily because I thought that in-between input symbols on the tape, one could have an arbitrary number of blanks, so every input would need to ...
2
votes
1answer
81 views

Turing Machine for comparing, copying, and operating

If one wants to design a Turing Machine for a function such as this: Where $x>0,y>0$ and are both integers represented in unary, so an example movement in this TM on the read-write head would ...