# Tagged Questions

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

1answer
36 views

### Complement of halting set is not r.e.

suppose we don't know that Halting problem is not recursive. I want to prove that complement of halting set is not r.e. then we can find halting problem is not recursive. Can you direct prove that ...
2answers
97 views
+200

### 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 ...
1answer
39 views

### Rice's theorem_Theory of computation

Is there any body tell me, where is wrong in this proof Problem: The set of number of turing machine that has 5 state is decidable or not? Answer: The set is obviously 'Set of partial computable ...
0answers
27 views

### Describing a multitape Turing Machine that enumerates the set of $i$ such that $w_i$ is accepted by $M_i$

I am having trouble with this problem. It regards the theory of Turing Machines. Describe a multitape Turing Machine that enumerates the set of $i$ such that the word $w_i$ is accepted by the ...
0answers
36 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 ...
1answer
123 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 ...
0answers
55 views

### Understanding this specific turing machine, NOT HOMEWORK

In regards to the turing machine below, what is it's language? What is the final string if the input is 0011 and in general. what kind of 4 symbol strings does the turing machine accept? I am trying ...
0answers
68 views

### Turing Machines!!! Please check! [closed]

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 ...
0answers
31 views

### Turing machine question [duplicate]

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 ...
0answers
127 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 ...
0answers
16 views

### Automata. Concatenation of Turing Machine

Given TMs T1 = (Q1,S1, R1, q1, δ1) and T2 = (Q2,S2, R2, q2, δ2), with R1 ⊆ S2, give a precise definition of the TM T1T2 = (Q,S,R, q0, δ). Say precisely what Q, S,R , q0, and δ are.
1answer
57 views

### Showing this language is not decidable by rice theorem or reduction

Consider this language: L = {<M1,M2> : M1 and M2 are TMs and L(M1) contained in L(M2) contained in {1}*} Intuition says that it's undecidable, though can ...
1answer
65 views

### Decidability/Undecidability Question

Could someone please help me with this question? I'm really having a hard time understanding reductions and decidability. Prove that the language L = \{\langle M,N \rangle \mid M,N\text{ are Turing ...
1answer
78 views

### Decidability of a Turing machine always halting in at most ten steps

I've exam comping up soon and I need help with this. Consider the problem: Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input. Is this decidable? Prove your ...
0answers
124 views

### Turing Machine that accepts the language { www : w ∈ {a, b}*} [closed]

Turing Machine that accepts the language { www : w ∈ {a, b}*} I'm trying to solve this but I'm not sure how to start! I understand how to solve it if it only has ...
1answer
25 views

### Writing multiple symbols on a Turing Machine

Just a quick question: is it possible to write multiple symbols in succession onto a tape of a Turing Machine at once? For example, I'm trying to make a Turing machine that will accept the language ...
1answer
170 views

### Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3.

I have exam coming up and I need help with this: Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3 Thank you :)
1answer
41 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 ...
1answer
35 views

### Decidablility Turing machine

Is it decidable whether a Turing machine takes more than 481 steps for some input? This was asked in one of the exams. I found some solutions but are not clear to me.
2answers
108 views

### Why is propositional logic not Turing complete?

According to 1 (probably not the most relevant source), propositional logic is not Turing complete. Aren't all computations in computers performed using logic gates, which can be represented as ...
4answers
74 views

### Non-Deterministic Turing Machine Algorithm

I'm having trouble with this question: Write a simple program/algorithm for a nondeterministic Turing machine that accepts the language:  L = \left\{\left. xw w^R y \right| x,y,w \in \{a,b\}^+, ...
1answer
145 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? ...
1answer
72 views

### Turing Machine Variation

Hi i'm trying to figure out this question: Give a formal definition of multihead-multitape Turing machine. Then show how such a machine can be simulated by a standard Turing machine Can someone ...
2answers
89 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 ...
1answer
60 views

### How many digits of Chaitin's $\Omega$ constant would we know if we had a $\Sigma_1$-Oracle?

According to Wikipedia (and it seems intuitive from the definition itself), $\Omega$ is Turing equivalent to the halting problem and thus at level $\Delta_2^0$ of the arithmetical hierarchy. Do this ...
2answers
173 views

### Why is showing a language is Turing recognizable trickier than showing Turing decidable?

I have written a proof to show that a Turing Decidable languages are closed under union (amongst other things). Later, I have written a proof to show that Turing Recognizable languages are closed ...
1answer
39 views

### Prove or disprove: Superlanguages of Turing-recognizable languages are themselves Turing-recognizable.

Consider the following claim: Prove or disprove: If $L_a$ is Turing-recognizable and $L_b$ contains (or equal to) La, then $L_b$ is recognizable. I'd love to get a hint or a direction Thanks ...
0answers
80 views

### Equivalence of 2-dimensional Turing machine and a standard Turing machine

I'm asked to prove that a two-dimensional TM (one with 2-dim tape that has the upper-left end, and downwards and to the right it goes infinitely) is equivalent to a standard TM. Can I please get a ...
3answers
638 views

### Proving that a Turing Machine that only accepts even length strings is undecidable

I need to prove that a Turing Machine that only accepts even length strings in undecidable. The proof I was thinking is explaining the following: Given an input that contains even length strings, if ...
1answer
43 views

### Proving a language is Turing recognizable

Turing Machine M with a wait option has the option to make the machine's head wait where it is, until a case comes along where ...
1answer
87 views

### Where is the flaw in the following proof?

Where is the flaw in the following proof, that if a language is Turing recognizable then we can enumerate it? Proof Let $TM1$ be a Turing machine for language $L$. We can create an enumerator $E$ ...
1answer
102 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 ...
0answers
96 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 ...
2answers
79 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 ...
1answer
106 views

### Turing machines, halting problem

Let's assume there exists hardware that is able to compute the halting function H(n). That is, if you give it the number of a Turing Machine program/input combination, it will output a 1 if the TM ...
1answer
57 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 ...
4answers
412 views

### Is the set of PA theorems the same as the set of solvable halting problems?

I am not sure if this is a trivial question. By Post's theorem we know that every PA (first order logic) theorem is equivalent to stating that a given input C in a given Turing machine halts or ...
0answers
35 views

### Simulation time of Universal turing machine

How to Design a UTM in which the simulation time of TM M is only O($log |T| +log |Q|$) times more than the original execution time of M. where T & Q denotes the tape alphabet & states of M ...
0answers
79 views

### Implement a Turing machine, Solve the system of logical equations

№ 1 Implement a Turing machine: The input is a sequence of 0 and 1. The machine should be replaced every second 0 to 1. Example: 000111 replaced to 010111. To demonstrate the correctness of your ...
1answer
48 views

### Where does the input x in Turing Machine subroutines come from in solving reductions to undecidable problems?

I'm taking an introduction to computation theory class and we went over the chapter on undecidable problems and proving undecidability through reductions. I can't seem to grasp some of the simplest ...
1answer
90 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 ...
1answer
102 views

### 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 ...
2answers
132 views

### 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 ...
1answer
62 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 ...
1answer
110 views

### Baker-Gill-Solovay theorem

I have been trying to understand the proof of Baker-Gill-Solovay theorem as described in Complexity Theory: Modern Approach. I think I do understand most of it, but what troubles me is that let's say ...
1answer
352 views

### Language that is recursively enumerable, but not recursive

I have a problem with this task: Show that this language is recursive enumerable, but not recursive: $L = \{ w \in \{0,1\}^* | M_w(x)\; \text{converges for some input}\; x \}$ (where $M$ is turing ...
1answer
70 views

### Understanding of working of Turing Machine for $\{0^k1^k\}$

I try to learn Computation Complexity by Sipser's textbook "Introduction to the Theory of Computation". The problem is I have a lack in understanding how Turing Machine is working. Example from the ...
1answer
150 views

### How can a turing machine solve the element distinctness problem?

I am reading an example in Sipser's famous book on the theory of computation. In this example, Sipser creates a turing machine M to solve the element distinctness problem. M is given a list of strings ...
2answers
256 views

### How can Busy beaver($10 \uparrow \uparrow 10$) have no provable upper bound?

This wikipedia article claims that the number of steps for a $10 \uparrow \uparrow 10$ state (halting) Turing Machine to halt has no provable upper bound: "... in the context of ordinary ...
0answers
32 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 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 48, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9139069318771362, "perplexity_flag": "middle"}