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 Halting problem
I have come across this halting problem question during my exam preparation and can't come up with a solid proof for the following question.
Question:
Let L be { Ti does not halt on input i}
Show that there is no Turing machine T such that T halts…
user2390775
- 13
1
vote
0 answers
Dual Turing Machine Simulation
(1) Define a Turing Machine that simulates a Dual Turing Machine (DTM)?.
A dual Turing Machine is defined as a Turing Machine with 2 heads and 2 tapes. At every step, the DTM can
read from either tape
write to one or both tapes
move 0/1/2…
Bovik Wing
- 33
0
votes
1 answer
Single tape Turing Machine and a Single Push Down Stack
The alphabet for all of the following problems is the same: A, B, C, and null. But I can use an additional character D if I want for this problem.
The initial tape is (A+B+C)*
The initial stack is empty
The final tape is empty
The final stack…
0
votes
1 answer
path of non-deterministic and deterministic turing machines
So let's say that we have state 1 2 and 3.
In both the non-deterministic and the deterministic turing machine, we only have one-way transitions between the state 1, 2 and 3. For example, if we can go to state 3 from state 2, we can't go to state 2…
john
- 21
0
votes
1 answer
Turing Machines and Decidability
I saw this question in a textbook on decidable languages, and I was wondering how you would go about solving this type of question:
Assume L1 and L2 are decidable languages. Which of the following are decidable?
a. L1 Union L2
b. L1 Intersection…
0
votes
1 answer
Constant value function Turing machine.
How would one go about writing a Turing machine which always computes to a certain value?
If the value is small, the problem is trivial of course, but how could I write a Turing machine for the function f(x) = 1000 for example?
oh54
- 101
0
votes
0 answers
$2023_{TM} $ = {$⟨M⟩$| M is a TM and there exists an input w on which M moves the tape head to the left of cell number $2023$} is decidable
Consider the following problem:
Given a semi-infinite tape Turing Machine M, determine if there exists an input w on which M moves the tape head to the left starting from cell number 2023 (i.e., if at some point during the computation, the head…
guglielmo
- 31
0
votes
1 answer
Is this language context-sensitive?
I want to make a grammar for the language consisting of all strings of $a, b$ and $c$ (including $\epsilon$) such that the number of $a$'s, $b$'s and $c$'s is equal.
The idea is to use nonterminals $A,B$ and $C$ and permute them in every way and in…
likeAvirgin
- 157
0
votes
0 answers
Is there any standard notation for turing machines outcomes?
On 2 symbols 1-state turning machine, there are 64 posible machines taking into account their transition tables.
One of this machines could be:
$$A0:0LA$$
$$A1:0RH$$
(meaning:
in state A, reading a 0, write 0, goes left and transition to A,
in state…
Eduard
- 304
0
votes
0 answers
Understanding Halting Problem, regarding the "input"
Before asking: My background is natural science and a bit of "coding" skills. I didn't study rigorous mathematics and logics since undergrad freshman, and this question is based on some videos and articles I read on the internet.
I've seen a lot of…
Hojin Cho
- 164
0
votes
0 answers
Equivalence of Position-Based Turing Machine Model to Standard Model
I came across this question:
A position-based Turing machine model is the same as the normal model except for the following change - the transition function also depends on the current position of the head. Prove/disprove: A position-based Turing…
Nalog
- 59
0
votes
0 answers
turing machine show equivalence
I have a question regarding proofs to show the equivalence of different turing machines and their possible time and space overhead:
I have to show, that a usual deterministic turing machine is equivalent to each of the following:
read-only input…
xxray
- 19
0
votes
0 answers
Turing machine problem.
I saw a problem of a Turing machine that seemed interesting to me, it is the following:
Construct a TM that decides if a given word has a even number of 0's and an odd number of 1's.
I wanted to give it a try and see if you guys could help me with…
asd asd
- 533
0
votes
0 answers
create a turing machine that decides the following language
I want to create a diagram of a turing machine that decides the following language.
$\{w \in $ $\{a,b\}^*: w = u^n, u \in \{a,b\}^+, n \geq 2\}$
The diagram I had planned to make was a very simple one, but I don't know if it would meet the goal of…
Sebastian
- 31
0
votes
0 answers
Is self-reference required to show the halting problem is undecidable?
The common proof of the undecidability of the halting problem using a hypothesized halting-decider HALTS and constructs a pathological Turing machine $M$ that halts on a string $w$ exactly when HALTS($M,w$) rejects.
This common proof relies on…
tw931
- 1