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

10
votes
0answers
231 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 ...
5
votes
0answers
105 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 ...
5
votes
0answers
272 views

Designing a turing machine for primality check.

I am designing some turing machines, so far I have made Binary Addition and subtraction. Now I've been thinking that what if turing machine can check if the number is prime or not. Lets suppose we ...
5
votes
0answers
152 views

Show that minimal CFG is undecidable (Sipser 5.36)

Question: Say that a CFG (context-free grammar) is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{\text{CFG}}$ = $\{\, \langle G \rangle$ | $G$ is a ...
3
votes
0answers
85 views

How to find the shortest path of a graph in a turing machine

I'm reading about Turing machine and I saw some examples as: Let $M_{1}$ a Turing Machine and the language $B = \{w\#w \vert w \in \{0,1\}^{*}\}$, We want $M_{1}$ to accept if its input is a member of ...
3
votes
0answers
92 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 ...
3
votes
0answers
214 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
36 views

How are weakly universal Turing machines actually defined?

For what I know, the definition of a universal Turing machine is something along the lines of the following (of course, details might vary from source to source): A Turing machine $M$ is called ...
2
votes
0answers
43 views

Find Pi number using Turing Machine

What is the most convenient and fast way to find first $n$ binary digits of $\pi$ using Turing Machine?
2
votes
0answers
96 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on ...
2
votes
0answers
151 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
125 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
24 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 ...
1
vote
0answers
29 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 ...
1
vote
0answers
109 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 ...
1
vote
0answers
51 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 ?
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
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 ...
1
vote
0answers
98 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
1
vote
0answers
44 views

Dual Turing Machine Simulation

(1) Define a Turing Machine that simulates a Dual Turing Machine (DTM)?. A dual Turing Machine is defined as a Turing Machine with 2 heads and 2 tapes. At every step, the DTM can read from either ...
1
vote
0answers
33 views

BusyBeaver growth: “simple” proof

I just try to prove that $BB(n)$ (BusyBeaver-Function) grows faster than any other computable function. Maybe someone can check the proof? $f(n)$ is a computable function which grows to infinity: ...
1
vote
0answers
71 views

Proof that Finite Turing Machine is reducible to Regular Turing Machine

I know that Finite Turing Machine and Regular Turing Machine are undecidable through Rice's theorem, but I may find a reduction among them? Finite TM = {< M > | L(M) is finite on {a}} Regular TM ...
1
vote
0answers
65 views

Probabilistic Turing machines as random variables

A probabilistic Turing machine (PTM) is informally described as a non-deterministic Turing machine such that ''the next movement'' is chosen with a certain probability. Suppose that the input of a PTM ...
1
vote
0answers
94 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
0answers
77 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
118 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
107 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
52 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
21 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
75 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
101 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
432 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 ...
1
vote
0answers
47 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
27 views

all recursive functions are turing computable

I'm studying with the book computability and logic(boolos). In chapter 5, the theorem is proved, indirectly, by showing that (recursive => abacus) & (abacus=> turing). But I want to prove ...
0
votes
0answers
28 views

Designing a Turing machine for Binary Division

I'm trying to design a TM to binary divide 2 numbers. The best approach I've found is the method: division as repeated subtraction, but I don't know if there's a fastest way or an easier way. ...
0
votes
0answers
20 views

How to compute the solution for this linearized diffusion-reaction system (separation of variables)?

Let $\Omega=(0,a), a>0$ and functions $u(x,t), v(x,t)\in\mathbb{R}$. Consider the diffusion-reaction system $$ \partial_tu=\Delta u+\gamma f(u,v)\text{ for }x\in\Omega,t>0\\\partial_t v=d\Delta ...
0
votes
0answers
35 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 ?
0
votes
0answers
25 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
19 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: ...
0
votes
0answers
31 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
0answers
15 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
16 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
0answers
18 views

Ph has log complete set

how can I show that PH has a ≤log m -complete set if and only if it collapses I am CS major and I do not have much Idea on how to do mathematical proofs
0
votes
0answers
41 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 ...
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 ...
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. ...
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 ...
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 ...
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 ...