# Questions tagged [turing-machines]

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

1,852 questions
Filter by
Sorted by
Tagged with
26 views

### Prove that a set A is semi-decidable if and only if there is a polynomial time relation R(x,y)

I know if there is a decidable relation R(x,y) for x in A, then A is semi-decidable. But how can I prove the relation is polynomial time? For R(x,y), x is where M is a TM, y is the accepting ...
36 views

### Is there defined limits on, how a Turing Machine can emulate itself / another one?

Meaning for example lower or upper bounds of any kind, possibly concerning time or space complexity?
44 views

### determine if a turing machine halts in less than n step, in less than n step

I would like to know if there is a turing machine which can do the following: take as input a turing machine T and integer n: return true if the turing machine halts before time n and false otherwise ...
65 views

### Show that for every language A, there exists a language B such that not B ≤m A

I have two mapping reducible questions. Show that for every language A, there exists a language B such that not B≤m A. Show that there exists a language C such that for every language A ≤m C and not ...
125 views

### Composition of functions computable in logspace

The bit-graph of $f\colon \{0,1\}^* \rightarrow \{0,1\}^*$ is the language: $\text{BIT}_f := \{\langle x,i \rangle : 1\leq i \leq|f(x)| \text{ and the$i$-th bit of } f(x) \text{ is } 1\}$ It is ...
142 views

### Prove {<M> | TM M on input 3 at some point writes symbol “3” on the third cell of its tape} is recursively enumerable but not recursive

Question: Let $$S = \{\langle M\rangle\mid \text{TM }M\text{ on input 3 at some point writes symbol “3” on the third cell of its tape} \}.$$ Show that $S$ is r.e. (Turing acceptable) but not recursive ...
93 views

### Maximum number of steps a Turing machine makes

Given the Turing machine $M = ( \{q_0, q_1, q_2. q_3,q_4\}, \Sigma= \{a, b, c \}, \Gamma = \{a, b, c, 򪪪\}, \delta, q_0, 򪪪, \{q_4\} )$ where $q_0$ is the start state, $q_4$ the end state and 򪪪 the ...
29 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 ...
34 views

### What are HP and MP in this context?

From Kozen's Automata and Computability, 3ed, lecture 32 p. 328: What are HP and MP in this context? I tried looking around and this text says: How did the halting problem and membership problem ...
19 views

### Reducing vertex cover to minimal vertex cover

What is a quick and a elegant way to reduce vertex cover to minimal vertex cover? Is it possible to use vertex cover as verifier in the algorithm that reduces vertex cover to minimal vertex cover? ...
133 views

### Connection between vertex cover and P=NP

I read about vertex cover and i can't understand why the following occurs. Tried to look and research on the site and in other places but still can't understand it. In an undirected graph $G(V,E)$, ...
13 views

### Proving existence of feedback edge set variant based on deciding if digraph acyclic [duplicate]

NOTE: this is a variation of Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC. here the definition of ACYCLIC is different to make it easier for me to understand a ...
46 views

### Obtaining a graph with no cycles after removing k edges

I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k ...
49 views

### There are functions with f (n) = f (2n) which can't be calculated

I have to proofe that there are functions defined by $f:\mathbb{N} \rightarrow \mathbb{N}, f(n)=f(2n), \forall n\in \mathbb{N}$, which are not-computable. However I'm not really sure about the correct ...
105 views

### Easy-to-describe example of uncomputable function

After teaching my philosophy of cognitive science undegraduates what a Turing machine is, I mentioned that there are functions that can't be computed using a Turing machine. A curious philosophy ...
18 views

### Prove that a set is decidable using time constructible function

I'm preparing an exam of theory of computation and I'm very in trouble with some exercise. Considering a Turing machine $\mu$ of alphabet $A=\{ 0,1 \}$ (we don't know nothing about termination) and a ...
160 views

### Are weakly polynomial time algorithms truly polynomial?

I've been looking through a ton of sources to try and understand the definitions of strongly and weakly polynomial time algorithms. Wikipedia states an algorithm runs in strongly polynomial time if ...
36 views

### Proving inexistence of a PCOMPLETE language in log logarithmic space cannot exist

Hello and thank you for helping me understand the following: I am trying to understand why the following cannot exist: A P-Complete language in regards to a log-logarithmic space. context: Defining ...
42 views

### Reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM}$

How to reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} =\{\langle M,w \rangle: M$ is a Turing machine that accepts $w$}. My try: Construct a ...
75 views

### why does $A≤_p \#SAT$ if $A \in BPP$

hello and thank you for helping me understand the following: I really don't understand this, why if language $A \in BPP$ then $A≤_P\#SAT$? language A is in BPP class, if for a probabilistic turing ...
24 views

### Existence of a P-Complete language with space($\log\log n$) reduction

I have been reading and searching and I still cannot understand if there exists a language as following: Can a language be P-complete with respect to $\mathsf{Space}(\log \log n)$ reductions? ...
79 views

### Why is nondeterminism physically not realizable?

Why it is so hard to make a nondeterministic computer? If such a device is physically realizable then would that be a counterexample to the extended Church-Turing thesis?
27 views

### Meaning of “uniformly computably enumerable in m”

Nies, in Computability and Randomness, p. 6, defines "uniformly computably enumerable": A sequence of sets $(S_e)_{e\in\mathbb{N}}$ such that $\{\langle e,x \rangle : x \in S_e \}$ is c.e. is ...
79 views

### Can we find a Turing machine such that there is no Turing machine to decide whether it halts on $\epsilon$?

The halting problem states that there is no Turing machine that can determine whether an arbitrary Turing machine halts on $\epsilon$. But I try to ask something different, can we find a specific ...