This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
Questions tagged [turing-machines]
954 questions
1
vote
0 answers
Turing Machine exercise
I would like to design a Turing machine that takes as input a tape with a sequence of As and counts them, writing the result in decimal at the end of computation.
Example: initial tape: $AAAAAAAAAAA \to $ Final tape: $11$.
My problem, here, is…
banana23
- 19
1
vote
0 answers
Turing Machine for $ = \{^n ^ c^{2^{nm}} : n,m\ge 1 \}$
This question requires high level description of Turing machine.
I found that we are able to solve a^n b^m c^nm by :
Step 1 : crossing out one a
Step 2 : continue to cross out one b followed by one c once until b are all crossed out.
Step 3 : we…
XX12
- 11
1
vote
1 answer
Formal definition of one Turing machine simulating another
Here on Wikipedia is says "In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input". I would like to know what the formal definition of 'simulate' is in reference to…
Mathew
- 1,894
1
vote
0 answers
The countability of the set of all Turing machines
There are many questions like this but I couldn't find what I was looking for in them.
I already know that the set of all Turing machines is countably infinite but I couldn't find
a proof of this, also it doesn't make sense to me intuitively.
So, my…
DavidDvali
- 11
1
vote
1 answer
What is the meaning of "w describes a halting TM" mean?
I was originally looking for languages that weren't context sensitive.
In Wikipedia (https://en.wikipedia.org/wiki/Chomsky_hierarchy), I believe the language $\{w | w \text{ describes a terminating TM} \}$ isn't a CSG. I'm not sure how a TM is…
Anon
- 2,460
- 1
- 15
- 23
1
vote
0 answers
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 machines that decide L and L′, respectively.
I don't…
sprajagopal
- 622
- 1
- 5
- 20
1
vote
1 answer
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?
Axuuuu
- 11
1
vote
0 answers
Will this turing machine accept this language?
I have to design a turing machine that will accept the language L={w1^n | w∈Σ∗ and w has exactly n distinct symbols from Σ and 1 is not in the alphabet}. My idea is to create a turning machine that has 2 stages, the first checks every element in w…
1
vote
0 answers
Turing Machine for $L = \{ a^ib^j \mid 0 \lt i \lt j \}$.
I would have a brief question about how to construct a Turing machine that is accepting only this language:
w E L = { aibj | 0 < i < j }.
Anyone can help?
stevienailstail
- 11
- 2
1
vote
1 answer
Turing machine which can find the center of a string
Is it possible to do it in $O(n \log n )$ ? or is the best solution $O(n^2)$? if yes, what's the idea to do so ?
Jaimy Hellen
- 13
1
vote
0 answers
Is there a name for a single state turing machine with two heads?
I noticed that if we had a Turing machine that looks not only at one position on a tape but two positions next to each other it is possible to make a single-state Turing machine.
For example the tape might be:
10010101010G01011010
^^
The…
zooby
- 4,343
1
vote
1 answer
Turing Machine for vertex cover
Give a polynomial-time Turing Machine which, given
a graph G and an integer k as input, will halt and output a vertex cover of G of size at
most k — that is, it halts with the encoding of an actual vertex cover on its tape.
I know a general…
Ozzy Dozzy
- 21
1
vote
1 answer
Minimum Number of states turing machine
I think my question is rather simple, but I can't wrap my head around it. In "The (new) Turing Omnibus" on page 266, the author writes:
[...], and let A be a [Turing-]machine that converts a blank tape to one with the number n written in binary on…
John Doe
- 13
- 3
1
vote
0 answers
Turing machine that accepts strings $w$ of ${a,b,c}$ where $w = a^i b^j c^k$ and $i\ge j$, $j\ge k$, and $i,j,k \ge 0$
Basically a Turing machine that accepts strings that look something like aaabbcc or even aabc or abc. There just has to be at least one of each letter and they have to be in that order and there needs to be more or equal a's than b's and more or…
David -
- 11
1
vote
1 answer
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 halts and a 0 otherwise. “Super Turing Machine”…
user60465
- 147