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
3answers
28 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 ...
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!
0
votes
1answer
20 views

Single tape Turing Machine and a Single Push Down Stack

The alphabet for all of the following problems is the same: A, B, C, and null. But I can use an additional character D if I want for this problem. The initial tape is (A+B+C)* The initial stack is ...
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 ...
0
votes
1answer
31 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 ...
0
votes
1answer
98 views

Proving a language is Turing recognizable

Turing Machine M with a wait option has the option to make the machine's head wait where it is, until a case comes along where ...
-2
votes
1answer
45 views

Probability over decidable languages

Let $\mathcal S$ be the set of all languages over some finite alphabet $\Sigma$. Prove that the probability of a randomly chosen (arbitrary distribution) language has a decider is zero.
7
votes
0answers
159 views

What turmite runs the longest before becoming predictable?

When looking at 2D Turing machines, many of them eventually become predictable. For example, Langton's Ant, the champion 2-color 1-state turmite, develops a highway after 10,000 steps. Predictable ...
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 ...
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 ...
2
votes
0answers
27 views

Maths, esp. Godel, and poetry

At the risk of being an interloper: I'm a poet with a bit of mathematical training. Right now I've got a grant from the Arts Council of Northern Ireland to write a collection (loosely) based on the ...
2
votes
0answers
65 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$ | ...
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 ...
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 ...
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 ...
1
vote
0answers
58 views

Primitive recursive and Turing machines

Can someone give me a hint or the start of a possible proof for the following theorem: A function $f: \mathbb{N}^r \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a ...
1
vote
0answers
33 views

(2,5) Turing Machine implemented with chess pieces

I recently came across a (limited) reference to a (2,5) Turing machine implementation that can be represented using chess pieces on a 2D board. I know it is possible to implement a UTM using ...
1
vote
0answers
8 views

Is the language that consists of machine configurations whose language is a subset of even palindromes semi-decidable?

Let $PAL = \{ww^R\ | w\in\{0,1\}^*\}$. Then let $A = \{\langle M\rangle \ | \textit{M is a Turing Machine and } L(M)\subseteq PAL\}$ Is A semi-decidable (Turing recognizable or recursively ...
1
vote
0answers
54 views

Time constructible, non-time constructible functions

A function T:N→N is time constructible if T(n)≥n and there is a Turing Machine M that computes the function x↦└T(|x|)┘ in time T(n). (└T(|x|)┘ denotes the binary representation of the number ...
1
vote
0answers
74 views

A question about the analogy between formal systems and Turing machines

It is well known the analogy between formal systems and Turing machines. If I am not wrong, you can code any formal system of language L in first order logic into a Turing machine, and there is a ...
1
vote
0answers
39 views

Would adding a stack to a 2-stack Turing machine allow it to recognize more languages?

I don't think it should because a third stack would be superfluous. The machine could just reuse the first stack after it uses the second right? I'm just beginning to learn about Turing machines, so ...
0
votes
0answers
31 views

how do I make this post machine accept aab or baa?

so far I made it accept, a, aaa,bab but now I want strings aab or baa. How would I do this ? this is what I have so far... edit: @Hagen von Eitzen here is the example of Post Machine that a lot of ...
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
0answers
51 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
24 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
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
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 ...
0
votes
0answers
106 views

A turing machine for binary addition

How would I write a turing machine which has configurations which does 2 bit binary addition?
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 ...
0
votes
0answers
44 views

Overwriting a blank symbol is semi-decidable

Consider the following language: $$ L = \left\{ \langle M \rangle~ \middle| \begin{array}{c} M \text{ is a single-tape TM that writes a blank symbol $\sqcup$ over a nonblank} \\ \text{symbol during ...
0
votes
0answers
26 views

Is a sum of an elementary chain on low models low?

We have an elementary chain of low models $(\mathcal{A}_i)_{i\in\omega}$ such that for every $n\in\omega$ the model $\mathcal{A}_{i+1}$ is a model obtained by Low Basis Theorem from the set $A_i$ that ...
0
votes
0answers
34 views

Proving DIAG2 = $\{\langle M\rangle | \langle M\rangle\langle M\rangle\notin{L(M)}\}$ is not semi-decidable!

This is a homework problem so I don't expect a full solution. I just want a hint on how to do this problem. Just in case you are not familiar with the notation, $\langle{M}\rangle$, means a string ...
0
votes
0answers
70 views

Variation of 3SAT is in NP-Complete

Consider the problem of "K-3SAT", a variation of 3SAT: Given a 3CNF formula O and an integer k, the machine determines whether the formula O has a satisfying assignment in which at most k variables ...
0
votes
0answers
31 views

Time complexity of the described DTM

There is a DTM with alphabet $\Sigma = \{∗, 0, 1\}$, that on input $1^n$ outputs $1^n ∗ 1^n$. That is it takes a string of $n$ ones and replaces it by two strings of $n$ ones, separated by a blank ...
0
votes
0answers
88 views

Describing a multitape Turing Machine that enumerates the set of $i$ such that $w_i$ is accepted by $M_i$

I am having trouble with this problem. It regards the theory of Turing Machines. Describe a multitape Turing Machine that enumerates the set of $i$ such that the word $w_i$ is accepted by the ...
0
votes
0answers
247 views

Turing Machine question, this is NOT HW

I was having a hard time understanding and solving this question that wants me to show the final tape and figuring out if whether or not the turning machine accepts it or not. I have a list of 20 ...
0
votes
0answers
260 views

Equivalence of 2-dimensional Turing machine and a standard Turing machine

I'm asked to prove that a two-dimensional TM (one with 2-dim tape that has the upper-left end, and downwards and to the right it goes infinitely) is equivalent to a standard TM. Can I please get a ...