Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
1,707
questions
1
vote
0answers
28 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 ...
-1
votes
0answers
44 views
Prove that for any non empty Σ show that there exists language that are not recursively enumerable
Using diagonalisation method, prove that for any non empty Σ show that there exists language that are not recursively enumerable.
0
votes
1answer
18 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
votes
0answers
19 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\:...
1
vote
1answer
30 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 ...
0
votes
1answer
16 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? ...
1
vote
1answer
46 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
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 ...
1
vote
0answers
25 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 ...
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 ...
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 ...
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 ...
4
votes
0answers
57 views
+50
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
32 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 ...
4
votes
1answer
53 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
66 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
57 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 ...
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
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 ...
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 ...
0
votes
0answers
32 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
98 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
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 $...
1
vote
4answers
138 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 ...
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. ...
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 ...
0
votes
1answer
41 views
Are Turing unrecognizable and undecidable languages, recognized and decided by hyper computation?
Do the hyper computing machines/models that are supposed to be more powerful than Turing machines, capable of recognizing and deciding the languages that are not recognizable/decidable by Turing ...
0
votes
1answer
50 views
Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?
So we know a nondeterministic Turing machine (NTM) is just a theoretical model of computation. They are used in thought experiments to examine the abilities and limitations of computers. Commonly used ...
0
votes
2answers
51 views
When Turing Machine behaves like Finite state automaton
I read following:
Turing Machine with finite (fixed sized) tape is essentially Finite state automaton.
Is this fact correct? My doubt is Turing Machine can go infinite loop even on finite tape if ...
3
votes
1answer
161 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
22 views
How Many Turing machines for n element Alphabet with m states [duplicate]
How many turing machines (NTM and DTM) are there over an n-element alphabet with m states (i.e. len(K) + 1 = m, and len(sigma) = n, where sigma is the set of alphabets in the language and K is the ...
0
votes
0answers
34 views
A Guess Turing Machine that accepts a random Binary number
I'm trying to construct a turing machine that accepts any random binary numbers. From the theory (and partial example) in this video, I understand (correctly?) that this is something that is more ...
2
votes
1answer
65 views
Assume that NP = DTIME(2^sqrt(n)), prove that DTIME(2^sqrt(n)) = DTIME(2^n)
I tried using the padding argument to prove such a thing (as it appeared in Arora's book), but I am not sure how this technique will help me here. I am trying to get to a contradiction to the Time ...
0
votes
1answer
27 views
In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?
Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction ...
1
vote
0answers
20 views
Proving Problems are Undecidable/ Semi decidable? E.g. Halting Problem, Membership Problem? [duplicate]
I am having issues finding similarities in different cases where a problem such as the Halting Problem or the Accept-Λ problem is reduced to the Membership problem to prove that it is semi-decidable ...
0
votes
2answers
38 views
if A is decidable then B is decidable too
Assume that a language A is reducible to language B. The claim is true?
if A is decidable then B is decidable too.
The correct answer is:
This claim is wrong. If A is e.g. the empty language (...
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
18 views
How does one program in a tag system?
I've played with 2-tag systems a bit and read all about tag/lag systems. They're great for experimenting with computation, and obviously useful as intermediaries in various proofs.
My question is: ...
2
votes
1answer
70 views
Is SAT a single language or a union of languages?
I know that a language is in NP if a Turing machine can decide the language of its checking relation $\{\text{boolean formula }\#\text{ truth assignment | truth assignment is correct}\}$ in polynomial ...
1
vote
1answer
25 views
Non-deterministic Turing machine for $L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$
Show if L is in NP, then also L1 is in NP
$$L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$$
I know that if L is in NP, then there exists a NTM $M_L$ than accepts $x$, ...
1
vote
0answers
18 views
Writing a non-deterministic Turing machine
I got an exercise in my college in which ive been asked to write a Non deterministic Turing Machine that accepts words of this form:
Ive manage to find some sort of solution but in a Deterministic ...
1
vote
1answer
25 views
Arbitrary Turing machine run time analysis on the empty word
Consider $L = \{ \langle M,n \rangle : M $ accpets $\epsilon $ in less than $T(n)$ steps$\}$
This language is decidable because a decider can simulate $M$ on $\epsilon$ and accept if it accepts and ...
