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
0
votes
1 answer
Is this Turing machine correct?
I think this Turing Machine for a^k b^k k>=0 is correct:
But if I need a^k b^k a^k b^k k>=0, is it correct the same picture? Or this:
0
votes
1 answer
Halting Problem with True/False Answer
The simplified explanation to the Halting Problem relies on the contradiction in if you have a Turing Machine H that can decided if a program p halts, it loops forever if p halts and halts if the p doesn't. Then be feeding this program into it's…
MikeS159
- 123
- 4
0
votes
1 answer
Turing machine for any language
I am trying to prove that for any language over an alphabet there is a
a) Turing machine which halts on all inputs and if it accepts a string, then it is in our language $L$
b) There is a Turing machine which halts on all inputs and if it rejects a…
Raton
- 729
0
votes
1 answer
Is it possible to make a turing machine counter for decimal numbers?
I'm solving a complex task using turing machines. To solve it, my idea was to use a turing machine, that would count decimal numbers, one digit per one place on the tape (# 1 #, # 2 #, ..., # 9 9 #, ...) . But as my knowledge of turing machines is…
T.Poe
- 147
- 8
0
votes
0 answers
Turing machine remembering its position
I want to built a TM, which can remember its position $n$, jump to the beginning of the tape and then iterate to the right until it's on the position $n-1$ (I can't use step to the left). I don't know how to achieve this position remembering and…
T.Poe
- 147
- 8
0
votes
0 answers
Any suggestions on how to go about proving that C generates infinite number of strings?
I know how to write pseudo code for proving C is CFG but how do i prove it generates infinite number of strings?
Prove that this language is Turing-decidable by designing Turing machine
pseudocode for a machine that decides it.
L1 = {〈C〉|C is a CFG…
kbreezy
- 1
0
votes
1 answer
In a Turing machine, can we determine how many times a loop will be processed?
I'm writing a transition diagram for a Turing Machine which will compute Stretch(y+1). the output consists of the string that replaces each input letter with y copies of that input character. Is it possible to have y as a variable in my diagram and…
Martyna
- 1
0
votes
1 answer
Prove that L = { | ∈ L(M)} is undecidable
Prove that $L=\{ \langle M \rangle \;|\; \langle M \rangle \in L \left( M \right) \}$ is undecidable. Hint: If there were a decider TM DL for L, what would happen if we gave DL its own description as input?
Here's what I've got so far:
ATM…
0
votes
1 answer
Modify a Turing Machine
How can we prove that every Turing machine $TM$ can be altered to a new Turing machine $TM'$ which can perform $2$ of $3$ operations in every step, how can we define this altered Turing machine.
$TM: \delta(Q \times \Gamma) \to Q \times \Gamma…
Alex Louis
- 3
- 1
0
votes
1 answer
Is there a language not in NP but for which exists a Non-deterministic TM which accepts/rejects strings based on belonging to the language?
Is there a language $L$ such that $L \notin NP$, and $\exists$ Non-deterministic Turing Machine $M$: $\forall l \in L$ : $M$ accepts $l$, $\forall l \notin L$ : $M$ rejects $L$?
A side-question. Are the following two statements equivalent?
$\exists$…
CrabMan
- 1,123
- 7
- 16
0
votes
0 answers
Determine to which class $\left\{\langle M\rangle\Big\vert L(M)\in RE\setminus R \right\}$ belongs
As stated in title I want to determine to which class
$$S=\left\{\langle M\rangle\Big\vert L(M)\in RE\setminus R\right\}$$
belongs. I believe that $S\notin RE\cup\text{co}RE$.
In order to show that $S\notin RE$ I tried to reduce…
Galc127
- 4,451
0
votes
1 answer
Using reductions of turing machines properly
I recently learned about reductions of Turing machines (here after TM), and here is a solution to a problem using reduction (showing L is undecidable, as defined bellow). I have given the reduction, correctness proof and my understanding of it. I'm…
user115919
- 91
0
votes
1 answer
Drawing a state diagram for a Turing Machine
I'm a bit rusty since it's been a couple weeks since I've last done this, but I could really use some help with starting out the Turing Machine for $\{a^i b^j c^k \mid i = j + k\}$
I'm confused on how I can make the number of a's = b's+c's since…
yoyoma207
- 113
0
votes
0 answers
What is the maximum amount of steps a Turing machine needs to take before you know it won't accept the input?
So for example, we take a Turing machine $M$ with alphabet $\{0,1\}$ and 10 states, where $q_0$ is the initial state and $q_F$ is the accepting state. For a certain algorithm or calculation $M$ is allowed to take $x$ amount of steps, for example $x…
user5368737
- 217
0
votes
0 answers
Prove that language $X$ is not decidable
$$X =\{\langle M, w\rangle \mid\text{$M$ has one tape and never modifies portion of the}$$ $$\text{tape that contains the input $w$}\}$$
And my proposition: Let $@$ will be character such that there is no $@$ in alphabet. Let suppose, that $X$ is…
user220688
- 509