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
3answers
73 views

Are files download times actually unknowable due to the halting problem?

When downloading a file from the internet to our computer we are usually prompted with an estimate of how long it will take for the file to be downloaded. From the Halting Problem, we know that $\...
0
votes
0answers
23 views

Why is it impossible to iterate over all TMs with $n$ states and $k$ symbols that halt after $m$ steps on $\epsilon$?

Define $\{\sigma(n,k,m,i)\}_{i=1}^{l_m}$ an ordered set of all TMs with $n$ states and $k$ symbols that halt after $m$ steps on $\epsilon$ There are $(2kn)^{kn}$ TMs with $n$ states and $k$ symbols, ...
1
vote
1answer
45 views

Why there is no Turing Machine that accepts the Diagonal Language?

Given the diagonal language $$L_d = \{ i : \sigma_i \notin L(M_i) \}$$ Where $M_i$ are all Turing Machines and $\sigma_i$ are all the words, if you put in in a Matrix like this: $$\begin{array} {|c|c|...
0
votes
1answer
39 views

Is the problem that determines whenever the word member $\in$ L(M) decidable or not?

Given a Turing machine M on alphabet {m,e,b,r} we're asked to determine if member $\in$ L(M). You must realize that M is not one specific machine and can be any turing Machine with the same alphabet. ...
1
vote
1answer
77 views

How to conceive a Turing machine that is the intersection of the languages of two Turing machines?

We have $ M = (Q,Σ,Γ,δ,q_0,q_a,q_r) $ and $ M′= (Q′, Σ , Γ′, δ′,q_0′,q_a′,q_r′)$. We want to construct a standard Tm that recognize L(M) ∩ L(M′). How do I go about it? I don't have much more ...
0
votes
2answers
108 views

Decidable questions of undecidable problems

Even if there is no general algorithm to decide if any program will halt, but there could be properties or meta-questions about the programs that is decidable. For example, given program $A$ and a ...
0
votes
1answer
50 views

Oblivious Machines and Input Dependency

So I know the Oblivious Turing Machines head position depends on the size of the input word and a number of steps. Can it be modified in such a way that it's not dependent on the size of the input ...
0
votes
0answers
22 views

Why is there no contradiction when using pumping lemma on a^N b^N a^2N, when k=2?

I have question where it asks: Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2? Here's what I've done, but I do reach a contradiction... u=a^r v=a^s x=a^t b^N a^...
0
votes
1answer
29 views

Determining recursive enumerability of given languages

I came across following problem: $L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$ $L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
1
vote
1answer
215 views

Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps

The detailed question is: Is there a word $w$ on which a TM M $M$ halts after a maximum of $|w|$ (word length) steps? I highly assume, that this problem is not decidable because in the worst case ...
0
votes
1answer
52 views

Provide a polynomial time algorithm that decides whether or not the language recognized by some input DFA consists entirely of palindromes

Everything needed to know is in the question statement. I believe that the DFA has to be acyclic (meaning its language is finite), which can be checked in polynomial time. However, finding all paths ...
15
votes
0answers
234 views

Is the two-color leapfrog problem in P?

My question is whether a specific decision problem is in P or not. It's straightforwardly in NP. The decision problem is a specific case of the general $k$-color leapfrog problem. I can already show ...
4
votes
1answer
815 views

How to simulate a bidirectional TM on a regular one with time factor four?

In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}...
0
votes
0answers
49 views

Is L = {<M>: M accepts a word whose length is at most 200} decidable? [closed]

I have a language consisting of all Turing machines that only accept words "σ" with |σ| ≤ 200 and I need to determine if it is decidable, but it doesn't look like any problem I have solved ...
0
votes
1answer
49 views

On the computable function of a problem that halts

Let's say program $P$ with given input $i$ is found to halt (or doesn’t halt) by a Turing machine. Is it true that the same program $P$ with input $F(i)$ also halts (or not, respectively), where $F$ ...
0
votes
0answers
34 views

Existence of a loop in a Turing machine?

Consider a Turing Machine which (1) reads all its input and (2) accepts inputs arbitrarily large. Can we conclude that there must be a loop in the finite-state control as its inputs get larger?
0
votes
0answers
37 views

examples for languages of natural numbers

I need to find examples for language $L_i$ $i\in[1,3]$ of natural numbers that is: $L_1\in$ $RE \backslash R$ $L_2\in$ $coRE\backslash R$ $L_3\in$ $\overline{ R \cup RE}$ My idea was in any case ...
1
vote
1answer
43 views

Speedup with multi-head Turing Machine

What sort of speedup can a Turing machine with more than one head give vs a one-headed machine (I do not mean multiple tapes, I mean multiple heads operating on the same tape making concurrent edits ...
-1
votes
2answers
237 views

To what extent is an x86 machine equivalent to a Turing Machine?

Is this statement true? Any computation that is decidable within the "C" programming language or the x86 machine language would be decidable on an actual Turing Machine on the basis of the ...
3
votes
1answer
246 views

A variation of the halting problem

Given an infinite set $S \subseteq \mathbb{N}$, define the language: $L_S = \{ \langle M \rangle : M $ is a deterministic TM that does not halt on $\epsilon$, or, $T_M \in S\}$ where $T_M$ is the ...
1
vote
2answers
36 views

Is this set semi-decidable? A set of all <M> that M is a TM halts on all input strings w such that w <= q(M) where q(M) is the number of states in M

$A$ is a set of all $\langle M \rangle$ that $M$ is a TM halting on all input strings $w$ such that $\lvert w \rvert \le q(M)$ where $q(M)$ is the number of states in $M$. Is $A$ semi-decidable? Is a ...
0
votes
3answers
187 views

Is English Turing-complete?

Is English Turing-complete? Intuitively it makes sense that English is Turing complete, since you can talk someone through building a Turing machine. But I also think there might be some operators ...
1
vote
1answer
64 views

How to prove the language of all Turing Machines that accept an undecidable language is undecidable?

I want to prove that $L=\{\langle M \rangle |L(M)\text{ is undecidable}\}$ is undecidable I am not sure about this. This is my try : Suppose L is decidable. Let $E$ be the decider from $L$. Let $A$ be ...
2
votes
3answers
245 views

Is a Turing machine too strong of a model to model physical computation?

I've heard many times people debate the possibility of a real world computation that is impossible for a Turing machine, especially in the context of a human mind. Implying that the Church-Turing ...
0
votes
0answers
36 views

Is a or free SAT formula NP complete?

Let $L$ be the languague which contains all satisfiable formulas which do not have the or symbol $\lor $. Or more precise $$L=\{\phi | \phi \text{ is a satisfable formula which is only using the ...
0
votes
0answers
31 views

$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$

I want to prove that $$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$$. Does anyone have a Idea how to solve this ?
1
vote
1answer
41 views

Rice's Theorem for Turing machine with fixed output

So I was supposed to prove with the help of Rice's Theorem whether the language: $L_{5} = \{w \in \{0,1\}^{*}|\forall x \in \{0,1\}^{*}, M_{w}(w) =x\}$ is decidable. First of all: I don't understand, ...
0
votes
0answers
44 views

If $A\in RE $ then $f(A)\in RE$

Let $A\in RE$, and define$f(A) = \{y |\ y= f(x),\ x\in A\}$ for some computable function $f$. Then $f(A)\in RE$. I can't figure out why this is true. Since $f$ is computable there is a Turing machine ...
1
vote
1answer
23 views

Relations between deciding languages and computing functions in advice machines

I'm trying to understand implications of translating between functions and languages for P/Poly complexity. I'm not sure whether the following all makes sense. Giving it my best shot given my current ...
3
votes
2answers
38 views

Intuition for Church-Turing thesis for Turing machines

I can very clearly see "why" mu-recursion is a universal model of computation, i.e. why the Church-Turing thesis -- that any physically computable algorithm can be executed with mu-recursion ...
0
votes
2answers
429 views

Which is the best approach to solve Turing machines exercises?

I've this exercise of which I'm not very sure about my solution. Exercise: Define the transition table about a Turing Machine that accepts words on the {a, b} alphabet where each a is followed ...
0
votes
0answers
28 views

Decidability for $ \exists w´, w´´\in L:$ so that |w´´| - |w´| is prime

I tried to decide wheter the given Language $ L = \{ \langle M \rangle | M \space is \space TM \space and \space \exists \space w´,w´´\in L(M):|w´´|-|w´| \space is \space prime \} $ is recursive or ...
-1
votes
1answer
59 views

How to design a formal grammar to convert EBNF description to a list of CFG production rules

I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm. Can CFG production rules is generated from an EBNF description by a rewrite ...
0
votes
1answer
25 views

Confusion about definition of languages accepted by Turing Machine, very basic question

I'm studying for an upcoming exam and my book gives the following definition: Let $M$ be a Turing machine, then the accepted language $T(M)$ of $M$ is defined as $T(M) = \{x \in \Sigma^* \mid z_0 x \...
0
votes
1answer
69 views

Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

Consider the function $f$ that maps strings over $\{a, b, c\}$ to strings over $\{0, 1\}$ by replacing each $a$ by 0, each $b$ by 0, and each $c$ by 1. For example $f(cabbc) = 10001$. The function $f$ ...
1
vote
1answer
37 views

Is {<M>: L(M) ∈ NP} ∈ NP?

Intuitively I think the answer is no since I don't think every certificate can be checked in polynomial time but I don't know how to give a formal proof. Is the statement true? Why or why not?
2
votes
0answers
32 views

Is the discrepancy in Turing's representation of complete configurations intentional?

On page 235 of Turing's 1936 paper, in the figure marked (C), the illustration appears not to match the description. The description states that space has been made on the left of the scanned symbol, ...
0
votes
1answer
34 views

What undecidable language $B$ is reducible to its complement?

I encountered a problem which asks to give an example of an undecidable language $B$ such that $B \leq_m \overline{B}$... However, I could find it hard to construct an example ... my difficulty is ...
0
votes
1answer
22 views

How to define a TM which writes all the tape alphabet, when the number of states is independent of the tape alphabet size?

Given tape alphabet $\Gamma = \{\gamma_1 ,...,\gamma_n\}$ I wish to define a single-taped TM which given the input $\varepsilon$ writes the string $\gamma_1 \gamma_2...\gamma_n$ on the tape, and the ...
0
votes
1answer
28 views

Is the languague L={<M>, M accepts a finite amount of words} decdidable?

Is $L=\{<M> | L(M) \ is \ finite\} $ decidable ? M is a TM. I think its relative simple to proof with the theorem of rice. But I am interested in a solution which does not use the Rice theorem. ...
0
votes
0answers
35 views

What is a make sense (meaningful) example of language that an unrestricted grammar could generate?

I have learned that: Unrestricted grammar is used to define (or describe) a formal language. Unrestricted grammar is used to define recursively enumerable set [https://en.wikipedia.org/wiki/...
0
votes
1answer
33 views

simple question about epsilon and estimation turing machines

i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple ...
1
vote
1answer
43 views

Why is this language Turing recognizable and not not-Turing recognizable

I read that the following language is r.e. but not not-Turing recognizable $L$: On input $M$ (where $M$ is a Turing Machine), $M$ accepts at least 20 inputs I am not sure why it is not not-Turing ...
1
vote
1answer
47 views

decider for a question not clear

This question was asked and answered but I cannot understand the solution. Why is it sufficient to test all strings of |Q| + 1 length? Why should special state q be found? the original question: ...
0
votes
1answer
196 views

Proving decidability of language

Prove or disprove: The following language $L$ is decidable: $\{ \langle M, t\rangle: M \text{ is a Turing machine and } \forall w \in \{0,1\}^* [M(w) \text{ halts in at most } t \text{ steps} ]\}$ ...
9
votes
2answers
153 views

Is the leapfrog automata problem in P?

My question is whether a specific decision problem—finding a computation path through a "leapfrog automaton"—is in P or not. It's straightforwardly in NP, and it resembles the hamiltonian ...
0
votes
1answer
21 views

Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$?

I was trying to solve a problem with a mapping reduction from $A_{TM}$ to $INFINITE_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A_{TM} \leq_M ALL_{TM}$. ...
0
votes
1answer
25 views

Out-Degree of a Configuration Graph

In Chapter 4 in Computational Complexity by Arora and Barak it states, regarding the configuration graph of a Turing Machine, that If M is deterministic, then the graph has out-degree one, and if M ...
0
votes
1answer
55 views

Do all languages in $P$ have polynomial proofs that they are in $P$?

A proof for a language $L$ belonging to a complexity class $C$ can be framed as there existing a verifier $V$ that accepts this proof as the first part of their input and the language as the second. ...
1
vote
1answer
27 views

Prove a language is not recursive enumerable

I need to prove $: L=\left\{<M>| M \text { is a } T M \text { and } L(M)=L\left((01)^{*}\right)\right\} \notin R e$ at first observation it looks like it's immediate from Rice's extended Thm, ...

1
2 3 4 5
38