1
vote
0answers
15 views

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable. (This is the same as the problem of detecting unreachable code in a program.)
3
votes
1answer
19 views

$L=${$a^nb^nc^n : n \geq 0 $} CFG Recognizing

Suppose $L=${$a^nb^nc^n : n \geq 0 $} and I. $h(L), h(a)=a, h(b)=bb, h(c)=b$ II. $L^R$ III. $L^*$ IV. $h(L), h(a)=a, h(b)=bb, h(c)=a$ Why just I is a CFG and other is not? anyone can help me to ...
1
vote
1answer
32 views

Language of a grammar vs regular expression vs nfa

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
1
vote
0answers
30 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 ...
2
votes
1answer
31 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
0answers
24 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
13 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 ...
9
votes
2answers
175 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
27 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 ...
2
votes
1answer
81 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 ...
0
votes
1answer
89 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
52 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
72 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
52 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

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
1answer
43 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
1answer
35 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 ...
0
votes
0answers
51 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
65 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
1answer
36 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 ...
1
vote
1answer
59 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
37 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 ...
2
votes
1answer
50 views

Are all constrtuctively describable functions continuous? Do they necessarily come with a topology?

In the paper "An injection from $\mathbb{N}^\mathbb{N}$ to $\mathbb{N}$" by @AndrejBauer, about the question whether there exists an injection $\mathbb{N}^\mathbb{N}\to\mathbb{N}$, we writes ...
1
vote
1answer
67 views

Let $L_{UIUC}$ = $\{ \langle M \rangle$ : $L(M)$ contains the string $UIUC\}$. Prove that $L_{UIUC}$ is undecidable.

Been stumped as to why the following proof works. Note: I have taken this proof directly from here. Proof by reduction from $A_{TM}$. Suppose that $L_{UIUC}$ were decidable and let $R$ be a Turing ...
2
votes
1answer
79 views

Designing a turing machine

Suppose you have a tape that has a block of $a$ strokes followed by a space, followed by a block of $b$ strokes, followed by a space, followed by a block of $c$ strokes, and otherwise blank. ...
1
vote
1answer
24 views

Interpreting probabilistic time turning machines

I was trying to understand better the definition of a strong PSRG and I came across this expression which I am trying to understand better: $$ Pr_{r \in \{0,1\}^l}[A(r) = "yes"]$$ Where r is a truly ...
1
vote
1answer
36 views

Languages in P that are not P-complete

Why aren't there any languages in P that are not P-complete?
2
votes
1answer
95 views

Turing Machine for comparing, copying, and operating

If one wants to design a Turing Machine for a function such as this: Where $x>0,y>0$ and are both integers represented in unary, so an example movement in this TM on the read-write head would ...
0
votes
1answer
81 views

Recursively enumerable language of Turing machines

If you have the language $L_{h}=\{M_{i} | (\exists z \in \sum ^{*}) M_{i}\text{ halts on some input } z\}$ where $M_{i}$ are Turing machines, is $L_{h}$ recursively enumerable? I'm fairly certain ...
0
votes
1answer
52 views

problem understanding a solution of Talbot's book (complexity and cryptography)

There's a question which is answered at the end of the book, but I have problem understanding the answer, my own understanding is that its lower bound would be $n^2$ as well. A palindrome is a a ...
3
votes
1answer
52 views

the time required to decide $L$

Suppose that a language $L$ is decided in space $S(n)$ by a DTM with alphabet  $\Sigma$ and set of states $\Gamma$. What upper bound can you give for the time required to decide $L$?
26
votes
4answers
751 views

Why do we believe the Church-Turing Thesis?

The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to ...
1
vote
2answers
182 views

Decidability and undecidability of a set or language

I want to find out whether the following sets are decidable or not. Generally speaking, what exactly should be done about it? Doing some research, I think a language or set is decidable if a Turing ...
1
vote
1answer
76 views

Decidability Turing Machine Problem

$L=\{G|G$ is a context free grammar over ${a,b}$ and $L\{G\}$ contains at least one string $w$ such that the number of $a$'s in $w$ is a multiple of $5\}$ Show that L is decidable by ...
3
votes
1answer
115 views

Explain why if the language A is recursive, then A is reducible to 0*1*

I'm in a theory of computation class and there is a problem that I think I am way overthinking. Can anyone point me in the right direction with the following: Give a short justification of the fact ...
1
vote
1answer
150 views

The set of Turing machines that recognize $\{00, 01\}$ is undecidable

$L =\big\{\langle T\rangle \mid T\text{ is a Turing machine that recognizes }\{00, 01\}\big\}$. Prove $L$ is undecidable. I am really having difficulties even understanding the reduction to use ...
1
vote
1answer
73 views

Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages Under Shrink

So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\mathrm{shrink}_a(L) = \{x \mid x=\mathrm{shrink}_a(w), w\in L\}$ and ...