Tagged Questions
-4
votes
0answers
55 views
Understanding this specific turing machine, NOT HOMEWORK
In regards to the turing machine below, what is it's language? What is the final string if the input is 0011 and in general. what kind of 4 symbol strings does the turing machine accept? I am trying ...
-4
votes
0answers
68 views
Turing Machines!!! Please check! [closed]
I was having a hard time understanding and solving this question that wants me to show the final tape and figuring out if whether or not the turning machine accepts it or not. I have a list of 20 ...
0
votes
0answers
128 views
Turing Machine question, this is NOT HW
I was having a hard time understanding and solving this question that wants me to show the final tape and figuring out if whether or not the turning machine accepts it or not. I have a list of 20 ...
-1
votes
1answer
67 views
Decidability/Undecidability Question
Could someone please help me with this question? I'm really having a hard time understanding reductions and decidability.
Prove that the language $$L = \{\langle M,N \rangle \mid M,N\text{ are Turing ...
0
votes
1answer
78 views
Decidability of a Turing machine always halting in at most ten steps
I've exam comping up soon and I need help with this. Consider the problem:
Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input.
Is this decidable? Prove your ...
0
votes
0answers
128 views
Turing Machine that accepts the language { www : w ∈ {a, b}*} [closed]
Turing Machine that accepts the language { www : w ∈ {a, b}*}
I'm trying to solve this but I'm not sure how to start! I understand how to solve it if it only has ...
0
votes
1answer
171 views
Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3.
I have exam coming up and I need help with this:
Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3
Thank you :)
1
vote
4answers
78 views
Non-Deterministic Turing Machine Algorithm
I'm having trouble with this question:
Write a simple program/algorithm for a nondeterministic Turing machine that accepts the language:
$$
L = \left\{\left. xw w^R y \right| x,y,w \in \{a,b\}^+, ...
0
votes
1answer
76 views
Turing Machine Variation
Hi i'm trying to figure out this question:
Give a formal definition of multihead-multitape
Turing machine. Then show how such a machine can be simulated by a standard Turing
machine
Can someone ...
0
votes
0answers
36 views
Simulation time of Universal turing machine
How to Design a UTM in which the simulation time of TM M is only O($log |T| +log |Q|$) times more than the original execution time of M.
where T & Q denotes the tape alphabet & states of M ...
1
vote
1answer
360 views
Language that is recursively enumerable, but not recursive
I have a problem with this task:
Show that this language is recursive enumerable, but not recursive: $L = \{ w \in \{0,1\}^* | M_w(x)\; \text{converges for some input}\; x \}$ (where $M$ is turing ...
