Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
1
vote
1answer
13 views
Universal Turing machine and virtualization technology
I was wondering if virtualization technologies (VmWare, virtual box) are possible thanks to the theoretical existence, translated into practice, of the concept of universal turing machine or if the ...
0
votes
0answers
9 views
building turing machine for busy beaverproblem
I have tried to build a turing machine for busy beaver problem that has BB(2,3) two variables and three variables but i am not sure if its correct or it needs any changes
1
vote
1answer
17 views
Turing recognizable language between languages that aren't recognizable?
Let $L_{1},L_{2}$ be languages that are not Turing recognizable, and let $L$ be a language such that $L_{1} \subseteq L \subseteq L_{2}$.
Is $L$ also not Turing recognizable?
I am inclined to ...
1
vote
1answer
30 views
Efficiently deciding whether TM accepts all inputs in at most $k$ steps
I want to decide if a deterministic TM $A=(Q, \varGamma, \delta, q_s, q_h)$ halts on every input in at most $k$ steps. If the TM $A$ stops after $k$ steps, then the positions $A$ can reach are ...
1
vote
1answer
41 views
Is $L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not accept}\ 010 \} $ Turing recognizeable?
I'm working on the following problem:
Is the following language Turing recognizable (recursively enumerable)
?
$$L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not
> ...
2
votes
1answer
29 views
How To Show That B is Semi-Decidable Given A
I am preparing for my Computational Theory final and ran into this exact problem :
B={ x | there exists a prefix of x that is in A}.
Show that B is semi-decidable. In other words, you need to ...
1
vote
1answer
68 views
I have trouble translating Turing machine language, can you help me break down language notation to English?
My problem is I don't have many issues with creating a Turing machine state table when given a string such as 01101, my issue arises when I am presented with a problem which requires the Turing ...
2
votes
2answers
51 views
How is diagonalization a valid argument for the undecidability of the halting problem?
All proofs for the undecidability of the halting problem seem to be based directly or indirectly on self-reference.
...
0
votes
1answer
38 views
Is finding a single digit of a computation is as hard as finding the computation?
Let $f: \mathbb{N} \rightarrow \mathbb{N}$ a computable function such that computing $f(n)$ takes $\Omega(2^{2^{2^{|n|}}})$ time in worst case terms and such that the languages:
$$\begin{align*} L_1 &...
-2
votes
0answers
33 views
How to build an NTM which should check as efficiently as possible for a 3-dimensional map whether it can be coloured with 42 colours
I need really your help to solve this problem. Can somebody give me a idea how to solve the following problem with NTM?
We are in the year 2500. People also populate the oceans. Since people in the ...
1
vote
1answer
56 views
how can this function be computed in polynomial time in regards to its input?
i am struggling for quite a while with this. trying to understand why the following function can be calculated in polynomial time(in regards to the input length)
defining a function from assignments ...
12
votes
3answers
3k views
Why is the blank symbol not considered part of the input alphabet of a Turing machine?
Definitions of Turing machines are always explicit about the blank symbol not being part of the input alphabet.
I wonder what goes wrong when you would make it part of the input alphabet, because ...
1
vote
1answer
33 views
How precise to be when describing a Turing machine?
I'm kind of new to the theory of computation and I was working on this problem:
We say that a Turing machine $M$ uses $k$ squares of tape for an input string $w$ if and only if there exists a ...
1
vote
1answer
37 views
Randomized Algorithm in $O(d)$ for Solving Unknown Degree $d$ Polynomial Function Using an Erroneous Oracle
Consider the field $GF(p)$, where $p$ is a prime number. If there is a function $f: GF_p \times GF_p \rightarrow GF_p$ which has an unknown degree $d$ polynomial, with $1 < d < p / 4$.
Although ...
4
votes
1answer
61 views
Prove the probability of which a hash function is collision-free
Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
1
vote
0answers
26 views
Theory for programs that are “embedded” in other programs?
We can make the following distinctions: (I will use the term "program" and "machine" as synonyms).
A (baseline) machine. This can be formalized by a Turing machine. It receives an input, and computes ...
0
votes
1answer
57 views
What's the purpose of the non-deterministic Turing machine?
(*) Acronyms
NTDM := non-deterministic Turing machine.
TM := deterministic Turing machine.
(*) Consider the following idea
The NTDM is able to follow, in parallel, all paths of the tree of the ...
1
vote
1answer
26 views
What is the relation between an algorithm and its implementation at the level of code?
Is there any isomorphism or equivalence relation? What strictly bind these two together?
8
votes
2answers
1k views
Does this article imply that Turing-Computability is not the same as “effectively computable”?
First of all, I apologize if this has been asked, but I truly didn't find anything.
I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve.
In my ...
1
vote
2answers
32 views
Describe in words how a NTM can simulate a DTM
I have this assignment
Describe in words how a DTM can simulate a NTM
Describe in wordshow a NTM can simulate a DTM
I'm working on this request and I'm crushing with the comparison.
1-I ...
0
votes
2answers
39 views
Draw a Turing machine that decides the language of all words over the alphabet {a, b} that have an odd number of a’s and an odd number of b’s
Does the question mean draw a Turing machine that takes input with any number of a's and any number of b's (eg. aaabbb, ab, abababab, etc.). The turing machine should only then accept or reject the ...
1
vote
1answer
37 views
Turing machine - compare two words
I have a simple turing machine with single tape.
I need to compare two words <w1>$<w2>$ and write output.
Language is all letters and numbers.
I did ...
2
votes
1answer
599 views
Do regular languages belong to Space(1)?
I was wondering, if we take some regular language, will it be in Space(1)?
For a regular language X, for instance, we can construct an equivalent NFA that matches strings in the regular language.
...
0
votes
1answer
56 views
Computability - The language of all strings of even length
Define a language $L$ as follows:
$$L = \{\langle M \rangle \in \{0, 1\}^* | M\text{ is a TM that halts on all strings of even length} \}$$
I can prove that $L$ is not decidable/recursive, but is it ...
1
vote
1answer
45 views
Undecidability of emptiness of LBA
How is the emptiness of Linear Bound Automata (LBA) i.e $L = \{B \mid L(B) = \emptyset \}$ is undecidable?
28
votes
4answers
4k views
What did Turing mean when saying that “machines cannot give rise to surprises” is due to a fallacy?
I encountered below statement by Alan M. Turing here:
"The view that machines cannot give rise to surprises is due, I
believe, to a fallacy to which philosophers and mathematicians are
...
-2
votes
0answers
90 views
Turing Machine the undecidable language
Consider the undecidable language
$$\mathrm{ALLTM} = \{\langle M\rangle \mid M\text{ is a Turing machine with }L(M) = \Sigma^*\}.$$
Suppose you had an oracle for the halting problem (that is, you have ...
1
vote
1answer
49 views
Why are those very similar languages in a different complexity class?
i am having a real time understand why the following two languages are in two different complexity classes(the first is NP-Hard and the second is in P). tried to look online at various resources and ...
0
votes
0answers
30 views
is this given language in class P? [duplicate]
i was wondering:
is this language in class P?
$NONDISJOINT_{DFA}\:=\:\left\{<A,B> |\:A\:and\:B\:are\:DFAS\:and\:L\left(A\right)\:\cap L\left(b\right)\:\ne \varnothing \right\}$
explanation: a ...
1
vote
1answer
51 views
Proving $L = \{\langle M, w, n \rangle$ : $M$ accepts $w$ within $n$ steps $\}$ is decidable
Show the following problem is decidable: Given $w\in \Sigma^{*}$, $n\in \mathbb{N}$, and a Turing machine $M$, does $M$ on $w$ halt within $n$ steps.
My Thoughts:
I am new to proving results like ...
0
votes
0answers
19 views
Is reduction from A_TM to EQ_TM possible to prove EQ_TM is undecidable?
\begin{align}
EQ_{\mathrm{TM}} &= {\{ \langle M,N\rangle : L(M)=L(N) \}}\\
A_{\mathrm{TM}} &= {\{ \langle M,w\rangle : \textrm{TM $M$ accepts $w$}\}}
\end{align}
I can do it using $E_{\mathrm{...
0
votes
0answers
43 views
Mapping reduction for the useless state problem to prove that its undecidable
I want to give a mapping reduction (many-to-one) using the Empty_TM which accepts nothing, so the accept state is a useless state. This is to show that useless_TM is undecidable.
A state q in a TM M ...
0
votes
1answer
23 views
Understanding the Linear speedup theorem and how strong it is
Let $k \in \mathbb{N} $ and define the language $L = \{ n,m | n^k = m \}$
Consider a (deterministic) TM deciding $L$ then it has to compute $k$'th power which will take $f(|n|+|m|) + h(k)$ time in ...
1
vote
1answer
57 views
How to prove that {<M1, M2> : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?
My idea is to find a turing machine which recognizes this language in $\log N$ space, could anyone give me some clue on how to find such turing machine?
2
votes
1answer
33 views
Construct a decidable set $B$ such that $B \neq A_w$ for any $w \in \Sigma^\star$
I've been stuck on this problem for a while. Any hints would be appreciated!
Let $A \subseteq \Sigma^\star$ be decidable. Given $w \in \Sigma^\star$, define $$A_w = \{x \in \Sigma^\star\:|\: \langle ...
2
votes
1answer
53 views
Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times
I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation").
Can I just use ...
2
votes
1answer
376 views
Some basic questions on halt and move in Turing machines
Im trying to learn about and set up Turing Machines (TMs) the simplest ways using the simplest definite rules. I am using my previous knowledge on simple Cellular Automata to do this. I want to write ...
1
vote
1answer
22 views
Is turing completeness related to recursive enumerable languages?
I recently came across this term "Turing complete" in my study of morphogenesis models. When I looked up, it said that a turing complete machine can simulate a universal turing machine.
When I ...
0
votes
1answer
38 views
Finding a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$
I am trying to find a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$, but I can't seem to find one.
Definitions:
$$\begin{align*}
CF_{TM} &= \left\{ \langle M \rangle \mid \text{$M$ is a ...
1
vote
2answers
261 views
Is the language {<p,n> | p and n are natural numbers and there's no prime number in [p,p+n]} belongs to NP class?
I was wondering if the following language belongs to NP class and if its complimentary belongs to NP class:
\begin{align}
C=\left\{\langle p,n\rangle\mid\right.&\ \left. p \text{ and $n$ are ...
0
votes
1answer
19 views
Does $E_{TM}$ accpets the empty word $\varepsilon$?
Let $L = E_{TM} = \left\{ \left<M \right> | M \text{ is a TM and L(M)} = \emptyset \right\}$.
Does $L$ accepts the empty word $\varepsilon$?
In other words, is $$\varepsilon \in L$$
I'm ...
0
votes
0answers
25 views
Is the proof for the undecidability of $A_{TM}$ still valid if we change certain parts?
i have a question based on a question i saw exists on the site, but with wrong information in it and no answer there, so i am reposting it with valid information(cited wrong from the book).
on page ...
1
vote
1answer
46 views
Turing machine algorithms for $\{0^n1^n\}$ using one and two tapes
I was tasked with finding a way to decide the language $A=\{0^k1^k \mid k\ge 0\}$ in $O(n\log n)$ time, and then to implement it on a deterministic Turing machine with one tape. Additionally, I was ...
0
votes
1answer
28 views
Computability - Can a Turing Machine calculate the input's length?
I have looked for an answer for this question which seems trivial, but I didn't find any.
Can a Turing machine, given a word $w$, calculate the length of the word?
0
votes
0answers
19 views
Turing Machine Language Class Recognition [duplicate]
Would a Turing Machine that cannot move left, but can move right or stay put recognize only regular languages? And how does it compare to a machine the can do the same, but also move left?
2
votes
2answers
94 views
Can a TM recognize whether another TM recognizes a non-empty language?
Let $$L_1 = \{\langle M\rangle\mid M \text{ is a Turing Machine and }L(M)\ne\emptyset\}.$$
Is $L_1$ recognizable? If so, can you give me a pseudo-algorithm?
My attempt:
I wanted to study ...
0
votes
1answer
30 views
Enumerators and recognizers
I got confused by this a bit... the words of any recursively enumerable language $\mathcal{L}_{RE}$ can be enumerated by an enumerator $E$, i.e. there is an effective procedure (using lexicographic ...
0
votes
1answer
98 views
How to prove the set of Turing machines that accept a string and its mirror is undecidable?
I'm trying to prove the undecidability of the following language.
$$L=\{\langle M \rangle\mid M\text{ is a Turing machine and there is a string }w\\\text{ s.t. }M\text{ accepts }w\text{ and }M\text{ ...
1
vote
2answers
52 views
Rice's Theorem - usage on $DFA$ or $LBA$
I have read about Rice's Theorem on Sipser's book, and I think I understand it quite well. I understand that it can be used to show that a language is not decidable.
However I am not sure about one ...
5
votes
3answers
740 views
Fastest algorithm to decide whether a (always halting) TM accepts a general string
Given a TM $M$ that halts on all inputs, and a general string $w$, consider the most trivial algorithm (Call it $A$) to decide whether $M$ accepts $w$:
$A$ simply simulates $M$ on $w$ and answer what ...
