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
1 answer
Turing Machine that orders the alphabet/characters of the entered string based on the frequency of each symbol
Give the following problem:
Design a Turing Machine such that given string from the alphabet $\{a, b, c, d\}$, produces on the tape a combination of the string "abcd" in which each symbol occupies the position coresponding to the relative order of…
Omari Celestine
- 1,025
1
vote
1 answer
How to insert symbols into tape?
I have this problem. The input alphabet is $\{A, B\}$ and I should design a machine that converts a single $A$ into $AC$. That is, a string like $ABAB$ should become $ACBACB$.
This means that there are cases where I have to memorize what is read…
Miagu
- 13
1
vote
2 answers
Why does this algorithm not prove that a language is Turing recognisable?
I saw this example in a textbook and a statement saying that this algorithm cannot be used for the forward direction of a proof that proves a language is Turing recognisable iff some enumerator enumerates it.
$s_1, s_2$ ... is a list of strings…
Y Ahmed
- 95
1
vote
1 answer
Is L Turing decidable?
Please help me get this right,
The question asks Is L Turing decidable ?
where L ={ : M is a TM, which accepts some palindrome
My thoughts on the poof to show that it is undecidable are the following.
Assume L is decidable and let R be a decider…
acagu
- 53
1
vote
2 answers
Turing machine that accepts language in n+1
Let $\Sigma$ be a finite alphabet and $L \subseteq \Sigma^n$. I want to show that there exists a Turing machine, which accepts $L$ and has a calculating time of n+1.
Pazu
- 1,077
1
vote
1 answer
Does "whenever / whether" equals to iff?
I encountered a question that goes like this:
M is a TM that accepts w^r whenever it accepts w
which of the following does it mean?
M accepts w^r <-> M accepts w
M accepts w^r -> M accepts w
M accepts w -> M accepts w^r
same question for…
Davis8988
- 125
1
vote
2 answers
Simulating non-deterministic Turing Machine with 3 - Tape.
I'm reading Sipser's description of a deterministic Turing machine D that is simulating a non-deterministic one (Page 179, Chapter 3).
3-Tape Diagram of Turing machine D
I'm having trouble understanding the behaviour of the 3rd "address" tape. I…
J Z
- 23
1
vote
1 answer
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 any help appreciated!
John Hoffman
- 2,734
1
vote
1 answer
Difference between Turing unrecognizable and Turing undecidable language
I get the fact that due to diagonalization argument number of language is uncountable and since TM are countable, hence there are some language which is not recognized by the Turing machine. I also read this recognizable vs decidable question.The…
motiur
- 207
1
vote
1 answer
Is each string decideble?
Is it possible to prove that there exist for every string a Turing Machine that decides that string?
I think it is provable that for every string you can build a TM that recognises that string, but I cannot find such a TM to decide a string.
user329394
- 11
1
vote
1 answer
Turing recognizable - $B = \{a^n b^n c^n \}$
Question:
My answer is no, because it loops forever. But I am a bit unsure if this is the right answer.
TheFermat
- 365
1
vote
2 answers
Do there exist infinite sets of non-halting programs such that every program in the set computes every other program in the set?
Do there exist infinite sets of non-halting programs such that every program in the set computes every other program in the set, and only programs in that set?
I know there exist programs which compute every other program, by diagonalizing on the…
1
vote
1 answer
Busy Beaver simple nonhalting rule
Regarding the busy beaver function, what's a simple rule to prove that the machine runs forever in one direction? I believe there's something about the machine not backtracking far enough before it repeats a state?
As an example, prove that this…
Frucifer
- 11
1
vote
0 answers
prove that language is not decidable (string and reverse)
Prove that $T=\{\langle M\rangle\mid M \text{ is TM that accepts $w^R$ iff it accepts $w$}\} $ is not decidable. I have no idea how to start. Help me, please
user220688
- 509
1
vote
1 answer
Deterministic Turing machine for a duplicate concatenation of a string
What's the best approach for building a deterministic Turing machine for the language
$$L = \{vv : v \in \{a,b\}^+ \}$$
where there is no midpoint marker in the string? How can we determine where one v ends and where the other v begins?
stevetronix
- 433