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
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?