This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
0
votes
0answers
20 views
Variation of 3SAT is in NP-Complete
Consider the problem of "K-3SAT", a variation of 3SAT: Given a 3CNF formula O and an integer k, the machine determines whether the formula O has a satisfying assignment in which at most k variables ...
1
vote
1answer
16 views
Proving that the independent set problem is in NP-Complete
Consider the problem of "Independent set" in grahps. Given a graph G and an integer k, the machine determines whether the graph G contains an independent set of size k.
I need to prove that it's in ...
0
votes
0answers
13 views
Time complexity of the described DTM
There is a DTM with alphabet $\Sigma = \{∗, 0, 1\}$, that on input $1^n$ outputs $1^n ∗ 1^n$. That is it takes a string of $n$ ones and replaces it by two strings of $n$ ones, separated by a blank ...
0
votes
0answers
18 views
Simulating an alternating Turing Machine
I'm trying to figure out this question:
Let's say we have an alternating Turing Machine that makes a restricted number of alternations (i.e. switches from a universal to an existential state or vice ...
1
vote
1answer
37 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 ...
1
vote
2answers
119 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 ...
3
votes
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 ...
0
votes
0answers
28 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 ...
1
vote
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 ...
2
votes
1answer
127 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 ...
-4
votes
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 ...
-4
votes
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 ...
0
votes
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 ...
0
votes
0answers
128 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 ...
2
votes
1answer
58 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 ...
-1
votes
1answer
68 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 ...
0
votes
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 ...
0
votes
0answers
128 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 ...
0
votes
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 ...
0
votes
1answer
171 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 :)
1
vote
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 ...
0
votes
1answer
36 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.
4
votes
2answers
110 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 ...
1
vote
4answers
78 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\}^+, ...
2
votes
1answer
146 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?
...
0
votes
1answer
76 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 ...
1
vote
2answers
93 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 ...
5
votes
1answer
64 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 ...
2
votes
2answers
179 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 ...
0
votes
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 ...
0
votes
0answers
81 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 ...
1
vote
3answers
680 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 ...
0
votes
1answer
44 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 ...
2
votes
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$ ...
-2
votes
1answer
103 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 ...
7
votes
0answers
97 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 ...
6
votes
2answers
80 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 ...
1
vote
1answer
107 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 ...
3
votes
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 ...
7
votes
4answers
415 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 ...
0
votes
0answers
36 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 ...
0
votes
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 ...
1
vote
1answer
50 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 ...
1
vote
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 ...
4
votes
1answer
103 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 ...
2
votes
2answers
133 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 ...
1
vote
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 ...
1
vote
1answer
115 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 ...
1
vote
1answer
363 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 ...
1
vote
1answer
71 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 ...
