Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [turing-machines]

Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.

2
votes
1answer
9 views

checking whether a language is turing recognizable

After reading about it in the textbook and in the web, i was wondering about the "turing recognizable" concept. so for instance, if i take a simple language like:"L = {< M > | M ACCEPTS < M >}",...
0
votes
1answer
20 views

How does a Turing machine compute when its head is at the right-hand end of its configuration?

I'm reading Sipser's Introduction to the Theory of Computation (2nd ed.), and I am having trouble understanding one of the cases of Turing machine computation. Sipser describes the cases in terms of ...
2
votes
1answer
28 views

Constructing a reduction between two languages about pairs of Turing machines

I'm curious about a potential relation between the following two languages. $L_1 := \{\langle M_1, M_2 \rangle : L(M_1) \cap L(M_2) \ne \emptyset \}$. $L_2 := \{\langle M_1, M_2 \rangle : L(M_1) \...
3
votes
2answers
47 views

Enumerate over all halting Turing Machines?

I understand that it is possible to enumerate over all Turing Machines. My understanding of how this works is by fixing an encoding of natural numbers to TM descriptions, and then enumerating the ...
0
votes
1answer
32 views

Implementation-level of a Turing machine that accepts a specific language

I'm trying to figure out a way to implement this kind of a Turing machine that accept the following language: $$\Sigma = \{ 0,1,2 \}, \quad\quad L(A) = \{ abc \mid a=b \land c = a^R \}$$ I was ...
5
votes
2answers
529 views

Do I need to consider instance restrictions when showing a language is in P?

I have already shown that 3-colorable for an unrestricted graph is in NP, but I was thinking about the similar language defined as the set of all acyclic $G$, where $G$ such that $G$ is 3-colorable. ...
0
votes
1answer
36 views

Complexity of an encoded turing machine

This is an example of an assignment question, there are 3 of them so I created my own in order to better understand it. First, we have the variable m which is a ...
1
vote
0answers
19 views

Is there any specific model/theory that proposes that the universe is an oracle machine? [closed]

Is there any specific (and well known/famous) model/theory that proposes that the universe is an oracle machine? Physicist Roger Penrose said his book "The Shadows of the Mind" It would be just as ...
0
votes
0answers
23 views

Analyzing the encoding of a DFA by a deterministic Turing machine [duplicate]

Define $L=\{\langle D,R \rangle \mid D$ is a DFA, $R$ is a regular expression, $L(D)=L(R) \}$ Is $L$ decidable? Is $L$ decidable in polynomial time ($L \in P$)? I am trying to ask: can a TM analyze ...
0
votes
1answer
38 views

Is there any model of Game of Life compatible with hypercomputation?

I found a question in Mathematics Stack Exchange which asks a very similar question (https://math.stackexchange.com/questions/1023812/hypercomputation-higher-dimensional-variants-of-conways-game-of-...
0
votes
1answer
61 views

Decide if a string is in a language without simulating the automata accepting the languge

Is it possible for a Turing machine with input of a DFA that accepts a finite language and a string to decide whether the string is in the language without "fully simulating" the DFA on the string? ...
2
votes
0answers
21 views

Is there a formal way of defining a Zeno Machine?

The idea of a Zeno machine is pretty interesting to me, but I can't seem to find a formal definition for how a Zeno machine would work. I can find a couple of definitions around but they are all ...
1
vote
1answer
55 views

Is it decidable whether a Turing machine M will reach state q on input s?

Given a turing machine $M$, one of its states $q$ and an input word $w$, will $M$ ever reach $q$ on $w$? As we are not given anything about the word length, I assume that we have a finite length word....
1
vote
1answer
77 views

Counter Machine (Halting Problem)

How can we show that Halting Problem for one-counter additive machines is decidable ?
1
vote
1answer
32 views

Turing Machine where branches are resolved via arbitrary operator

Alternating Turing Machines output Boolean values and combine the values returned by branches via the any/all operators. Is ...
4
votes
0answers
23 views

Unbounded-time programs in lambda calculus?

The Turing machine model has been extended to “infinitary turing machines”, which are Turing machines that can perform a countably and uncountably infinite amount of computations in finite time. Is ...
2
votes
1answer
41 views

Prove the languages |L<M>| = 2 and |L<M>| $\not=$ 2 to be non-Turing recognizable or non-recursively enumerable

I am trying to prove the non-recursively enumerable property of two languages. $L_2 = \{\langle M \rangle: |L\langle M \rangle| = 2\}$ and $L_{\not=2} = \{\langle M \rangle: |L\langle M \rangle| \not=...
0
votes
0answers
31 views

How to show that the complement of ATM $\leq_{m}$ L = {<M> : |L(M)| = 2}?

My original intention was to prove that $L = \{\langle M \rangle \mid |L(M)| = 2 \}$ is not turing recognizable but soon I realized that I could use the complement of ATM because the complement of ...
1
vote
1answer
24 views

Reading elements of a countable set with Turing machine

I have a basic question about the behavior of a potential Turing machine. Suppose that $S$ is a countable set of binary strings, so that we can enumerate $S$ as $(s_i)_{n\in \mathbb{N}}$. Suppose ...
3
votes
2answers
46 views

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

In this proof of the Space Hierarchy Theorem the following langugae is defined $$ L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\...
3
votes
2answers
184 views

Is the set of language decidable by some Turing machine computing in some given computable time bound decidable

Let $T : \mathbb N \to \mathbb N$ be some computable function. Then by $\mathcal C_T$ we denote the class of languages decidable by a deterministic Turing machine in at most $T(|w|)$ steps for an ...
2
votes
2answers
61 views

Why cannot we enumerate all Turing machines that have no fixed point?

The language $$ L_1 = \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) = x\} $$ ($w$ is an encoding of a DTM, $M_w$ is the respective DTM.) is not decidable, according to Rice's ...
1
vote
1answer
13 views

Show: “Checking no solution for system of linear equations with integer variables and coefficients” $\in \mathbf{NP}$

I've been struggling for a while trying to solve this problem: Show that the following problem is in $\mathbf{NP}$: Check that a system of linear equations with $m$ integer variables and integer ...
4
votes
1answer
68 views

Transforming TM with useless state(s)

I'm new to Computation Theory and trying to figure out the undecidability problems. Last night, I came up with the language of TM with a useless state: $\text{USELESS_TM} = \{ \langle M, q \rangle\...
2
votes
1answer
16 views

Is this proof for showing that $EQ_{CFG}$ is co-Turing-recognizable incorrect?

I have been searching for proofs that show that $EQ_{CFG}$ is co-Turing-recognizable. When searching for proofs I can only find proofs on the following form: Construct a TM $M$ which recognizes the ...
1
vote
1answer
40 views

Halting Problem, Typed Version: A Headache

After many years, I have been revisiting the venerable old Halting Problem and the self-referential / diagonalization “party trick” that shows that there is no Turing Machine able to solve it. I was ...
2
votes
1answer
59 views

Is the Shakespeare Programming Language Turing complete?

I was reading about tge Turing machine. I also came across with the Shakespeare programming language. After trying to understand the basics of the PL, I thought ...
1
vote
1answer
32 views

Constructing CFG

How to generate CFG for this language? $ L = \{ w \mid w \in \{ (, [, ], ) \}^* \text{ s.t. } $ In any prefix of $w$, no. of ( is more than no. of ), and no. of [ is more than no. of ]. $\}$ Thus,...
0
votes
2answers
66 views

Proving a language as undecidable without using reductions

Let's say our Σ is 0 and 1. I want to disprove the following: There can be Turing Machines that accept only 1's, i.e. 1, 11, 111, etc. Therefore, all languages that have strings of 1's are ...
1
vote
1answer
34 views

Max number of configurations of a Turing Machine

I was wondering about a result in the Sipser book which states that any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$. Is this because a configuration consists of a state, a ...
1
vote
1answer
39 views

Find a language $L$, such that $L \notin \mathbf{P}$, but $L^* \in \mathbf{P}$

I'm being asked the following Find a language $L$, such that $L \notin \mathbf{P}$, but $L^* \in \mathbf{P}$ For the $L \notin \mathbf{P}$-part I have to show that there is no polynomial Turing ...
0
votes
1answer
50 views

Would Schmidhuber's theories of everything be capable of performing hypercomputation?

Jürgen Schmidhuber pointed out that a simple explanation of the universe would be a Turing machine analogy programmed to execute all possible programs computing all possible histories for all types of ...
1
vote
1answer
31 views

Recognizer to check if the language of a Turing machine contains a finite subset

Let $B = \{ 123 \}$. Note that $B$ is finite. Let $L = \left \{ \left\langle M \right\rangle | M \text{ is a Turing machine such that } B \subseteq L(M) \right\}$. Is it sufficient to show that $...
2
votes
1answer
49 views

Can generalized Turing machines compute all reals?

Super-recursive algorithms are theoretical super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines. In this entry it ...
5
votes
4answers
2k views

Is the infinite language unrecognizable in a Turing machine?

This question is building up on an older one, here. But now let's say we keep $Σ=\{0,1\}$. Is the TM that accept anys ($1^x \mid x \gt 0$) recognizable? That means 1, 11, 11111, 1111111, and so on ...
2
votes
2answers
43 views

Is the reverse of a closed under operation maintainable?

I'm looking at the following question from this handout: The class of decidable languages is closed under union My question is, does this hold in reverse? Is there a phrase for this? Basically, if ...
0
votes
0answers
31 views

Church-Turing thesis and hypercomputation?

The Church-Turing is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being following an algorithm, ignoring resource ...
1
vote
0answers
23 views

Converting (reverse-engineering) Turing machine into program or most concise algorithm?

It is known that every program or every algorithm can be converted to Turing machine. But what about the reverse process? Is there algorithm (or research trend that considers such algorithm) to ...
1
vote
1answer
23 views

Is there any problem that is R-complete and RE-complete

R-complete, i.e. it is an analogue to all recursive language can be reduced to that problem and also recursive? Or is there a really such definition? RE-complete is described on wikipedia. But what ...
1
vote
1answer
45 views

A language which is neither r.e. nor co-r.e

First, consider $$L_\exists=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts some input}\}$$ is RE. I tried to construct a Turing machine: ...
1
vote
1answer
26 views

Proof of proposition between Precise Turing Machine and Proper Complexity function

In "Computational Complexity" textbook by C. H. Papadimitriou, p. 141, he proved the following claim. Proposition 7.1: Let there be a DTM/NDTM M that decides a language L within time/space $f(n)$, ...
1
vote
0answers
29 views

Can a Turing Machine compute the binary representation of $n!$ in $O(n!)$ time?

We can compute the binary representation of $n$ and similarly by decrementing the value of $n$ by $1$ each time we can get all values from $2$ to $n$. We can now use a Turing Machine that multiplies ...
2
votes
0answers
629 views

Turing machine VS Push Down Automaton in CFL

I want to ask that between turing machine and pushdown automaton: which abstract machine can handle context-free language (CFL) in a more efficient way, and why? I know that a pushdown automaton can ...
2
votes
1answer
39 views

Decidability of language of TMs which accept only their Gödel number [duplicate]

I am trying to prove that $L = \{\langle M \rangle \mid L(M) = \{\langle M \rangle \}\}$ is undecidable, where $\langle M \rangle$ is the code of the TM $M$, and $L(M)$ the language recognized by $M$....
1
vote
1answer
43 views

Prove Halting on all Inputs is not in RE simulation

I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine ...
0
votes
1answer
29 views

Can a non-RE language be reduced to an RE language?

Let $L$ be recursively enumerable and $U$ be non-recursively-enumerable. Is it possible to reduce $U$ to $L$ recursively, $U\leq_R L$? Personally, I do not think this is possible. If we can reduce $U$ ...
1
vote
1answer
44 views

Reduction between these two languages

I'm given $L_\cap=\{\langle M_1\rangle\#\langle M_2\rangle\mid L(M_1)\cap L(M_2)\neq\emptyset\}$ and $L_U=\{\langle M\rangle\#w|M \text{ accepts } w\}$. How can I reduce the former to the latter: $L_\...
1
vote
1answer
26 views

Interpretation of Turing's statement on universal computers

I'm currently reading a book about artificial intelligence and i frequently come across the concept of universal computers, as it is essential to understand the book i would like to know the meaning ...
1
vote
1answer
35 views

Rice's theorem applicable to the following language?

Let $L= \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle \} $ be a language where $\langle M \rangle$ is the Code of the TM $M$. $L$ is undecidable. I've heard that I can't use Rice's ...
1
vote
1answer
39 views

REC and RE under intersection

Would the intersection of a recursive language and a recursively enumarable language be recursive or recurisvely enumbarable or neither? Assume $L_{3}$ is the intersection of some language $L_{1}$ $\...