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
1answer
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 ...
0
votes
1answer
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 ...
-1
votes
0answers
15 views

algorithm for a #SAT oracle (#SAT algorithm)

i tried to look for an algorithm that decides whether an input x is in #SAT or not. $\#SAT$ is defined, at least in this case to be: $<\phi ,k>=\left\{\phi \:is\:a\:boolean\:formula\:with\:at\:...
2
votes
1answer
80 views

Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times

I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation"). Can I just use ...
1
vote
1answer
38 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)$, ...
0
votes
1answer
15 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? ...
2
votes
1answer
589 views

Is chess game movement TM decidable?

If we have a finite chess board and two figures x and y. Is it possible to get y from x by following chess rules and when white is y and white starts from y placement. Is this decidable? My ...
1
vote
2answers
229 views

Determining the classification of languages

$L_0 = \{ \langle M, w, 0 \rangle \mid \text{$M$ halts on $w$}\}$ $L_1 = \{ \langle M, w, 1 \rangle \mid \text{$M$ does not halt on $w$}\}$ $L = L_0 \cup L_1$ I need to determine where in ...
0
votes
3answers
494 views

Prove or disprove if $L_{1}$ is undecidable and $L_{2}$ is finite language then $L_{1} \cup L_{2}$ is undecidable

I tried to prove by contradiction. $L_{1}$ is undecidable and $L_{2}$ is finite language then $\overline{L_{1}}\cap \overline{L_{2}}$ is decidable. $$L_{1} = \overline{HALT_{TM}} = \big\{ \langle M, ...
2
votes
2answers
4k views

Is the language of TMs that halt on some string recognizable?

I would like to show that the following language is recognizable: $$L:= \{ \langle M \rangle \mid M \text{ is a TM that halts on some string}\}.$$ How do I go about showing that this language is ...
1
vote
4answers
936 views

The language of TMs accepting some word starting with 101

I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language $$ L = \{ \langle M \rangle | \text{$M$ is a TM and $M$ accepts some string $w$ which has ...
1
vote
2answers
83 views

Is $L=\{\langle M \rangle|M$ makes more than 10 steps on some input$\}$ decidable?

I want to show that it satisfies Rice's theorem: (i) $L$ is non-trivial, since $\langle M\rangle \notin L$ where $L(M)=\emptyset$, as $M$ halts/rejects any input string in the first step. (ii) if $L(...
2
votes
2answers
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 & ...
4
votes
4answers
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,...
2
votes
2answers
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 ...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
4
votes
1answer
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 ...
2
votes
0answers
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? ...
-1
votes
0answers
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 ...
-1
votes
2answers
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?
1
vote
0answers
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
2answers
61 views

Why assume Turing machine can compute arbitrary results in Kraft-Chaitin theorem?

The Kraft-Chaitin theorem (aka KC theorem in Downey & Hirschfeldt, Machine Existence Theorem in Nies, or I2 in Chaitin's 1987 book) says, in part, that given a possibly infinite list of strings $...
2
votes
2answers
160 views

The halting problem of Turing machines in view of enumeration of initial tape configurations

As far as I know, presentations of the (general) halting problem (cmp. Wikipedia) are referring explicitly to an ennumeration of (applicable) programs. For the purpose of my questions let's consider ...
0
votes
1answer
41 views

Copy operation in under 9 states?

There is a long row of cells. Each cell contains 0 or 1. A machine is positioned immediately to the right of a series of uninterrupted 1’s followed by an uninterrupted series of 0’s. In the following ...
2
votes
0answers
32 views

Density of non-equivalent programs

Some different programs are in a sense equivalent, for example loop; and loop; write(42); will do the same thing (loop). Given ...
1
vote
5answers
2k views

Whether TM accepts epsilon?

$L = \{ \langle M \rangle \mid \epsilon \in L(M) \}$, where $M$ is any Turing machine. Why is the above problem undecidable? Can't we just check whether the initial state is a final state and say the ...
0
votes
0answers
17 views

Can you apply Rice's Theorem on the following languages? Are they decidable?

Can you apply Rice's Theorem on the following languages? Are they decidable? $$L_1:=\{v\mid v \text{ is the Code of a TM } M_v \text{ and } M_v \text{ has an even number of states.}\}$$ $$L_2:=\...
0
votes
1answer
31 views

What computational model supports arbitrarily sized integers?

I want to do some research, but I don't think it's important the number of bits it takes to represent the integer input and arithmetic on the abstract machine. So what is the model that addresses ...
11
votes
4answers
520 views

Why is the tape not part of the definition of a Turing Machine?

I've wondered why the tape/tapes are not part of the formal definition of a Turing Machine. Consider, for example, the formal definition of a Turing machine on Wikipedia page. The definition, ...
0
votes
0answers
31 views

Union of a decidable language with complement of a recursively enumerable language

So the question wants to prove or disprove that 'a Union of a decidable/recursive(i understand them to be the same) language and the complement of a recursively enumerable language is a recursive/...
3
votes
0answers
97 views

Undecidability of language involving two TMs

I am currently browsing the lecture notes on computability/decidability and I have encountered the following exercise I am unable to solve. Given $M_1$, $M_2$ Turing machines, is it true that for ...
0
votes
0answers
26 views

Is it possible to run more than one Turing Machine emulator using only one processor kernel?

I had this question on computer architecture exam and can't find an answer anywhere. Is it possible to run several Turing Machine emulators at once using only one processor kernel? a) Yes, by ...
1
vote
0answers
28 views

Spaced-bounded Probabilistic Turing Machine Always Halts

For example, in the definition of BPL, we require that the probabilistic Turing machine has to halt for every input and every randomness. What is the reason for us to define them this way? What would ...
1
vote
4answers
137 views

Does infinite length strings lead to uncountable languages?

This answer says: We can have uncountable languages only if we allow words of infinite length. So does that means any (finite / infinite) language or any (finite / infinite) set of languages over ...
3
votes
1answer
159 views

Undecidability of two Turing machines acting the same way on an input

So I need to find a reduction to the (undecidable) problem of deciding if two Turing machines $M_1$ and $M_2$ behave the same way on an input $x$. "Behaving the same way" is defined like this: $M_1$ ...
0
votes
0answers
23 views

Is it decidable whether Turing Machine never scans any tape cell more than once when started with given string

The problem: Is it decidable that the set of pairs $(M,w)$ such that TM $M$, started with input $w$, never scans any tape cell more than once. How can I easily prove above to be decidable. I found ...
0
votes
0answers
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. ...
1
vote
1answer
57 views

How to translate automaton (Turing machine) into the program of high level programming language?

Every program in high level ("industrial") programming language can be expresses as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the Cartesian ...
2
votes
1answer
51 views

PSPACE-completeness of DFA intersection problem

Let some deterministic finite automata be given. There is a problem of determining whether the intersection of these DFA is empty, and I want to show its PSPACE-completeness. It seems to me that I ...

1 2 3 4 5 35