Questions tagged [turing-machines]
This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
793
questions
0
votes
0answers
20 views
How to Design Turing machine for n=1^(n+1), n>=0
by F(n) = 1 if n is even and 0 otherwise
Ex q0BnB -> qfB1B, qfB11B
and Tape set, only one composite symbol, including 1
2
votes
1answer
97 views
Why is $f_1(n)$ not computable but $f_2(n)$ is?
I have the following two functions, where the first one is not computable and the second one is.
$$f_1(n)= \begin{cases}
1 & ,\text{if in the decimal representation of n appears in the ...
0
votes
0answers
39 views
Attempted proof of undecidability of halting problem
I've heard before that the proof of the halting problem is a straightforward application of a diagonalization argument. However, I haven't actually tried to carry it out before. I think the argument ...
0
votes
0answers
30 views
Do the Robinson and/or Peano arithmetics suffice to prove that the Halting problem is undecidable?
Robinson and Peano are both rather weak systems, but they suffice to capture the rules of the natural numbers sufficiently to talk about the Gödel numbering etc., and Kleene's T predicate indicates ...
1
vote
0answers
48 views
Decider that reject All inputs if and only if Goldbach's conjecture has a counter example
I want to design a $Decider$ such that for every input accept if and only if Goldbach's conjecture is true and reject all inputs if and only if Goldbach's conjecture has a counter example.
I made a $...
0
votes
0answers
21 views
Diagonalization for Etm
$E_{TM} = \{\langle M\rangle\mid M$ is a TM and $L(M) = \emptyset\}$
We want a proof by diagonalization to show that $E_{TM}$ is undecidable. But the form of inputs are like $<M>$ and the Table ...
2
votes
1answer
73 views
Arithmetical Hierarchy
So i was reading the book "Turing Computability" of Soare.
I read about the Arithmetical Hierarchy.
There we it's defined that:
$$B \in \Sigma_n \iff (\exists y)(\forall x_1)(\exists x_2) \...
3
votes
2answers
54 views
Question: are quantum computers a type of Turing machine or something else?
I read that in quantum computations you can not examine the internal state of the computation while it is happening. This is something I thought is always possible with Turing machines. Does this mean ...
1
vote
1answer
64 views
How to simulate $IF \ x_i \neq 0 \ THEN \ P \ END$ in a LOOP program. [closed]
I want to simulate the following IF loop in a LOOP program:
$$IF \ x_i \neq 0 \ THEN \ P \ END$$
I know that $IF \ x_i = 0 \ THEN \ P \ END$ in LOOP is:
$$x_j :+ 1; LOOP \ x_i \ DO \ x_j := 0 \ END; ...
0
votes
0answers
36 views
Can a finite Turing machine model itself?
Given the following constraints, can a finite Turing machine (FTM) model itself?
An FTM receives only data initially stored on its tape;
The amount of initial data on the tape is limited to $D_{m}$ ...
1
vote
1answer
50 views
What does $w' := <M'>$ mean in the context of the Halting Problem?
I am studying the Halting Problem and I came across the following notation. I am not sure what it means. The context is as follows:
To prove that the Halting Problem is undecidable, we employ proof ...
0
votes
1answer
16 views
Is the language $L=\{<M>|M \text{ has 24 states}\}$ recursive?
I know that I cannot use the rice theorem because there are two turing machines that calculate the same function but have different ammount of states. What techniqu can I use to prove that this ...
0
votes
1answer
44 views
Explaining the difference between two definitions for recursively enumerable languages.
I'm a little confused about the definition for recursively enumerable languages in my script. A recursively enumerable language is defined as:
A language $A \subseteq \Sigma^*$ is called recursively ...
0
votes
0answers
11 views
Show that the “slowdown” in the use of k > 1 tape to k = 1 tape is not too significant.
We Let A be a language that can be decided in time T by a 2-tape Turing machine M2. Then there is a 1-tape Turing machine M1 that decides A in time O(T^2).
Proof.
We will sketch the proof for the case ...
1
vote
0answers
21 views
Understanding this proof: intersection of acceptable languages are acceptable
I'm reading this and the first part in Lemma 4 is confusing:
Lemma 4. For all acceptable languages L and L′, the languages L ∪ L′ and L ∩ L′ are also acceptable.
Proof: Let M and M′ be Turing ...
1
vote
0answers
139 views
Given a Turing Machine $M$ and a word $w$, can we tell if the Turing Machine will move its head at every step?
The exercise I'm trying to solve is: Is the language $L = \{<M>,w\ |\ M \text{ moves its head on input } $w$ \text{ at every step}\}$ decidable or undecidable.
We work with a version of the TM ...
0
votes
0answers
29 views
What is the intuitive reason why there is no recursively related notation-system which gives a name to every constructive ordinal?
The Question: I found this claim in Douglas Hofstadter's book 'Gödel, Escher, Bach'. The author says that this result was proven by Church and Kleene. Correct me if I am wrong, but I interpret this ...
0
votes
1answer
51 views
Does the MIP*=RE presentation imply that the Turing Halting Problem is solvable?
I noticed an article where the author seemed to imply the halting problem was solved so I found the paper he was referencing but it is over my level of knowledge.
Was hoping someone in the community ...
2
votes
1answer
48 views
How to code a model by a real number (an infinite sequence of bits)?
The proof of Lemma $2.10$ in the paper “Feedback computability on Cantor space” mentions “any fixed standard way of coding a model by a real.”
What does it mean? What can be an example of how to code ...
1
vote
0answers
28 views
If language L is decidable show that $L^R$ is also decidable.
If L is decidable, then the language $L^R$ = {$w^R$|w ∈ L} of the reversals of all strings in L is decidable too.
My approach to this was to define M' as a decider for $L^R$ such that it was a ...
0
votes
1answer
71 views
Is the halting problem still an open problem?
(Spoiler: Turing was right!)
I was thinking about Turing's proof that the halting problem is undecidable. But can the paradox, which is often given as a proof, be broken?
Proof that a single program ...
-1
votes
1answer
38 views
Turing reductions
During the proof that $K_1 \equiv_T K$ , difficulties arose with the proof of $K_1\leq_T K$. On the one hand, I used the theorem that if A is enumerable, then $A \leq_T K_1$.
Here $K_1=\{<n,m>|m\...
0
votes
1answer
46 views
Let $f$ be a computable and injective function. Is $f^{-1}$ computable and injective?
So I just started learning about computability, undecidability and Turing machines. And I wonder if:
Given a computable and injective function $f$, is $f^{-1}$ also computable and injective?
I don't ...
0
votes
0answers
18 views
Incompleteness of semi recursive languages
Let $L=\{\langle M_1 \rangle, \langle M_2 \rangle,...\}$ be a semi recursive language of gödel numbers of turing machines with input alphabet $\Sigma=\{0,1\}$ which always terminate and decide some ...
0
votes
2answers
23 views
Construct a TM to show that {<G,s,t,k> | G is a directed graph with path length $\le$ k from s to t} is in class P
I would like to construct a deterministic TM that decides $L=${$<G,s,t,k>$ | $G$ is a directed graph that has a path of length at most $k$ from vertex $s$ to vertex $t$} in polynomial time.
So ...
0
votes
1answer
45 views
Is $L=\{\,a^ib^jc^k \mid i=2j=3k\, \}$ a Turing language?
Is $L= \{a^ib^jc^k \mid i=2j=3k\}$ a Turing language?
At first I thought it was possible to scan the tape and for each $c$ delete the amount of $a$ by the amount of $b$, it works when the input is $...
1
vote
0answers
49 views
Two problems related to NP-Hard and why they are true?
$F(z_1,...,z_n)$ is a Boolean expression. The assignment of variable ($x_1,...,x_n \in {0, 1}$) is the answer of $F$, if $F$ for that assignment equals to $1$.
If that case is true and the conditions ...
2
votes
1answer
33 views
Why is it enough to test only the words up to length n ( number of state) in the given algorithm for a decidability problem
My question is related to the problem below, basically it's a decidability problem and the algorithm prooves it's decidable.
My question :
After reading the step 2 of the algorithm below, why is it ...
1
vote
1answer
51 views
Does proof of FOL undecidability require tacit appeal to the Church-Turing Thesis?
We can prove that FOL is undecidable using a strategy based on the undecidability of Q. But does this latter proof require tacit appeal to the Church-Turing Thesis?
2
votes
1answer
64 views
Can we give an equivalent definition for computable numbers without mentioning turing machines?
Let $\mathbb{R}$ be the set of all real numbers, as defined by dedekind cuts. Given $\mathbb{R}\subset\mathscr{P}(\mathbb{Q})$, and we have a construction of $\mathbb{Q}$ as as a set of equivalence ...
0
votes
1answer
38 views
How to show that this language is Turing recognizable
So this question has two questions and i have to use the answer from 1 to answer question 2. Assuming that my answer for 1 is good. I need help with 2. ( Correct me if wrong please.)
Question 1 :
Show ...
0
votes
1answer
44 views
If L1 is decidable and if L2 is included in L1, is L2 also decidable?
Is this statement true or false and why ?
If $L_{1}$ is decidable and if $L_{2}$$\subseteq$$L_{1}$ then $L_{2}$ is also decidable.
I would be tempted to say yes, but i am really not sure. I am also ...
2
votes
1answer
82 views
How to show that this language is decidable
The question :
The language is $L=$ { $< G,w > $ : $G$ is a grammar in normal form of Chomsky and $w$ is a word on the terminal alphabet that can be derivated in $G$ by at least 2 differents ...
2
votes
1answer
82 views
Show that the following language is decidable by finding the algorithm for the finite automaton
Given the language $K$ = $\{<M>: M$ is a finite automaton on the alphabet {0,1}) and $L(M)$ contains at least one word of the form $0^k1^l$ with $k,l\geq 0$}. In other words, describe an ...
1
vote
0answers
46 views
Show that this language is undecidable
Given the language $K$ $=\{<M> $ where $M$ is a turing machine ( that is on the alphabet {0,1}) and $L(M)$ contains at least one word of form $0^k1^l$ with $k,l\geq 0\}$
I would like to know if ...
0
votes
0answers
40 views
First value of the second order busy beaver function?
There is a bit of talk about the busy beaver function. It was asked whether or not it is possible to make a function that grows faster than the normal busy beaver function.
One way to do this is to ...
1
vote
1answer
39 views
Best approach for Undecidability proof
Context:
Hi, my professor sent me this challenge and I got stuck. I thought using Rice's Theorem for this question, since $M$ is non-trivial, but he told me to use a reduction.
Is he right? Should I ...
0
votes
2answers
96 views
How to prove undecidability other than Rice Theorem?
Im studying Rice Theorem and I would like to verify its consistency. If I am able to prove de undecidability in other ways, the Rice Theorem would prove to be useful after all.
Im trying to find out ...
0
votes
0answers
120 views
Turing machine to copy string
I'm trying to design a TM intended to copy a string before an initial symbol. For example, if I input:
**@bba**
the machine should copy:
...
0
votes
0answers
23 views
NP closed under Kleen Star (Proof step misunderstood)
I had a question about the proof that NP is closed under *.
Here is the proof I'm using, from Sipser's
We make a non deterministic Turing machine that decide L * in non deterministic polynomial time.
...
1
vote
2answers
54 views
How to prove a function is computable?
I'm reading Computation Complexity: A Modern Approach and one of the exercises is:
Prove that [the addition function is] computable by writing down a full description (including the states, alphabet, ...
0
votes
0answers
25 views
How could one prove the Turing-recognizability of a class of formal languages?
I'm currently trying to figure out my approach to a problem that asks me to prove the Turing-recognizability/ enumerability of a class of formal languages. (Let's say for example, all languages that ...
0
votes
1answer
64 views
show this language is undecidable
$L = \{ \langle G \rangle \mid G$ is context-free, $L(G)$ contains a palindrome $\}$
Reduce the post correspondence problem to $L$.
So I have to show that if I could decide L then I could decide PCP.
...
0
votes
0answers
26 views
Turing machine with any integer shifts
Prove that the set of computable functions does not change if we allow the Turing machine any integer shifts.
I think that we can do it by adding some conditions and doing simple shifts, but don't ...
0
votes
0answers
30 views
Prove that the set of computable functions will change if the Turing machine is prohibited shift to the left.
I (+-)know that set of computable functions does not change if we allow the Turing machine
any integer shifts. But how to prove that the set of computable functions will change if the Turing machine ...
0
votes
1answer
33 views
What is the complement of the acceptance problem of a Turing machine?
I know that the acceptance problem of a Turing machine is the problem to decide if for any turing machine $M$, given a string $w$ the Turing machine accepts $w$ or not. If the not acceptance of a ...
0
votes
1answer
49 views
How to show that this languange is not turing-recognizable?
Let $S=\{<M> | M \textrm{ is a } TM \textrm{ and } L(M) = \{<M>\}\}$ how can I show that $S$ isn't turing-reconizable? Besides that, what $L(M) = {<M>}$ means?
0
votes
0answers
46 views
Recognizable not decidable subset
Prove that an infinite $(|L|=|\mathbb{N}|) $ language L has an infinite, recognizable and not decidable subset
I have already proved that L has an infinite not recognizable subset A, but I don't know ...
0
votes
0answers
16 views
Infinite recognizable not decidable subset of a language
If L is an infinite ($|L|=|\mathbb{N}| $) decidable language, prove that it contains:
a) An infinite subset that is not recognizable
B) An infinite subset that is recognizable and not decidable
For ...
0
votes
0answers
33 views
Proving that a set is unrecognizable.
Define $K = \{x\in \mathbb{N}: x\in W_x\}$ where $W_e$ is the set recognized by Turing machine with code $e$.
Now, I want to prove that, $\overline{K}$, the complement of $K$, is unrecognizable.
In my ...
