Questions tagged [turing-machines]

Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.

Filter by
Sorted by
Tagged with
1
vote
0answers
325 views

Is there a name for a useful Turing-like machine that is more powerful (meaning accepts more languages) than a Turing machine?

Disclaimer: I'm a software engineer with only an undergrad education and have never published or anything so please forgive any minor notation or jargon blunders - but of course feel free to point ...
1
vote
1answer
2k views

How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

I have read of an algorithm that a non-deterministic Turing machine $N$ can run to determine whether a given graph $G$ has a Hamiltonian path from the start node $s$ to a certain node $n$: Write a ...
1
vote
1answer
114 views

Construct this two-taped Turing Machine {(u#,v#):u,v E {a,b}* , |u| = 2|v|}

I am having troubles trying to create this two-taped Turing Machine, I understand how I would get it to accept 2 strings of equal length. But to move forwards, I dont know how I would check to see if |...
1
vote
0answers
172 views

A question about $O(T \log T)$ simulation of a TM on some input by universal turing machine

In the textbook by Arora and Barak in Chapter 1 and section 1.7 they have proved how a UTM can do simulation in $O(T \log T)$ time. I have read it and understood everything except that how the $k$th ...
1
vote
2answers
80 views

Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$?

In the proof of Savitch's theorem from the 3rd edition of Sipser's Intro to Theory of Computation, Sipser claims that the maximum time that an $ f(n) $ space nondeterministic Turing machine that halts ...
0
votes
1answer
55 views

Isn't the given characterisation of recursively enumerable subsets of the class of all recursively enumerable languages?

$S$ is a subset of the class of all recursively enumerable languages over some finite symbols then $S$ is recursively enumerable iff If $L$ is in $S$ and $L'$ is a language such that $L ⊆ L'$ and $L'$...
0
votes
2answers
65 views

Questions about Turing Machine

Below I will list a concrete example and the confusion it causes. Let's first say we have a decision problem, which is: "Is X <= 400?" We define the alphabet as the set of natural numbers. The ...
0
votes
0answers
70 views

How can (generalized) Turing Machine tapes be defined?

Introduction I'm trying to formalize (generalized) Turing machines in Mizar (Wikipedia) and I'm looking for the optimal way to formalize the (generalized) tape. Note that you don't need familiarity ...
0
votes
0answers
266 views

What is the limit for Turing machines with 2 states and 3 symbols that halt?

I read here that a proof has been offered that a Turing Machine with 2 states and 3 symbols can be universal (in that it is capable of arbitrary finite computations). Even if this proof is accepted, ...
0
votes
1answer
1k views

how do I find a undecidable subset of a set that's decidable? [closed]

Given that Let S = {a | |a| is odd}. I know that since S is decidable, but does there exist a subset within S that is undecidable?
0
votes
3answers
109 views

Where does the need for conditionals (if, switch, jump tables, etc…) truly arise? [duplicate]

I know that this question is a bit out-of-the-box, yet i would be glad if someone could help with a good answers for my question because it is something that is troubling my curious mind. When we ...
0
votes
1answer
92 views

Determining if a TM decidable or not, with limited information

Were being asked to determine the whether this Turing Machine is decidable or not "Given a two way, one-tape DTM $M$ whose tape set is $\Gamma=${$a,b,B$} and a string $x\in${$a,b$}*, determine ...
0
votes
1answer
370 views

Prove that this language is decidable or undecidable

Is the following language decidable? L = {(M) : M performs at least 100 steps on every accepted input.} I tried to use reduction from the halting problem, but still no dice.
0
votes
0answers
230 views

Turing machine M overwrites a non-blank char by B (Blank)?

What are the implications of a non-blank character being over-written by a Turing machine M for the given input variable 'x'? Intention of the question: I am trying to answer how the halting ...
0
votes
0answers
142 views

Can we recognize wheter a Turing machine is a decider? [duplicate]

Let $L=\{ \langle M \rangle \mid M \text{ is a Turing Machine which halts on all inputs}\}$. Is this a Turing-recognizable language? I guess that it is neither Turing-recognizable, nor co-Turing-...
0
votes
1answer
2k views

Multiple-Choice Questions about decidability

I'm working on old MC-Questions about decidability und don't have the answers to the following ones: 1.) $L_1$ and $L_2$ are not decidable $\Rightarrow$ No superset of $L_1 \cup L_2$ is decidable 2.)...
0
votes
0answers
64 views

Decidability of a given language

$L_1=\{ ⟨M⟩ ∣M$ takes at least 2016 steps on some input$\}$ the answer says $L_1$ is recursive. I am stuck at one point and i am wasting my time on it here for $L_1$ if we are given a set of to see ...
0
votes
2answers
2k views

Can languages with infinite strings be recursively enumerable?

I am not 100% sure about the definition of recursively enumarable languages. Yes I know how are they defined: There has to exist a Turing machine that accepts all wrods of the language and halts but ...
-2
votes
2answers
77 views

Why Rice theorem work for decidability?

Rice's theorem states: Every nontrivial property of recursively enumerable language is undecidable. I came across following problems, which Ullman's books say both are undecidable: Turing ...
-2
votes
2answers
421 views

If I prove that a language is not a CFL, can I assume it is Turing-Decidable?

Lets say I have just used the pumping lemma to prove a certain L language is not CFL. If it is not CFL can I use that as a proof that it is Decidable? Or is this not enouph and I still have to ...