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

-6
votes
0answers
68 views

Computation Challenging Problem [closed]

i ask one question, but someone put it on-hold. I ask it again. I see some strange definition in lecture note, every expert could help me in defining this notation in computation theory course? and ...
-5
votes
0answers
65 views

Computation Challenging Definition Problem [closed]

I see some strange definition in lecture note, every expert could help me in defining this notation in computation theory course? and why this sentence is true?? a) there is infinite number t, such ...
-1
votes
1answer
63 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
82 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
40 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.
-1
votes
1answer
60 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?
1
vote
0answers
47 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
61 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
11 views

how to decide if a language belongs to RE, or coRe?

I can't understand how to determine if a language is in RE or coRE or neither. Can someone give me an intuition about it? or maybe a thumb rule?
0
votes
0answers
19 views

Turing Reductions

Consider the language $L=\{<M>: \forall x$ s.t $\left|x\right|$ is even , $x\in L\left(M\right)$ How to show it's not in RE (meaning it's not Turing recognizable) using a mapping reduction from ...
-1
votes
1answer
47 views

NP vs CO vs P Problem

if we assume set of all tautology in predicate logic, with above assumption is : 1) NP Complete? 2) NP but not NP- Complete? 3) CO-NP Complete? 4? CO-NP but not CO-NP Complete? i ran into a ...
0
votes
0answers
66 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
39 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
63 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
44 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
32 views

L={(M,W) | M is a Turing Machine that stops on input W } is not R. E.

I've been thinking about how to show this but I'm stuck. on Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science (Computer Science and Scientific ...
0
votes
0answers
26 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
33 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
25 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
65 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
65 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
27 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
37 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
34 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
24 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
40 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
49 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
60 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
28 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
39 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
26 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
115 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
307 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
33 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
51 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
28 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
60 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
35 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
57 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
35 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
27 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
54 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 ...