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
0answers
13 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
1answer
29 views

PDA and Some language Grammar inference

L1={$w^* $| w=x and $ x \in \Sigma^*$} L2={$ww^R ww^R $| $ w \in ( \Sigma + \Sigma)^*$} L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x} a) there is a PDA(push down automata) that accept ...
2
votes
0answers
22 views

Pushdown Automata and Challenge in Grammar

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
2
votes
1answer
36 views

A CFG Grammar for One Language

Suppose : $w_1,w_2 \in \{a,b\}^∗$ and $ L=\{w_1w_2 \mid w_1,w_2 \in \{a,b\}^* \land n_a(w_1)=n_b(w_2)\}$ $n_a$ is number of $a$'s and $n_b$ is number of $b$'s. This is a Entrance Exam question. I ...
2
votes
0answers
22 views

Strange Turing Machine Definition [closed]

i prepare for Autotmata Course Final Exam. in one of lecture, our professor draw this Turing Machine, and wrote DELTA is Neutral element of TM. it'w wrote: Language of this TM is: {$W \in ...
0
votes
0answers
10 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 ...
2
votes
1answer
58 views

Challenge on Property of Complement in Language

We have: and M be a finite automata. Suppose d(M) be a deterministic automata that equivalence to M. if $M_1$ and $M_2$ be two finite automata, $M_1 + M_2$ is the finite automata such that the ...
9
votes
2answers
169 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
0
votes
1answer
17 views

Deciding TM which fails to halt whenever the length of its input string is a prime number

I have the following Statement: "A TM called $A$ which fails to halt (i.e runs forever) whenever the length of its input string is a prime number, and eventually halts for all other input strings" ...
0
votes
1answer
25 views

Computable Function and Predicate Question

I See on Our Lecture note on Theory of Computation Course that: .... The basic characteristic of a computable function is that there must be a finite procedure (an algorithm) telling how to compute ...
1
vote
1answer
72 views

$NP^{PP} vs. PP^{NP}$, which one subsumes the other?

I understand why P with an NP oracle ($P^{NP}$) subsumes $NP$: because it contains co-NP. But how about NP with a P oracle? Can it be any different from NP? (I'm guessing they are the same otherwise ...
2
votes
1answer
77 views

Many to one Reducible & Polynomial time

we know that If $A \le_p B$, then $A$ can be reduced to $B$ in polynomial time. we know that If $A \le_m B$, then $A$ is many to one reduction to $B$ . can we deduce that: if $A \le_m B$ then $A ...
-1
votes
1answer
60 views

Recursively enumerable language [closed]

In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable or Turing-acceptable) if it is a recursively ...
0
votes
1answer
70 views

$\{x: 2x ∈ M\}$ is R.E Set [closed]

In computability theory, traditionally called recursion theory, a set $S$ of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if: ...
2
votes
1answer
87 views

Is it decidable: is there an input for which turing machine will move its head left?

$L=\{\langle M \rangle | M $is a Turing machine and $\exists$ input $x$ such that in $M(x)$ running $M$ moves its head left at least once $\}$ Is $L$ decidable?
0
votes
1answer
52 views

Logic & Computability Problem

i read this sentence in one exam that be false. anyone could say why? if predicate H(x) become false when a program with code r(x) halt on input l(x), then H be a computable predicate.
0
votes
1answer
88 views

Turing & Computability & Computation

We know if we have: we can show (T=t= Turin Redu.) but i have no idea why this relation be correct? any idea?
2
votes
0answers
50 views

Big Challenge in TM & R.E Set [closed]

we know that Halting problem {(M.w) | M halts on input w} is r.e but not recursive. i see the following sentence in one book. "the set of {(M.w) | M halts on input w and M is a TM}} is not r.e" ...
0
votes
0answers
63 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
71 views

Primitive Recursive Predicate Challenge

I'm an Computer scientist, and I recently ran into a challenge. If we have primitive recursive predicate $P(x), Q(x)$, I think that all of following 4 expressions can be primitive recursive. Any hint ...
0
votes
0answers
46 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
1answer
73 views

Recursive Set Challenge

we knoe also we know for example if A be any arbitrary r.e set. can we always Necessarily the following is TRUE ? (always) any description is good. (bar sign means complement)
0
votes
1answer
49 views

Complexity & Computation & Logic Problem [closed]

As i study for prepare to CS Final exam, i have some challenges. can i say all of following statements are true? 1) each infinite recursive set, is union of two disjoint infinite recursive set? 2) ...
0
votes
0answers
29 views

Turing Machine for $L$={$a^nb^m: m=n^2, n \geq 1$}

The problem only requires a description of the machine. I was thinking for each a you need to find 1 + 2k b's where k is the a your on. (ie for the for the first a find 1 bs, the second find 3 bs, ...
0
votes
1answer
36 views

Multi-Tape Turing Machines to find palindrome

Given an Alphabet {a,b,c} , produce a Turing Machine which recognize if a given input string X is a palindrome. means if X is a palindrome, TM is halting and accepting, else halting and rejecting. ...
0
votes
0answers
29 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 ...
1
vote
1answer
66 views

Turing machine for the language a^nb ^2nc^3n

How can we give a Turing Machines that accept following language. $$a^nb^{2n}c^{3n}$$ I am allowed to use also pseudo-code descriptions (i.e. high level descriptions of movements of r/w head):
3
votes
1answer
66 views

A constructive algorithm for a jump of a low set.

Suppose we have an oracle Turing machine which, with $K$ (the halting problem) as an oracle, computes a low set $A$. ($A$ is low if $A'\equiv_T K$) Is there an algorithmic way of obtaining a Turing ...
3
votes
2answers
28 views

Turing Machine Decidability

I have been working on this problem for few hours, but haven't been able to come up with a solution : Is the following problem decidable? Given a TM M, whether there is a w such that M enters each of ...
0
votes
1answer
39 views

turing machine accept and reject state

I am pretty new to Turing Machines and I am trying to understand the basic things first...so my question is , would this machine accept all words ending in 'a' ? if ...
1
vote
0answers
37 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
1answer
29 views

having hard time reading symbols in this Turing Machine

I am reading few books and I am looking at different examples of a Turing Machine, and I am getting frustrated reading symbols especially in this example...What does ...
2
votes
0answers
43 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 ...
0
votes
0answers
50 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
1answer
17 views

not understanding the part of the answer for drawn turing machine

Could someone please tell me what does capital B mean here ? of course I know R and L stands for right and left... and also I know for example if we have a,b,R (which tells you if you have an a , ...
0
votes
1answer
51 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
63 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
46 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
46 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
11 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
29 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
64 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
41 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
12 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
29 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 ...
1
vote
2answers
121 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
314 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
32 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
35 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
53 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 ...