Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
1,567
questions
0
votes
1answer
10 views
A condition for $\emptyset \neq S\subset RE$ under which $L_S \notin RE$
I read some computation theory lecture notes and after citing and proving the proposition: $\emptyset \in S \Rightarrow L_S = \{\langle M \rangle : L(M)\in S\} \notin RE$ it says that $\emptyset\in S$ ...
1
vote
0answers
15 views
Deterministic Time Hierachy Proof by Arora and Barak: Question about time to simulate Turing Machine $M$ that decides separating language
In the book "Computational Complexity: A modern approach", Arora and Barak proof the statement that $DTIME(n) \subsetneq DTIME(n^{1.5})$ by constructing a separating language $L \in DTIME(n^{1.5})$ ...
2
votes
0answers
18 views
On teaching Kolmogorov complexity with Python and the complexity of composed strings
The setting of this question is a bit long-winded, but please bear with me.
This fall I will be lecturing a course on mathematical information theory, and on a few lectures we will be discussing ...
0
votes
0answers
16 views
Why are CFL not closed under set difference, and complementation? [duplicate]
I was wondering why CFL are not closed under set difference, and complementation can anyone explain? I tried searching, but no luck.
0
votes
0answers
14 views
How to compute within a Multi tape turing machine [a binary substraction between 2 numbers and result on 3rd tape]? [closed]
I'm trying to compute a Multi-tape turing machine (of 3 tapes) that follows this statement.
"A binary subtraction operation between the first and second tape printing the result on the third tape"
I'...
1
vote
1answer
39 views
What is an example of a Turing-recognizable infinite word, which is not Turing-decidable?
I am confused about Turing Machines that are able to decide languages that contain infinite words.
Are languages with an infinite amount of only finite strings always decidable?
How can a Turing ...
0
votes
1answer
21 views
Proving whether an input sequence is in a given RE language
I've learned this a few years ago that this is impossible unless one simply 'executes' (in a modern computing sense) the input with the language rules, but I have some problems in just using this ...
2
votes
0answers
38 views
How strong is an oracle that avoid don't-halt
Consider such an oracle:
Given a turing machine[1], return the halting state it falls on, or arbitary result(but don't stuck in) if the TM doesn't halt.
How strong is a TM with the oracle?
Can the ...
1
vote
1answer
23 views
How to detect infinite loop exist in linear bounded automata (LBA)?
The following theorem from Michael Sipser's book "Introduction to the Theory of Computation" states:
$A_{\textrm{LBA}}= \{ \langle M, w \rangle \mid \text{$M$ is an LBA that accepts string $w$} \}$....
1
vote
1answer
17 views
Differences between ALLTM and INF
The definitions of ALLTM and INF are as follows:
$$\mathrm{ALLTM} = \{ \langle M \rangle \mid \text{ TM $M$ such that $L(M) = \Sigma^*$} \}. $$
$$\mathrm{INF} = \{ \langle M \rangle \mid \text{...
6
votes
1answer
42 views
What publication first introduced the concept of a non-deterministic Turing machine?
What publication first introduced the concept of a non-deterministic Turing machine?
Turing did not define the concept in his 1936 paper.
0
votes
1answer
16 views
What is the difference between a collection of Turing Machines and a family of Circuits?
Given a Collection of Turing Machines $T_1, T_2, T_3,...T_n$ where $T_1$ denotes that the Turing machine can only take in an input of size 1. Is there any difference in computational power to a family ...
2
votes
1answer
19 views
Simulating multi-tape turing machines by single-tape TM
In "Computational Complexity: A modern approach", Arora and Barak proof the following Claim:
Define a single-tape Turing machine to be a TM that has only one read-write tape, that is used a input, ...
3
votes
1answer
136 views
Can an alphabet for a Turing machine contain subsets of other alphabets?
For example;
Is {0,1,{a,b,c},d,e} a valid alphabet to form a language over and is it usable in any context?
-1
votes
2answers
140 views
The Halting problem proof is wrong?
First, let's see the pseudocode proof of halting problem:
P(x) =
run H(x, x)
if H(x, x) answers "yes"
loop forever
else
halt
Then we have a ...
-1
votes
1answer
103 views
Is the infinite program Turing-recognizable/decidable?
Imagine we have a program which does an infinite loop: while(true){loop}
We run the program on a linux machine(assume the compilation is ok), then this linux ...
4
votes
1answer
84 views
A push-down automaton with two stacks which is equivalent to a linear-bounded automaton
It is known that a PDA with two stacks is equivalent to a TM.
On the other hand a PDA with one stack is capable to recognise only context-free languages.
Hence there is a kind of a gap between the ...
1
vote
1answer
41 views
How can the VC-dimension of Turing machine be finite?
The VC-dimension of a hypothesis class $\mathcal{H}$ is defined to be the size of the maximal set $C$ such that $\mathcal{H}$ cannot shutter. This paper shows that the VC-dimension of the set of all ...
0
votes
0answers
33 views
Is the language $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$ decidable?
I have stumbled upon this language: $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$. At first, it looked like an undecidable problem, but I have failed to prove it, and now ...
3
votes
1answer
71 views
Which languages, decided by a turing machine are decidable?
How do I decide if a language is decidable and/or semi-decidable?
I have theses languages:
a) { < M > | L(M) ⊆ 0*}
b) { < M > | L(M) contains at least one word of even length}
c) {...
-1
votes
1answer
38 views
If the human brain is a Turing machine then how is it able to ascertain that certain problems are undecidable? [closed]
I recently read about the idea that the human brain might be a Turing machine (or Turing complete). If that is true then how is the brain able to reason that a certain problem is undecidable for e.g. ...
1
vote
3answers
143 views
Can undecidability theorems be detected by a machine? [closed]
this question was originally written in mathoverflow, but a comment recommended me to rewrite it as a CS question.
This is not a mathematically formalized question. I'm sorry for that but think it's ...
1
vote
0answers
59 views
Encoding any turing machine to one with 2 symbols
This is a repost from https://stackoverflow.com/questions/56990710/encoding-any-turing-machine-to-one-with-2-symbols since it was brought to my attention that the question would be better suited to ...
0
votes
1answer
41 views
prove that there is a complete language in $L \cup \{A_{TM}\}$
$A_{TM} = \{\langle M,w\rangle\mid w\in L(M)\}$
$L$ = complexity class containing decision problems that can be solved by a deterministic Turing machine using logarithmic space
Given the language $L ...
1
vote
2answers
85 views
Turing machine where the next step is determined by the state and the symbols up to the read/write head
Given a modified type of turning machine where
$\delta = Q\times \Gamma^* \implies Q\times \Gamma \times \{L,R\}$
where the next step of the machine is determined by the current state and whatever ...
2
votes
1answer
63 views
Are Context Sensitive Grammar with Polynomial Complexity Time?
Accordingly, to the question Chomsky Hierarchy and P vs NP, Context-Sensitive Grammars are on Linear Space.
Assuming a Deterministic Parser is the one which can parse unambiguous grammars in ...
1
vote
1answer
46 views
How can I prove the languages of incompressible words is undecidable?
I have hard time understanding the proof by contradiction for the claim "$L=\{x : K(x) \ge |x| \}$" is undecidable ".
The proof is as follows :
M' = " On input $n$
Enumerate over all $n$-...
0
votes
1answer
27 views
Language which is recursively enumerable but not recursive [duplicate]
Can someone provide me with some examples of languages which are recursively enumerable but are not recursive. I know that there exist some languages which are not Recursive but recursively enumerable ...
2
votes
1answer
23 views
Turing Machine equivalence in MinTM proof
The proof with contradiction that $MIN_{\mathrm{TM}}$ is not Turing-recognizable from Michael Sipser's textbook "Introduction to the Theory of Computation" (Theorem 6.7) is as follows:
$C=$ "On ...
1
vote
2answers
42 views
L(M)=L where M is a TM that can move right or stay, so L is decidable
Suppose that L(M)=L where M is a one tape TM that can move right or stay.
I need to Show that L is decidable.
I thought of reducing a PDA to this TM, since moving to the right is equivalent to ...
2
votes
1answer
25 views
Böhm-Jacopini theorem
I had a discussion with a friend developer and teacher. He told me about the Structured program theorem arguing that this theorem is one of the most important to know about. However, I have never ...
0
votes
1answer
22 views
What is the intuition behind the relationship between space and time for an algorithm? [duplicate]
I believe I have heard that you can never have more space than the algorithms running time. I could be wrong, maybe other way around. What is the intuition behind this?
1
vote
1answer
31 views
What is a trivial language?
I have heard the quote "L is a trivial language" What does this mean and how do we relate this to Turing machines and complexity theory?
2
votes
1answer
54 views
Turing Machines proof notations
In context of "Computability", I have went over some proofs for Recursion
Theorem using Turing Machine description. A TM $M$ stands for a single tape
Turing machine and $\langle M \rangle$ is the ...
0
votes
1answer
68 views
Prove completeness of a language with Turing Machine
I'm trying to prove that a simple computer language is Turing Complete. For that, I did some researches about Turing Machine and I found (if I understand correctly), that we can prove that by simuling ...
0
votes
1answer
122 views
What does it mean for a TM to solve a problem?
When we say a TM solves a problem, what does this mean?
1
vote
1answer
17 views
What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements?
What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements?
I.e. What is the link between the language and the algorithm
0
votes
1answer
13 views
Turing Machines: What is the difference between the language realised by a problem and the language for which the TM accepts on?
A decision problem A corresponds to the language L1 if L1 contains all of the solutions to A.
A language L2 is defined as the set of all inputs to which a TM halts and accepts.
What is the link ...
1
vote
1answer
18 views
Can a Turing Machine be defined over many languages?
What does it mean, if possible, for a Turing machine to be defined over many languages?
5
votes
2answers
2k views
Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting?
I have seen a remark saying "we usually say that a turing machine accepts/rejects a string, while it decides a language" Is this correct?
As I have also seen places where we mention a Turing machine "...
2
votes
1answer
42 views
D has polynomial verifyer, the certificate for any word $w \in D$ is at most O(|log w|) space. Prove $D \in P$
Given that a language D has a polynomial verifier,
and given that for every word $w \in D$, the length of the certificate $c$ is $O(\log|w|)$ space.
How can I prove that $D\in P$ ?
My idea was to ...
1
vote
2answers
41 views
Is a language whose Turing Machine doesn't halt for some positive cases but for others does not recursive?
Say language $L$ is recursively enumerable, but not recursive.
Say $a$ and $b$ are symbols of the alphabet and $w$ a word.
Say we have the following language:
$L' = \{ aw | w \in L \} \cup \{ bw | w \...
3
votes
1answer
36 views
How to prove the union of languages recognized by a set of turing-recognizable Turing machines is also turing-recognizable?
Let $G = \{\langle M_1\rangle, \langle M_2\rangle, \langle M_3\rangle,\cdots\}$ be an infinite turing recognizable language, whose members are descriptions of turing machines.
How can one prove that ...
1
vote
2answers
44 views
Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$?
In the proof of Savitch's theorem from the 3rd edition of Sipser's Intro to Theory of Computation, Sipser claims that the maximum time that an $ f(n) $ space nondeterministic Turing machine that halts ...
0
votes
1answer
45 views
Is function `number of TM which terminates on an empty word` computable?
Let f: N → N be a function where ...
0
votes
2answers
31 views
Does there exist an undecidable problem such that the answer is YES for exactly one input to a UTM, and NO for all others?
Suppose I have a universal Turing Machine (UTM) which accepts some input in binary. Is there a computational problem such that the answer to the problem is YES (accepting) for exactly one input (and ...
1
vote
1answer
36 views
Reduction to proof undecidability of the problem: machine M and N accept infinitely many words
I am struggling with the following problem:
Decide whether this problem is decidable or not: For two given Turing Machines M and N, there exists infinitely many words accepted by both machine M and ...
2
votes
1answer
61 views
How to prove the language of Turing machines that run at most $4|x|^2$ steps is not recursive?
I am trying to prove that the language
$$ L=\{M\mid M\text{ is a TM and for all }x\in \Sigma^*\text{ with }|x|>2, M\text{ on }x\text{ runs at most }4|x|^2\text{ steps}\} $$
belongs to Co-RE but ...
2
votes
1answer
35 views
Does a Non-Deterministic Turing Machine solve all problems in P in constant time?
If a non-deterministic Turing machine can just "guess" the correct answer to a problem, does it do this in constant time/immediately? Also, does this also apply to problems in NP too?
0
votes
2answers
32 views
Are Linear Bounded Automatons Turing Complete?
Linear Bounded Automatons are just Turing Machines with finite tape, instead of infinite tape.
But this causes them to not be Turing Complete? Why?
