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
5
votes
4answers
5k views

Decidability of empty intersection of two languages accepted by Turing machines

I am really struggling with determining the decidability of languages and cant figure out whether this problem is decidable or not. I have a language $\qquad\displaystyle L = \{ (R(M_1), R(M_2)) \...
5
votes
2answers
529 views

Proof-sketch on the language accepted by a Turing machine

Let $T$ be a Turing machine whose accepted language is $L(T)$. Let $X$ be another language. How do you approach a proof like $L(T)\subseteq X?$
5
votes
1answer
2k views

Example of unrestricted grammar which produces non-context-sensitive language

I'm talking about Type-0 (Chomsky hierarchy) unrestricted grammar, where production rules of grammar are of the form $\alpha\rightarrow\beta$, where $\alpha,\beta\in N\cup\Sigma$. I can not find any ...
5
votes
2answers
8k views

What is an “encoding” of a TM?

I'm currently working on a reduction from $A_{TM}$ to another language, and have been reading through some example proofs. I've come across the situation where, for example, we have $L = \{ \langle M,...
5
votes
3answers
761 views

Fastest algorithm to decide whether a (always halting) TM accepts a general string

Given a TM $M$ that halts on all inputs, and a general string $w$, consider the most trivial algorithm (Call it $A$) to decide whether $M$ accepts $w$: $A$ simply simulates $M$ on $w$ and answer what ...
5
votes
2answers
156 views

Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time

In this proof of the Space Hierarchy Theorem the following language is defined $$ L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\...
5
votes
1answer
82 views

Computability of Stack Cleanliness

Brain-Flak is a minimalistic, stack-based, Turing complete, esoteric programming language. A big concern among Brain-Flak enthusiasts is a concept informally called "stack cleanliness". The basic ...
5
votes
2answers
83 views

Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable

Define the language $\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$ where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$. Prove that $R$ is co-...
5
votes
1answer
6k views

Difference between a TM with an empty language and the one accepting empty string

If a TM(Turing Machine) accepts NO input string(even the blank), then its language is empty. If a TM ONLY accepts the blank string(meaning that there is nothing on the tape except for the default ...
5
votes
1answer
186 views

Conflicting definitions of language accepted by Turing Machine?

I am reading Papadimitriou, Computational Complexity, page 24, where it is says We say that $M$ accepts $L$ whenever for any string $x \in (\Sigma - \{\sqcup\})^*$, if $x \in L$, then $M(x) =$ ``...
5
votes
2answers
494 views

PSPACE-complete problems can't be in NL using the space hierarchy theorem?

I want to prove that no PSPACE-complete problem is in NL using the space hierarchy theorem. What I want to say is this : From the time hierarchy theorem I know that for every $t(n)$ there exists a ...
5
votes
1answer
292 views

How a reduction can help up solve a problem?

I am studying the basics of Computation Theory and I came up with an example I can't understand. Let's have a language $L = \{\langle M\rangle \mid L(M) = \Sigma^{\ast} \}$, so $L$ contains codes of ...
5
votes
1answer
2k views

Non-deterministic Turing machine and palindromes

I have to design a Non-deterministic Turing machine that accepts only non-palindromes in $NTime(n\log n)$. I think this would be easy on a 2-tape DTM. Simply copy the string onto the second tape – $O(...
5
votes
3answers
2k views

How to calculate the number of states in designing a Turing machine?

I would like to ask how to determine the number of states when designing a Turing machine from the description for a language? For example: $\qquad \displaystyle L = \{wcw \mid w \in \{0,1\}^*\}.$ I ...
5
votes
1answer
313 views

Decidability of Machines

I cannot understand decidability really well. I have been reading from books and internet, but I am little bit confused. According to the book (as I understood), we can decide on decidability of a ...
5
votes
1answer
526 views

Confused between turing-completeness and universal approximation - are they related?

I am trying to de-knot a point of confusion in my mind regarding "turing-completeness" and the "universal approximation theorem". The context here is deep neural nets: So, consider two types of ...
5
votes
3answers
187 views

Language of TMs that accept some x in less than 50 steps. Is it in co-RE?

L = {M | M is a TM and there exists an input that the TM M accepts in less than 50 steps} I need to find a minimal class it belongs to between R/ RE/ co-RE/ not in RE∪co-RE. I managed to show that ...
5
votes
1answer
372 views

Prove that there is no computable enumeration of all decidable languages

The question: Let $L_1,L_2,...$ be an enumeration of $\mathcal{R}$ and define $A_i = \{\langle M\rangle \ | \ L(M) = L_i\}$. Let $L$ be a language in $\mathcal{RE}$ such that $L \subset \{\langle M\...
5
votes
1answer
3k views

How to find left-hand side of tape on a Turing Machine?

I am pretty new to Turing Machines and am trying to figure something out. So let's say I have a tape with input 0 0 1 0 0 1 The language is twice as many 0's ...
5
votes
1answer
121 views

Problem regarding Turing Machine notation

Here I have a Turing Machine (sorry for awful drawing): So, I have a question regarding the usage of a here. It is treated as a variable here. But since it doesn't ...
5
votes
1answer
260 views

Why the name Recursively Enumerable and Recursive? [duplicate]

Why did the sets of languages accepted/decided by a TM get the name Recursively Enumerable and Recursive, respectively?
5
votes
2answers
145 views

Countably many oracle Turing machines?

In Sipser's text, when proving that there exists an oracle $A$ such that $P^A \ne NP^A$, he writes: Let $M_1, M_2, \ldots$ be a list of all polynomial time oracle TMs. I understand that there are ...
5
votes
1answer
736 views

Non-deterministic Turing machine to solve graph colouring

Consider the graph coloring problem: given an undirected graph $G$ and a natural number $n$ return yes if we can color the graph with n different colors and no otherwise. I am able to design a ...
5
votes
1answer
1k views

How to convert a Turing Machine program to a tiling using Wang Tiles?

This is a cross-post from a post on MathSE due to lack of answers. To illustrate my question I provide the following example. The website Online Turing Machine provides a Turing Machine simulator. ...
5
votes
2answers
2k views

EQtm is not mapping reducible to its complement

This is a problem from Sipser's book (marked with an asterisk). $EQ_{TM} = \{(\langle M \rangle, \langle N \rangle)$ where $M$ and $N$ are Turing machines and $L(M) = L(N)\}$ We know that neither $...
5
votes
1answer
376 views

For the time hierarchy theorem, how is the input translated efficiently?

I'm trying to understand the proof of the time hierarchy theorem appearing in sipser's book. The proof requires a TM M to simulate an arbitrary TM N without too much slowdown. In particular, it is ...
5
votes
1answer
103 views

The content of an implication from the snm-Theorem

I have a question on the statement of the s-m-n Theorem and the implication $$ \varphi_{f(x,y)} = \lambda z \varphi_x(\varphi_y(z)) $$ for some recursive function $f(x,y)$ cited in the above link. ...
5
votes
1answer
944 views

Understanding Levin's Universal Search

I am having troubles understanding Levin's universal search method. In Scholarpedia, http://www.scholarpedia.org/article/Universal_search, it is claimed that “If there exists a program $p$, of length $...
5
votes
0answers
51 views

Analogue of the topology-computability correspondence for computational complexity

There is an interesting correspondence between notions of topology and notions of computability theory originating from the ingenious idea of Dana Scott to identify computable functions with ...
5
votes
0answers
129 views

Is $E_{LBA}$ a Turing-recognizable language? [closed]

I know that $E_{LBA} = \{\langle M \rangle ~ \mid ~ L(M) = \emptyset \}$ is an undecidable language, but is it recognizable (recursively enumerable)? It seems that it's complement is recognizable ...
5
votes
0answers
180 views

Difficulty in the halting problem for a simple Turing machine with standard enumerations of programs and of initial tape configurations

Preparations Consider a Turing machine with just one head and one tape (on which the head may move left, move right, or remain stationary), and with just two symbols ("blank" and "non-blank"). The ...
4
votes
4answers
600 views

Can Turing Machines solve non-decision problems?

Since TMs are equivalent to algorithms, they must be able to perform algoriths like, say, mergesort. But the formal definition allows only for decision problems, i.e, acceptance of languages. So how ...
4
votes
5answers
181 views

Where can I find a short and 'easy' peer reviewed paper on something from computability, decidability or complexity?

It's a homework assignment, we were asked to read, understand, and present to our colleagues a short paper/article (suggested 4-6 pages) for our Computability, Decidability or Complexity class. The ...
4
votes
3answers
5k views

Given two total Turing machines, is it undecidable problem to detect whether they give the same output on all inputs?

See title. And by all inputs I mean providing the functions with the same input and checking whether they give the same output for each case. EDIT If it can be reduced to Halting problem, then how? ...
4
votes
2answers
792 views

$L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular

Suppose that $L(M) = L$ where $M$ is a $TM$ that moves only to the right side. I need to Show that $L$ is regular. I'd relly like some help, I tried to think of any way to prove it but I didn't ...
4
votes
2answers
6k views

Non Recursively Enumerable Languages

Can someone give me an example of Non Recursively Enumerable language... i.e. A language which no Turing machine can accept ? What makes a language non recursively enumerable ?
4
votes
2answers
758 views

Why is a deterministic Turing machine a special case of a probabilistic Turing machine?

I have no formal training in computer science as I have not yet taken any such classes, so perhaps this question appears naive. I was reading about BPP and it was claimed that a deterministic Turing ...
4
votes
3answers
2k views

Turing machine and coming up with an idea

I read many things about the Turing machine and understand how it works but what I can't get the grasp of (and what none of the books seem to try to teach) is how should I approach a problem I am ...
4
votes
4answers
7k views

Language of Turing machines that loop on all inputs, recognizable?

Prove that the language Loop Turning Machine = { < M > | M is a TM that loops on all inputs} is recognizable. I feel like $M$ would never halt. To make $M$ recognizable it needs to accept or ...
4
votes
3answers
763 views

Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?

The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers. An ...
4
votes
3answers
1k views

Definition of Turing Machine as a language acceptor

The following is an excerpt from the book "An Introduction to Formal Languages and Automata" by Peter Linz. My question is, why is $\Sigma^+$ used and not $\Sigma^\ast$?
4
votes
1answer
3k views

Multitape Turing machines against single tape Turing machines

Introduction: I recently learned that a multi-tape Turing Machine $\text{TM}_k$ is no more "powerful" than a single tape Turing machine $\text{TM}$. The proof that $\text{TM}_k \equiv \text{TM}$ is ...
4
votes
1answer
459 views

Halting problem with Proof of The Immerman-Szelepcenyi Theorem (knowledge of the theorem might not be necessary to clear my doubt)

So, I was reading this pdf on complexity theory. On page 18 pf pdf (Page 12 of book) The Immerman-Szelepcsenyi Theorem is mentioned with proof. The following lines are from the book : The idea is ...
4
votes
1answer
277 views

Lambda Calculus in Rewriting systems

How to do or implement Lambda Calculus in a Rewriting systems? Rewriting systems are Turing complete. But I can't figure out how to do lambda calculus or functions with them.
4
votes
4answers
242 views

Is computation independent of hardware?

We use electronics to build computers and do computation. Is computation independent of the hardware we use? Would it be possible to do whatever a computer does with pen and paper? If computation is ...
4
votes
3answers
516 views

Can every program be parallelized infinitely and automatically?

In my previous question ( Can Turing machines be converted into equivalent Lambda Calculus expressions with a systematic approach? ), I got the answer that it is indeed possible. And as I have read ...
4
votes
2answers
2k views

Can I construct a Turing machine that accepts only its own encoding?

Is the set $S$ = $\lbrace M \mid M \text{ is a Turing machine and }L(M)=\lbrace \langle M\rangle\rbrace\rbrace$ empty? In other words is there a Turing machine $M$ that only accepts its own encoding? ...
4
votes
1answer
557 views

Can we read N numbers in O(N) time?

In a different post it came up that (using the Turing machine model of computation), it is not even safe to say that $N$ numbers can be read in $O(N)$ time. To me this is boggling since it's ...
4
votes
2answers
549 views

Proof of Trakhtenbrot's theorem

In the proof of Trakhtenbrot's theorem (as given in "Elements of Finite Model Theory" by Leonid Libkin), for every Turing machine $M$, author constructs a FO sentence $\Phi_M$ of vocabulary $\sigma$ ...
4
votes
1answer
888 views

Official Name for the “First” Programming Language Developed by Turing?

As is widely known, Alan Turing discovered/invented the Turing Machine in his classic 1936 paper. Here he also gave how these machines are specified in terms of their machine states and instructions ...

1
3 4
5
6 7
35