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
0answers
24 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
207 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
115 views

Counter Machine (Halting Problem)

How can we show that Halting Problem for one-counter additive machines is decidable ?
1
vote
1answer
35 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 ...
6
votes
0answers
29 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
77 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
65 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
25 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
72 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
285 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
77 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
23 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
229 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
34 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
47 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
75 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
38 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
117 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
113 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
42 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
60 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
40 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
55 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
77 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
51 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
32 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
28 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
67 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
34 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
35 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
712 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
43 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
67 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
57 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
48 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
28 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
58 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
44 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}$ $\...
1
vote
1answer
98 views

Language of TM is Undecidable

why is this Problem$$L = \{ \langle M\rangle \mid L(M) \text{ is undecidable}\}$$ undecidable? I thought if we know $L(M)$ the turingmaschine accepts all $x \in L(M)$, so $L(M)$ is in every case ...
2
votes
1answer
40 views

Is there a relation between the size of the domain/range of a function and its computability?

This was a question given in a course, without answer. The referenced literature (just a few books) do not cover it, unfortunately. I think there is no relation with the range as the range of the ...
0
votes
0answers
61 views

Correctness proof: induction on sequence of steps, need a stronger claim?

Im trying to prove the correctness of the construction proposed in this site answer: a two stack PDA that simulates a Turing Machine. By "correctness" i mean to prove more or less formally that we can ...
1
vote
0answers
55 views

How can an arbitrary Turing machine running for $t$ steps be simulated in $O(n \log(n))$ steps?

I'm confused about a point regarding the Time Hierarchy Theorem. In order to establish the upper bound for this theorem it's necessary to show the following: We're given $(\langle M \rangle, t)$ ...
-3
votes
3answers
97 views

Does undecidability violate Turing completeness? Shouldn't “complete” include “decidability”? [closed]

Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"? That is, if one has a language that's Turing complete, but expresses infinite computation (i.e. may not ...
1
vote
2answers
102 views

Are $A$ and $B$ necessarily be decidable if $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable and $A$ & $B$ being exhaustive?

I found the following question Suppose A and B are recursively enumerable languages such that $A∪B=Σ^∗$. Further, suppose $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable. Which of the following ...
1
vote
1answer
62 views

Space and time complexity of $L = \{a^nb^{n^2} \mid n≥1\}$

Consider the following language: $$L = \{a^nb^{n^2} \mid n≥1\}\,$$ When it comes to determining time and space complexity of a multi-tape TM, we can use two memory tapes, the first one to count $n$, ...
2
votes
1answer
153 views

Confusion about proof of undecidability of REGULAR TM in Sipser's book [duplicate]

in the book "Introduction to the Theory of Computation" by Michael Sipser there is an example of undecidable languages in which there is a language REGULR_TM which is described as follows : ...
2
votes
0answers
94 views

Equivalence between different Turing Machines and a definition of simulation

Im having some difficulty understanding how the following two concepts could be related. Equivalence between TMs as is commonly tought According to this site answer, to prove a standard TM model to ...
1
vote
1answer
52 views

RAM BSS model based (or its variant) computer recognizing Boolean languages

Can any RAM BSS model based machine, or machines which are variants, recognize boolean languages(languages such as P, NP, or the like)? If so which languages are recognizable by RAM/BSS nachines, or ...
2
votes
0answers
37 views

Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...