# Questions tagged [turing-machines]

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

1,705 questions
Filter by
Sorted by
Tagged with
15 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 ...
26 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 ...
15 views

1k views

### Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?

I was reading the Sipser's book on the Theory of Computation, 3rd edition and came up with a question. "Does showing a problem and its complement are not Turing-decidable means that the language & ...
1k views

### What approaches are most useful when proving uncomputability of a given function?

I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows: Reduction,...
88 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 ...
505 views

### non deterministic space hierarchy

I want to prove the non deterministic space hierarchy theorem. Let $f(n),g(n)\geq\log n$ be space constructible functions such that $f(n)=o(g(n))$, Prove: $$NSPACE(f(n))\subsetneq NSPACE(g(n))$$ I ...
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 ...
41 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 ...
24 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 ...
48 views

### How To Show That B is Semi-Decidable Given A

I am preparing for my Computational Theory final and ran into this exact problem : B={ x | there exists a prefix of x that is in A}. Show that B is semi-decidable. In other words, you need to ...
15 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 ...
36 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 ...
35 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 ...
31 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 ...
40 views

### Turing machine: errata in computable numbers paper?

I'm reading Turing On Computable Number 1936, specifically the section pictured here: Does anyone see errata here? Should the second m-configuration "c" in the table, have the "final m-config" be ...
42 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 ...
21 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? ...
21 views

### Creating language $L_1$ with given parameter

Suppose $G$ is a context-free grammar, the language $L_0⊆\Sigma^*$ is also context-free but not-regular and $\#\not\in \Sigma$. Using $L_{(G)}$, $\#$, $L_0$, and $\Sigma^*$ create language $L_1$ such ...
65 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?
15 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 ...
55 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 ...
99 views

### Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.

...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM. I had this problem on my exam. From my ...
61 views

17 views

### Proof by reduction that the Universal Language is not recursive using the complement of the Diagonalization language

I have the following proof which I don't fully understand. L D/ is the complement of the Diagonalizaton Language. L U is the Universal language. Assume U* is a TM for Lu which always halts. ...