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

learn more… | top users | synonyms

0
votes
1answer
15 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
21 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
46 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?
-4
votes
0answers
39 views

LOOP-EVEN Turing machine: is it decidable? RE? [closed]

Suppose I have the following language: $$\mathrm{LOOP\mbox{-}EVEN} = \{\langle M \rangle \mid M \mbox{ doesn't halt on EVEN input} \}$$ Can someone can give me a hint whether this language or its ...
0
votes
0answers
28 views

Do we have any multitape turing machine that computes log n? [closed]

I dont wanna any turing program for it. I need a plan to how that could be computed in multitape turing machine. Not that it is not [log n]!
-1
votes
1answer
70 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
17 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
39 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 ...
-3
votes
0answers
45 views

Polynomial reduction ,RE and R

Are there any languages L1,L2 such that: L1 is decidable (in R) L2 is Recursively enumerable (in RE) and there is a polynomial reduction between L2 and L1? Thanks.
0
votes
1answer
35 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
27 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
33 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
82 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
24 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 ...
-1
votes
0answers
21 views

Turing machine with rice theorem [duplicate]

How can I prove with Rice Theorem that the following is undecidable: Can a Turing Machine M with constant n >= 1 accept some input of length less than n?
-4
votes
0answers
20 views

decidable languages (Computational Models) [duplicate]

I need to prove whether L is decidable or not: L={ | M is a TM and the union of L(M) and H_TM is in RE} ( H_TM={ | M is a TM that halts on w} ) (<M> is the encoding of a TM) THANKS!
-4
votes
0answers
19 views

Is a union of any TM language and the halting problem language decidable [duplicate]

I need to find if the following language is decidable (in $R$): $L=\{ \langle M \rangle \mid M \text{ is a TM}, L(M)\cup H_{TM}\in RE\}$ Where $H_{TM}$ is of the halting problem. My intuition is ...
0
votes
1answer
68 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
137 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
33 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
130 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
48 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
71 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
77 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
60 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
62 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
58 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
38 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
1answer
61 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
107 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 ...
0
votes
1answer
54 views

Implications of Halting Problem being unsolvable?

I came across a confusing situation when reducing the Halting Problem (HP) to the Blank Tape Accepting Problem (BP). We know that since HP can be reduced to BP, BP is decidable $\implies$ HP is ...
1
vote
1answer
37 views

Prove Undecidability Without Using Rice's Theorem

Show that checking if a TM accepts some input string of length greater than some constant $k$ is undecidable. Here the constant $k$ is publicly known. I tried solving this problem by trying to reduce ...
-1
votes
1answer
53 views

Building an undecidable T-Grammar

I am asked, "Show that these T-Grammars constitute a set of languages that are undecidable. Do this by building a T-Grammar for a Turing machine description. For a starting point you might think about ...
1
vote
1answer
27 views

Turing Machine that always returns a blank tape

Is it possible to construct a Turing Machine such that given any finite input on a tape $s$, it clears the tape in a finite amount of time? I have used such a TM as an intermediate step to show a ...
0
votes
1answer
31 views

Is function application actually a memory manipulation algorithm?

I thought about how in lambda calculus (and many implementations of functional programming languages) function (lambda) application and lambda itself, as a construct, are "primitive things", usually ...
4
votes
1answer
44 views

Is there an example of a recursive language which is not context sensitive?

I have been looking for a prototypical language for recursive languages (decidible) which is no context sensitive without success. For instance $a^*$ is prototypical of regular languages, $a^nb^n$ for ...