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

learn more… | top users | synonyms

0
votes
0answers
26 views

A question on the graph induced by the transition function of a deterministic Turing machine

Let $M$ be a deterministic Turing machine with totally defined transition function $\delta$ and working alphabet $\Gamma$. Let $Q$ denote the statespace of $M$'s finite control. Let $G_M$ be the ...
1
vote
1answer
18 views

Timely lower bounded Turing machines

Let M be a deterministic Turing machine wich has the properties: 1) $\forall x,y \in \Sigma^* : t_M(xy) \ge t_M(x) + t_M(y)$ 2) $\forall a \in \Sigma: t_M(a) \ge 1$ (Also 2) should be obvious for ...
5
votes
1answer
77 views

Why do we reject turing machines that use space less than the log of the length of the input?

In Computational complexity: Modern Approach by Arora and Barak, it's mentioned that We will require however that $S(n)> \log n$ since the work tape has length $n$, and we would like the ...
1
vote
1answer
33 views

Is this language semi-decidable?

Let $M_w$ be the DTM encoded by the binary string $w$ and let $$L=\{w\#x\,|\,\text{all states are reached when running }M_w\text{ on }x\}.$$ I've already proved that this language is undecidable (the ...
3
votes
1answer
44 views

Is unrestricted grammar equivalent to deterministic Turing machine?

Suppose we have unrestricted grammar but with restrictions on how rules are applied: we take first rule, search in string left to right and apply it as we go. If no match found, we proceed with second ...
0
votes
0answers
25 views

Time complexity of fixed point program

Suppose $\mathcal{M}_f$ is a Turing machine that computes the total function $f(x)$ in time $T_{\mathcal{M}_f}(|x|)$. Also suppose $M_H$ is a Turing machine that computes the total function $H(n,x)=\...
6
votes
1answer
27 views

Showing strong connectivity is in DSPACE((logn)^2)

$ST-CONN = \text{{(G,s,t) | G is directed graph, there's path from s to t}}$ I've learned the following deterministic algorithm to solve the problem in $log^2n$ space: $\psi(G,s,t,k) :$ $\hspace{1cm}\...
1
vote
1answer
61 views

TM that accepts all strings is recognizable or not?

Lets say we have the following language $L = \{\text{$M$ is a TM such that $M$ accepts all strings}\}$, is this recognizable or not? I have a feeling it is unrecognizable, if this statement is correct ...
2
votes
0answers
14 views

Uses of unary or sparse languages in other models

In the turing model we have the statements that if there is an unary or sparse language that is NP complete then P=NP and if there is a Turing reduction from an NP complete problem to an unary or ...
0
votes
1answer
60 views

How do I prove that a Turing Machine that accepts a string w in an even number of steps is not decidable?

Let a language A = {(M,w) : M is a TM and w is a string such that w is accepted by M in an even number of steps}. How can I prove that this is undecidable? I have considered trying to build the ATM ...
1
vote
1answer
34 views

Example of a simple recognizable language, whose complement is not recognizable

Can any one provide me with a simple language that is recognizable, but that it's complement is not? I have read that recognizable languages may have this property but I am yet to find an example to ...
1
vote
2answers
108 views

Is it possible to create a chatbot that doesn't fall into an infinite loop under some restrictions?

Consider a chatbot that runs on a turing machine. It has some restrictions: It must talk to itself 1 sentence at a time. It is forced to use English words to reply. (so only around say 80 k ...
-2
votes
2answers
40 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 ...
0
votes
1answer
27 views

Can you do operations on the halt state of a turing machine?

As the title says, can operations be performed by a turing machine after it has transitioned to the halt state like shown in the following image.
0
votes
1answer
53 views

Turing Completeness of System Which Randomly Fails to Complete Calculations

If one were to create a variant of a turing complete language which upon completing a calculation randomly changes the answer by one, would it be Turing complete? For example, say I had a Python ...
2
votes
0answers
25 views

Oblivious Universal Turing Machine in O(T log(T)) time

I'm currently reading Computational Complexity: A Modern Approach. In this book, they give a proof of a universal Turing machine $U$ such that if $M(x)$ runs in $T$ steps, then $U(\lfloor M \rfloor, x)...
1
vote
2answers
50 views

Efficient algorithms for checking non-emptiness of the language of a Turing machine

I know that language non-emptiness is TM recognizable, and one can perform a BFS to find an input string that TM accepts, if there is any. But, what is the most efficient algorithm for that?
-1
votes
1answer
74 views

Turing Machine and decidability

so the thing is that i have to prove that if the language $L ⊆ \Sigma^*$ is decidable then both languages are also decidable. $$P_1(L) = \{w ∈ Σ\mid \text{ For every prefix v of w, we have }v ∈ L\},$$ ...
3
votes
1answer
18 views

How to handle an undefined case with µ-recursive functions?

How to construct my proof and generally what should I aim to get when showing a function is $\mu$-recursive? Should I transform it in some of the basic functions using the given operators? For ...
1
vote
2answers
40 views

Oracle Relations Between Complexity Classes

I'm trying to get a better handle on oracle separations between complexity classes but I keep running up against some (seemingly) silly issues that make me think that I'm fundamentally ...
0
votes
1answer
44 views

Is it always possible to convert a k-tape Turing machine to a single-tape one without increasing its running time complexity exponentially?

I am studying the past exam paper of course Theory of Computation. I know it is always possible to convert a k-tape Turing machine to a single-tape one, but how will the running time complexity be ...
0
votes
0answers
30 views

Are there any RE-complete languages w.r.t. polynomial reduction?

I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L $, meaning a polynomial-time reduction. I've tried to use $L=A_{TM}$ (the accepting problem), but got ...
1
vote
1answer
18 views

Example Turing Machine for a time-constructible function

I am currently reading "Computation Complexity: A Modern Approach" by Arora and Barak and have a question about time-constructible functions. In particular, I can't construct a turing machine for a ...
0
votes
1answer
37 views

Relating memory complexity and decidablity

Given a language $L_u$, about which we know that there exists a non-deterministic turing machine which accepts it (as in, implying $L_u \in RE$) with memory complexity of $c^{p(n)}$, where $c$ is a ...
5
votes
2answers
84 views

How do nondeterministic Turing machines compute general function problems?

(Hope this hasn't been asked before, but I didn't find anything.) In my understanding, nondeterminism applies to decision problems only, due to the requirement of the existence of an accepting path. ...
0
votes
0answers
23 views

Turing machine that computes w#w when the input is w? [duplicate]

Can someone please describe how such a machine would work? My approach: Move the head full on the left. Scan the input to verify no # symbol exists. Add # at the end of input. Move the head full on ...
1
vote
1answer
27 views

Turing Machine remembering copied symbols

So, I now that any multiple-tape TM can be in theory turned into one-tape TM. However, it is too easy to copy lets say binary number from one tape to another. Thats why I thought about putting a ...
0
votes
1answer
70 views

Classify the set of all TMs whose languages from the accepting problem

Let $$L = \{ \langle M \rangle \mid M \text{ is a Turing machine so } A_{TM} \leq_m L(M) \}$$ The question is whether $L$ is in $\mathcal{R}, \mathcal{RE}, co-\mathcal{RE}$ or in $\overline{\mathcal{...
0
votes
2answers
142 views

Decidability of the TM's computing a none empty subset of total functions

I have this HW problem: Let $F$ be the set of computable total functions, and let $\emptyset\subsetneq S\subseteq F$. Denote $$L_S=\{ \langle M \rangle | M \text{ is a TM that computes a function ...
1
vote
0answers
34 views

Canonical definition of suitable encoding

I've had several Computer Science courses and, from what I recall, I've never been given a rigorous definition of suitable encoding. Definitions always tend to use effective method or some synonym to ...
0
votes
1answer
47 views

How to prove intersection between languages L1 (belongs to NP) and L2 (belongs to P) actually belongs to NP?

I have to prove that if L <=p L1 intersection L2, where L1 and L2 are described as above, L belongs to NP. I thought about the definitions of P and NP and built a DTM D that decides L2 and a NTM N ...
4
votes
1answer
133 views

Prove that there is no computable enumeration of all decidable languages

The question: Let $L_1,L_2,...$ be an enumeration of $\mathcal{R}$ and define $A_i = \{\langle M\rangle \ | \ L(M) = L_i\}$. Let $L$ be a language in $\mathcal{RE}$ such that $L \subset \{\langle ...
1
vote
0answers
49 views

Is $f$ which returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ computable?

The question itself: Let $f:\mathbb{N}\to\Sigma^\star$ be such that $f(n)$ returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ (which is the complement of the language of TMs which accept $\...
-4
votes
1answer
72 views

Order classic notions of computability by power

I need some help with a question. I'm currently studying for an exam and I could therefore use some help with this following question: Order the following formalisms (but one) according to their ...
2
votes
1answer
79 views

Turing Machine with additional finite memory of size $n$

The question itself: Let us define a generalization of Turing Machines to include a finite memory of >size $n$. We denote such a Turing Machine formally as: $M_{mem} = (Q, Σ, γ, δ_{...
3
votes
1answer
62 views

Undecidability of REGULAR_TM (Detail within Proof)

I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book. The example shows how $REGULAR_{TM}$, defined as the ...
3
votes
2answers
64 views

Given a r.e. (recursively enumerable) language, L, how many Turing machines semi-decide L?

$L\subseteq \{0,1\}^*$ Since the language is r.e. there is definitely at least one Turing Machine that semi-decides the language. I'm thinking that if you have one Turing Machine that semi-decides ...
1
vote
1answer
64 views

Pseudocode algorithm to check encoding of Turing machine

My question goes like this: Write an algorithm (in pseudocode) that on input $w$, checks that $w$ encodes a valid Turing machine $\langle M\rangle$. e.g, you need to validate that the structure is ...
6
votes
1answer
3k views

Are all languages in P?

Are all languages in $\mathbf{P}$? Note: The definitions of all the symbols and functions here follow the document [1]. The following is my attempt to answer the question. Assume that we design a ...
0
votes
1answer
12 views

Transition and configuration of Turing machine

In my lecture I have examples about 0 -> R (which means if it's 0, move Right) or 0 -> x, R (replace 0 with x and move Right) but I don't quite understand about the 0, 0 -> R expression. What is the ...
0
votes
2answers
40 views

Proof for TM accepting any PDA-language

How do you suggest I go about proving this: Give a short, basic outline of a proof that Turing machines can accept all languages accepted by PDAs. You are allowed to use a non-standard Turing machine....
0
votes
2answers
47 views

What happens after the accept state if there are still letters in the string in a Turing machine?

Lets say there is a turing machine $M$ where \begin{align*} M &= (Q, \Sigma, \Gamma, \delta, q_1, q_{accept}, q_{reject}) \\ Q &= \{q_1, q_2, q_3, q_{accept}, q_{reject} \} \\ Σ &= \{0, 1\}...
2
votes
2answers
61 views

Language of TMs such that one state is visited most often

To be safe, let me start this question by giving the definition of a TM I will be using: A TM is some $M = (Q, \Sigma, \Gamma, q_0, \delta, q_F)$, where $Q$ is the finite state set, $\Sigma \subset \...
0
votes
0answers
43 views

Calculating Big-O

I was asked to find the O-complexity of the algorithm accepting the language {0^(2^k) | k>=0} meaning the length of a string in the language will be of a power of two. (using a turing machine) $ The ...
1
vote
0answers
50 views

Language of Turing machines that never visit some given state

Can someone help me to determine and prove if the following language is decidable or not? I tried to think on some reductions but I can't figure it out... $$A=\{\langle M\rangle|\text{$M$ is $TM$ ...
2
votes
0answers
74 views

Understanding Levin's Universal Search

I am having troubles understanding Levin's universal search method. In Scholarpedia, http://www.scholarpedia.org/article/Universal_search, it is claimed that “If there exists a program $p$, of length $...
3
votes
1answer
117 views

What is the fastest addition algorithm on a turing machine?

What's the asymptotic running time of the fastest algorithm for adding two $n$-digit decimal numbers on a Turing machine? To specify, the input is of the form $a_1+a_2$ where $a_1$ and $a_2$ are ...
0
votes
0answers
20 views

On Karp reduction

Assume a complete problem for a class $\mathcal C$ is in $P/poly$ and at each $n$ assume that the advice string is $s_n$ of length $n^c$ for a fixed $c>0$. Assume that $SAT$ of $n$ length input ...
0
votes
0answers
47 views

Why is $coNP\subseteq NP/O(1)$ and $coNP\subseteq NP/O(\log n)$ not same as $coNP=NP$?

If $NP\subseteq P/log\implies P=NP$ why does $coNP\subseteq NP/O(1)$ or $coNP\subseteq NP/O(\log n)$ not implies $coNP=NP$?
3
votes
1answer
20 views

How to identify strongly confluent cellular automatas?

Lets represent a class of cellular automata as a finite, unidimensional bit array state : [Bit], plus a rewrite rule ...