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
1
vote
1answer
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 ...
0
votes
0answers
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?
0
votes
1answer
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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? ...
1
vote
1answer
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)$, ...
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
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 ...
0
votes
2answers
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 ...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
8
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
4
votes
1answer
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 ...
2
votes
0answers
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? ...
-1
votes
2answers
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?
1
vote
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
47 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
27 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:=\{v\mid ...
0
votes
1answer
36 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
48 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
103 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
29 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
33 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
64 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
241 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
28 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
27 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
97 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
61 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
96 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
153 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
206 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
24 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
1answer
52 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
94 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
62 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
21 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
88 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
50 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

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
79 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
33 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 2 3
4
5
38