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
1answer
39 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

$ E_{\text{TM}} = \{ \langle M \rangle \mid L(M) = \varnothing \} $ is undecidable.

In this proof, we need to convert the input from $ \langle M,w \rangle $ to $ M_{1} $ as $ E_{\text{TM}} $’s input is only a Turing Machine. However, I couldn’t understand the construction of $ M_{1} ...
10
votes
0answers
196 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 ...
4
votes
0answers
89 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 ...
3
votes
0answers
52 views

Do there exist a pair of 'orthogonal' non-halting Turing machines?

I'll explain what I mean by orthogonal, which is probably a poor choice of words on my part. Given two Turing machines $\lambda $ and $\tau$,and two inputs $i$ and $j$. lets say $\tau(i) \preceq ...
3
votes
0answers
66 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
108 views

Whats the connection between Turing machine and First order logic?

Today in my Computing class i came across the theorem which states that., If language $L$ and $\Sigma^*\setminus L$ are recursively enumerable then L is recursive (total turing machine). Which looks ...
3
votes
0answers
165 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
35 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
59 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 ...
2
votes
0answers
86 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
66 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
113 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
78 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
49 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
29 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
32 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
53 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
48 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
91 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
50 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
98 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
83 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
50 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
16 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
67 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
83 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
349 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
42 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
24 views

Show the following languages are not recursive

Show that the language $$L = \{ M : M \text{ is a Turing Machine that halts on input $M$ } \} $$ is not recursive. Show that the language $$ L = \{M : M \text{ is a Turing Machine such that $L(M)$ ...
0
votes
0answers
26 views

Problem with tracing computation from Turing Machine

Transition Function of TM M start_state: q final_state: qf R denotes move right L denotes move left S denotes stop I traced the computation but not sure if it is exactly correct my problem is ...
0
votes
0answers
19 views

Non-deterministic multiplication algorithms

Are there any algorithms for non-deterministic Turing machines that can compute the decision problem $mn=x$ (where $m=O(n),x=O(n^2)$) faster than the equivalent deterministic algorithm? Equivalently, ...
0
votes
0answers
31 views

Showing that Turing-recognizable languages are closed under union

I'm reading "Theory of Computation" by Michael Sipser and I've encountered a solution (provided by the book) that I don't understand. The question: Show that the collection of Turing-recognizable ...
0
votes
0answers
18 views

Design a Two-Tape Turing Machine which generate Palindrome

For e.g I have a String on a tape, $Blank|1|0|1|0|Blank$. Now I have to Use two tape and Reverse this string into second tape. First tape =$Blank|1|0|1|0|Blank$. ...
0
votes
0answers
31 views

Turing machine notation question.

I'm a bit confused on some of the notation being used for turing machines in one of our exercises in class. The question gives us a string α ϵ {0,1}* and the function int(α) that changes a binary ...
0
votes
0answers
16 views

program which it's power is equal to LBA

Can anyone give an opinion about this matter: what is the smallest program which it's power is equal to LBA Turing machine(Linear bounded automata are acceptors for the class of context-sensitive ...
0
votes
0answers
34 views

Turing's Corrections on his 1936 paper On computable Numbers

On Turing's proof of the "Lemma 1" (If $\ S_{1}\,$ appears on the tape in some complete configuration of$\ M\,$,then$\ Un(M)\,$is provable) He states that we are unable to deduce$\ F^{n+1} \to ...
0
votes
0answers
23 views

is it in fact impossible to construct a machine which can know if a macine ever prints a character?

In $\S\ 8$ of his paper "On computable numbers, with an application to the Entscheidungsproblem" Turing uses his proof that $\mathfrak{D}$ (a machine which given the S.D. of another machine ...
0
votes
0answers
82 views

could a machine $\mathfrak{D^+}$ be made to produce $\beta$ so the diagonal argument could be used on computable numbers?

I was reading Turing's paper "On computable numbers, with an application to the Entscheidungsproblem" and while reading $\S\ 8$ (his proof that computable numbers are enumerable) and his proof that ...
0
votes
0answers
25 views

Designing a turing Machine belonging to a language

Im trying to learn the concept of turing machines.I have understood the basic stuff like its a simple mathematical model of a computer and its parts.Now im asked to create a turing machine. ...
0
votes
0answers
23 views

Show that L4 is decidable (i.e., recursive), by describing a Turing machine that decides L4.

L4 = {<M, w> | M is a turing machine, w is a string, and M never moves it's head left on input w} I know that M is allowed to move to the head to the left ...
0
votes
0answers
21 views

If we create a partition of $E_{TM}$ by listing its elements, are the subsets undecidable?

Consider the set $E_{TM} = \{ <M>$ | M is a TM such that $L(M) = \emptyset\}$ The set of all Turing Machines in countable. Thus $E_{TM}$ is countable. Suppose we list all elements of $E_{TM}$ ...
0
votes
0answers
16 views

Showing that $f(K) = {f(a) : a ∈ K}$ is recursively enumerable

Today we went over things that are recursively enumerable, but I cant seem to grasp how to prove the equation $$f(K) = {f(a) : a ∈ K} $$ is recursively enumerable. I can prove that equations are ...
0
votes
0answers
16 views

Can this language be solved in PTIME?

I would like to know why we cannot prove that $P \subsetneq PSPACE$ by considering the following language for some particular Turing Machine $M$: $L_M:=$ {$w : M$ accepts or rejects $w$ without using ...
0
votes
0answers
83 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
0
votes
0answers
49 views

Recursive Set and Complement Problem

if we have $$A=\{x:|W_x\ne\phi\}$$ can we say always my tight listed below is true? $A$ is recursive , $A$ is r.e, complement of $A$ is r.e, complement of $A$ is not recursive?
0
votes
0answers
33 views

Proof that whether some arbitrary Turing machine on some input outputs $5$ is undecidable

Consider the language $L = \{<M, w> \mid w \, \text{run on } M \, \text{evaluates to} \, 5\}$, ie the problem of deciding whether, for a TM $M$ and input $w$, if you run $w$ on $M$ then $M$ will ...
0
votes
0answers
59 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
50 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
100 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 ...