# Tagged Questions

25 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 ...
22 views

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 ...
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: ...
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?
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.
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?
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" ...
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 ...
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?
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)
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) ...
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 ...
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 ...
47 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 ...
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 ...
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 ...
61 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 ...
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^*$. ...
70 views

### How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
234 views

### A turing machine for binary addition

How would I write a turing machine which has configurations which does 2 bit binary addition?
75 views

### Solving the halting problem for *almost* all machines?

As I understand it, the proof of the halting problem’s undecidability is conceptually pretty simple. You postulate a machine $h(m, x)$ which (1) always halts and (2) returns 1 if $m$ halts with input ...
89 views

38 views

### Proving DIAG2 = $\{\langle M\rangle | \langle M\rangle\langle M\rangle\notin{L(M)}\}$ is not semi-decidable!

This is a homework problem so I don't expect a full solution. I just want a hint on how to do this problem. Just in case you are not familiar with the notation, $\langle{M}\rangle$, means a string ...
46 views

### Probability over decidable languages

Let $\mathcal S$ be the set of all languages over some finite alphabet $\Sigma$. Prove that the probability of a randomly chosen (arbitrary distribution) language has a decider is zero.
105 views

### Proof of undecidability of $FINITE_{\text{TM}}$ and $USELESS_{\text{TM}}$

I came across these 2 problems about proving of undecidability of languages: $1$. $FINITE_{\text{TM}} = \{\langle M \rangle | M \text{ is a Turing machine and } L(M) \text{ is a finite language} \}$. ...
110 views

### Why do complex grammars require powerful algorithms?

I am reading a fabulous book on Formal Languages and in the book it says: As the rewrite rules of a grammar become more complex, the algorithm for recognizing the associated language becomes ...
50 views

### Tally method to build a machine (on paper, Turing Machine

Consider function $q$: For any even integer $x\ge0$ (including $0$): $q(x) = 4x$ I want to design a machine (on paper of course) to compute q under the Tally system. Another restriction is that when ...
737 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 ...
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 ...
155 views

### Injection from computable numbers into natural numbers

Each Turing machine which writes an infinite sequence of 1 and 0 can be regarded as representing a (computable) real number (and of course each Turing machine represents a natural number by its ...
319 views

### Is this undecidable language recognizable?

Is this language: $L = \{\langle M\rangle : \text{$M$is a Turing machine and$L(M)$is decidable}\}$ which I know that is undecidable, turing-recognizable? Is its complement recognizable? ...
471 views

### Turing machine for balancing parentheses on a two letter alphabet

How to construct a Turing machine $M=(Q,\Gamma,b,\Sigma,\delta,q_0,F)$ which decides if a sting on the alphabet $\{(,)\}$ is ''balanced'' (e.g. $(()())$ is balanced and $))(($ or $()(($ is not) with ...
183 views

### Computability of busy-beaver sequence? [closed]

We can draw a parallel between cellular automata and busy-beaver numbers. For example the initial case occupies some kxk square in the plane,leaving all the other cells emty, after how many ...
139 views

### Are there known natural problems of intermediate degrees of unsolvability?

I know there exist intermediate degrees of unsolvability, i.e. there are undecidable problems which can be reduced to the Halting Problem, but not vice versa. Are there any "natural" problems known or ...
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 ...
149 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 ...
### Question about $\Sigma_n$-soundness
According to wikipedia (http://en.wikipedia.org/wiki/%CE%A9-consistent_theory#Definition): "$\Sigma_n$-soundness has the following computational interpretation: if the theory proves that a program C ...
### I do not understand why the Turing computable sets of N are exactly the sets at level $\Delta_1^0$ of the arithmetical hierarchy
The reason I don't understand it is this. Take for example the twin primes conjecture, which is $\Pi_2^0$. The set of twin primes is computable right? (there is a Turing machine that enumerates all of ...