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
0 votes
0 answers
23 views

Problems in $DTIME(n\log n)$ [closed]

Let $DTIME(t(n))$ denote the complexity class of languages solvable in time $O(t(n))$ by a deteministic Turing machine with one tape. By the result of Kobayashi, we know that $DTIME(o(n\log n))=REG$. ...
  • 101
0 votes
1 answer
30 views

Does a non-deterministic Turingmachine reach every possible result?

I have problems to imagine a non-deterministic Turingmachine. Let's make an example: There is the problem of a Vertexcover. Let $G=(V,E)$ be an undirected graph and $k\geq 0$. The question is whether ...
0 votes
0 answers
20 views

Simulating 2D Turing Machine Page onto a 3 tape turing machine

If I have a 2D Turing machine, how would I go about simulating this onto a multi-tape (k=3) turing machine? I have these math properties that are supposed to help me: Consider a function φ : N2 → N ...
1 vote
1 answer
21 views

Enumerator for $L=\{0^{3^n}| n\ge 0\}$

I need to build an enumerator for $$L=\{0^{3^n}| n\ge 0\}, \Sigma = \{0\}, \Gamma = \{0, x, \sqcup\}$$ that has at most 10 states, including print and halt states. I can ignore the halt state and any ...
0 votes
1 answer
19 views

"Succinct circuit representation" on Turing machines?

The famous PPAD class revolves around the End-Of-The-Line problem. Basically, it states that you are given two polynomial depth circuits, $P$ and $Q$, which act as "possible previous" and &...
0 votes
1 answer
34 views

How does a Turing machine read a transition table as a function?

I am learning about Turing machines. I understand the alphabet set of symbols and the states a machine can be in. However, I do not understand how the transition function works. I come from a maths ...
  • 13
0 votes
2 answers
38 views

Unlimited use subset sum

Given a finite set of integers $Z$ and a number $z$, I would like to check if there exists a subset $A=\left\{ a_1,...,a_{\left| A\right|}\right\}\subseteq{Z}$ and a set of $\left| A\right|$ numbers $...
-1 votes
0 answers
37 views

A turing machine that decides {0^2^n; n>0} with a diffrent approach

we are asked to create this algorithm: ...
0 votes
0 answers
19 views

Reduction between a decidable language $L$ and $\Sigma^*$

Is there a reduction between a decidable language $L$ and $\Sigma^*$?
  • 1
1 vote
1 answer
67 views

Can someone help me understand this Turing Machine?

I am using the book Elements of the Theory of Computation (2nd edition), which has been fine until now. However, I am stuck trying to grasp the Machine Turing conveyed in Example 4.1.8 (pages 189-190)....
  • 13
0 votes
1 answer
30 views

If a language is undecidable, then its complementary language must also be undecidable?

Reference from here If a Language is Non-Recognizable then what about its complement? There exist complementary languages of unrecognizable languages that are recognizable, and there exist ...
  • 195
0 votes
1 answer
22 views

Unrecognizable languages must be undecidable?

A decidable language must be recognizable. Unrecognizable languages must be undecidable? I want to know more about the relation of undecidability and unrecognizability
  • 195
0 votes
1 answer
32 views

If the complementary language of an recognizable language is a non-recognizable language, is the recognizable language a non-decidable language?

The complementary language of a recognizable undecidable language is not recognizable. If the complementary language of an recognizable language is a non-recognizable language, is the recognizable ...
  • 195
0 votes
0 answers
16 views

If $B \in RE$ then $A \in RE$ - Reduction

I know that if there is a Turing Reduction from $A$ to $B$, say $A \le_T B$, and $B \in R$ then $A \in R$. I also know that Turing Reduction is for Decision, and not Recognition. Is it possible to ...
  • 37
0 votes
1 answer
29 views

Prove by reduction that language of TMs accepting only words starting with 101 is undecidable

Before an exam in Computability I go through questions from last year's test. So the question is: $$A= \{ \langle M\rangle x | M \text{ is a TM and accepts } x \}$$ $$ L = \{ \langle M \rangle | M \...
0 votes
0 answers
18 views

Is $L(M_{A_{TM}⤭})$ NP-Hard?

Let $A_{TM}=\{<M,w>|M~is~a~TM~and~M~accepts~w\}$, clearly it is NP-Hard. Let $M_{A_{TM}}$ be the DTM that recognizes $A_{TM}$. Define $M_⤭$ to be the TM obtained from $M$ by swapping the accept ...
  • 37
2 votes
0 answers
25 views

Are $\mathsf{L,NL}$ closed under reverse operation?

for a language $L$ we define $rev\left(L\right)=\left\{ \sigma_{n}\cdot\ldots\cdot\sigma_{1}\mid w=\sigma_{1}\cdot\ldots\cdot\sigma_{n}\in L\right\} $. My question is, are $\mathsf{L,NL}$ closed under ...
1 vote
0 answers
21 views

Reduction from $\mathsf{ALL}_{\mathsf{TM}}$ to it's complement

I'd like to know if there's a reduction $\mathsf{ALL}_{\mathsf{TM}}\leq_{m}\overline{\mathsf{ALL}_{\mathsf{TM}}}$ where of course $\mathsf{ALL}_{\mathsf{TM}}=\left\{ \left\langle M\right\rangle \mid\...
0 votes
0 answers
59 views

If a Turing machine can compute any computable problem how can Turing completeness be achived?

To my knowledge a Turing machine is able to compute anything considered computable. I got the definition of Turing completeness from this answer Explain the difference between Turing Complete and ...
0 votes
0 answers
40 views

Is the set of instances of PCP, which have a solution, semi-decidable?

My idea was that it is because we can construct a TM M' that simulates a TM M that is to find a solution for a PCP instance. M' accepts if M accepts, rejects if M rejects, and doesn't halt if M does ...
0 votes
2 answers
25 views

Is this definition of the class P correct?

The definition of P is given by the union of all DTIME($n^k$) languages for $k >= 0$, where DTIME($n^k$) is the set of languages for which there exist a TM time-bounded by $T(n) = O(n^k)$. However, ...
0 votes
1 answer
30 views

L is a recognizable undecidable language ,M is a Turing machine that recognizes L, does M reject or infinitely loop for s belonging to L-complement?

If $L$ is a decidable language, $M$ is a Turing machine that determines $L$. For $\forall s \in L$, M accepts, and for $\forall s \in \overline{L}$, M rejects However, my question is that If $L$ is a ...
  • 195
1 vote
1 answer
101 views

What is the smallest NFA you can design for {a^n : n =/= 1003}

What is the smallest NFA that could be design for a^n where n!=1003? I have been racking my brain at this for a while but still can't reduce the number of states required from 1004. Here state(1003) ...
  • 13
2 votes
1 answer
24 views

Whether the class of languages with time complexity between polynomial and exponential is an NP language?

We know that the P language class is a polynomial-time solvable language class, and the NP language class can be determined in exponential time. And there exist some languages that can be decided only ...
  • 195
12 votes
3 answers
2k views

Detecting if three Turing Machines halt given a magic oracle that is only used twice

We were given a question in class as follows: You have a "magic oracle" that can decide if a Turing Machine halts. You have three TMs $T_1, T_2, T_3$. Device an algorithm that decides which ...
  • 131
0 votes
0 answers
25 views

How to think about blank symbol when Turing Machine used as a function?

Turing Machines can be used to compute functions. For example f(x)=x-1. 0011 is on the tape. Turing Machine computes for some ...
  • 299
1 vote
1 answer
55 views

Turing Machine, UNLIMITED number of steps left or right on the tape?

In the Church-Turing thesis Wiki page, there are a set of descriptions of the "behavior of a computor—`a human computing agent who proceeds mechanically'". I am content with all of them, ...
  • 604
0 votes
0 answers
31 views

Equivalence for Turing Machines is not Recognizable - Reduction DOUBT

I have a big doubt on this video about $EQ_{TM}$, especially on minute 5:11. Why is he saying that to reduce $ A_{TM}\lt_{m}\overline{EQ_{TM}} $ we need to create a machine M that rejects every input? ...
0 votes
1 answer
42 views

Is a problem in NP if it runs in P time on a NDTM, verifiable in P on a DTM, but solution doesn’t halt on a DTM?

Say there was a decision problem which was solved optimally in polynomial time on a non-deterministic Turing machine, and verifiable in polynomial time on a deterministic TM, but would not halt when ...
0 votes
2 answers
45 views

Decidability of the minimum number of states a Turing Machine needs to accept a language

I'm reading some old notes from a course on Turing Machines and I've bumped into the following question: Is the following language decidable? The language formed by the set of all Turing Machines ...
0 votes
0 answers
31 views

Are all languages determined in exponential time NP languages?

According to the theorem, if $L \in NP$, then $L$ can be determined by a deterministic Turing machine in exponential time. So, are all languages determined in exponential time NP languages?
  • 195
0 votes
1 answer
40 views

Which definition of decidable is correct?

Please note I don't use any of the "verifier" notation, I only concern definitions made with DTM and NTM . Now there are two definitions of decidability: 1. A set (predicate) is decidable (...
  • 3
1 vote
1 answer
32 views

Self-referential systems cannot predict their future behaviour? (reference request)

Seth Lloyd claims in this video that free will stems from our impossibility of determining how a system capable of self-reference will behave in the future (e.g. whether a human being will have chosen ...
  • 111
0 votes
1 answer
41 views

Decidable or Not: Set of all Turing Machines M that on input w uses all states of M

Show that the following language or problem is not recursive: $$ L=\{\langle M,w\rangle\mid \text{computation of TM } M \text{ on input } w \text{ uses all states of } M\} $$ I was trying to prove it ...
-3 votes
1 answer
72 views

Is there an unsound solution to the halting problem that makes the following functions computable?

I'm interested in this functions \begin{align*} g(m) &= \begin{cases} \text{defined} & \text{if turing machine $m$ computes $g$} \\ \text{defined} & \text{if turing machine $...
  • 75
-1 votes
2 answers
71 views

Is P vs NP, a paradox in a hypothetical perspective?

In a hypothetical scenario, where a precise and formal definition does not exist here, and thus expressed with analogies and verbal reasoning for the sake of simplifying the P, NP problem. A(lan) ...
1 vote
1 answer
41 views

Upper limit of instructions of a program for a Turing machine that has been converted from a real programming language

Imagine that I have an algorithm written in C that is of, let's say, 10,000 characters in length. Such a program can be simulated on a turing machine (Wikipedia: Anything a real computer can compute, ...
0 votes
1 answer
45 views

Practicability of enumerating all Turing machines with fewer than $s$ states to find a potential polynomial-time algorithm for subset-sum?

It is known that the $\mathbf{P}\overset{?}{=}\mathbf{NP}$ problem is equivalent to asking whether there exists a polynomial-time Turing machine that decides an $\mathbf{NP}$-complete problem. Let's ...
  • 15
3 votes
1 answer
65 views

A Markov algorithm that does unary multiplication

I am learning Markov algorithms and came across the paper Markov Algorithm by CHEN Yuanmi. I am trying to understand the following example (well, any of the examples in the paper). Example 3: ...
  • 155
1 vote
1 answer
73 views

Is Enumerator a variant of Turing machine that starts with empty string and builds according to the description of language

My understanding is an "Enumerator" is a Turing Machine that: instead of taking an input string, then going through a series of transitions and "halting" or "not halting" ...
0 votes
0 answers
37 views

Is Brainf*ck still Turing Complete without I/O?

I've made an interetsing esolang, and to prove Turing completeness, I've written a small Brainf*ck interpreter in it. However, due to the nature of the language, input is rather hard to handle. The ...
0 votes
0 answers
18 views

A query regarding reading input parameters vs hard-coding for TMs

Consider a Turning Machine $A_0$ that takes two input parameters $(x, y)$ and its (exact not asymtotic) (polynomial) running time is given by $f(|x|, |y|)$ such that $x^c < f(|x|, |y|) < x^{c+1}....
  • 715
0 votes
1 answer
38 views

Try to proof halting problem on a special TM

Hey guys, Got a tricky question here. I need to determine if this TM will ever halt on a empty word "". Seems like it will halt but I can't proof it. Can anyone help?
  • 11
1 vote
0 answers
36 views

FOO = {M | |L(M)| < ∞} What does this turing machine defines?

FOO = {M | The length of language that M accepts is less than infinity} M: a turing machine M such that |L(M)| is less than inifinity: a turing machine such that the length of the language that the ...
  • 11
0 votes
0 answers
24 views

How to prove by reduction this (acceptance?) problem

At school I was assigned this example: Prove by the reduction method that it is undecidable whether for a given Turing machine M with the alphabet {a, b, _} holds aabb ∈ L(M). I think it's acceptance ...
  • 3
0 votes
1 answer
73 views

What is wrong with this proof that shows every language over $\Sigma=\{0, 1\}$ is recognizable?

In the following let $\Sigma=\{0, 1\}$. I'll prove that every language over $\Sigma$ is recognizable. Let $L\subseteq\Sigma^*$. Let $w_1,w_2,\ldots$ be the list of words in $L$. For every $i=1,2,\...
0 votes
1 answer
59 views

Is there a known method for reducing the problem of prime factorization to the problem of determining if a hamiltonian path exists?

I hope this question is not out of place here, but I am currently attempting to implement the problem(a reduction algorithm) stated in the Title. I included the steps I am following as of now and an ...
1 vote
0 answers
35 views

Turing-reducibility for guaranteed decider

The following exercise is taken from Theoretical Computer Science by Atiba. Use Rice's theorem to demonstrate that every decidable language is Turing reducible to some language that is already ...
  • 11
0 votes
1 answer
87 views

Indices of Turing machine on different arity inputs

Let $\Sigma$ be an alphabet, and denote by $\mathrm{ind}(\varphi_M^{(k)})$ the index set (w.r.t some numbering) of the $k$-ary partial computable function $\varphi_M^{(k)} : (\Sigma^*)^k \rightarrow \...
0 votes
2 answers
56 views

Prove that if a language is in co-RE it doesn't mean that it's mapping reducible to another language

Prove/disprove: if $L\in \text{coRE}$ then $L$ is mapping-reducible to $\text{PAL}_{\text{TM}}$, where $\text{PAL}_{\text{TM}} = \{~\langle M,w\rangle ~|~ M ~\text{is a TM and}~w~\text{is a palindrome}...
  • 167

1
2 3 4 5
49