This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.

learn more… | top users | synonyms

46
votes
3answers
2k views

Are there any Turing-undecidable problems whose undecidability is independent of the Halting problem?

To be more specific, does there exist a decision problem $P$ such that given an oracle machine solving $P$, the Halting problem remains undecidable, and given an oracle machine solving the Halting ...
28
votes
4answers
987 views

Why do we believe the Church-Turing Thesis?

The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to ...
15
votes
3answers
594 views

How can Busy beaver($10 \uparrow \uparrow 10$) have no provable upper bound?

This wikipedia article claims that the number of steps for a $10 \uparrow \uparrow 10$ state (halting) Turing Machine to halt has no provable upper bound: "... in the context of ordinary ...
12
votes
4answers
2k views

How large is the set of all Turing machines?

How large is the set of all Turing machines? I am confident it is infinitely large, but what kind of infinitely large is its size?
10
votes
0answers
207 views

What turmite runs the longest before becoming predictable?

When looking at 2D Turing machines, many of them eventually become predictable. For example, Langton's Ant, the champion 2-color 1-state turmite, develops a highway after 10,000 steps. Predictable ...
9
votes
2answers
1k views

Show that the question “Is there life beyond earth?” is decidable

I was given a question to prove that there exists a turing machine that solves the question Is there life beyond earth? and is decidable. I actually don't understand how to show a turing ...
9
votes
2answers
237 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
7
votes
4answers
480 views

Is the set of PA theorems the same as the set of solvable halting problems?

I am not sure if this is a trivial question. By Post's theorem we know that every PA (first order logic) theorem is equivalent to stating that a given input C in a given Turing machine halts or ...
7
votes
2answers
171 views

Are there known natural problems of intermediate degrees of unsolvability?

I know there exist intermediate degrees of unsolvability, i.e. there are undecidable problems which can be reduced to the Halting Problem, but not vice versa. Are there any "natural" problems known or ...
6
votes
1answer
99 views

An Undecidable but not Universal Turing Machine?

I have seen many examples of universal Turing machines, all of which are undecidable due to the undecidability of the halting problem. I have also seen proofs that certain really small Turing ...
5
votes
2answers
534 views

Why is propositional logic not Turing complete?

According to 1 (probably not the most relevant source), propositional logic is not Turing complete. Aren't all computations in computers performed using logic gates, which can be represented as ...
5
votes
1answer
138 views

Lower bounds for bb(7) and bb(8) wanted

The busy beaver function $bb(n)$ is not known for $n \geq 5$. Does Anyone know suitable lower bounds for $bb(7)$ and $bb(8)$? Remark: $bb(6)$ as a trivial lower bound does not count as a suitable ...
5
votes
0answers
67 views

What Constitutes a Pattern

Mathematics is often referred to as the "study of patterns." What I'm wondering is whether there is somehow a technical way to describe a pattern. For the length of this question let's assume that ...
4
votes
1answer
52 views

What breaks the Turing Completeness of simply typed lambda calculus?

On the Wikipedia page about Turing Completeness, we can read that: Although (untyped) lambda calculus is Turing-complete, simply typed lambda calculus is not. I am curious as to what exactly ...
4
votes
1answer
134 views

How many digits of Chaitin's $\Omega$ constant would we know if we had a $\Sigma_1$-Oracle?

According to Wikipedia (and it seems intuitive from the definition itself), $\Omega$ is Turing equivalent to the halting problem and thus at level $\Delta_2^0$ of the arithmetical hierarchy. Do this ...
4
votes
2answers
64 views

Can you solve the halting problem for a single, non-universal Turing machine?

So, I'm familiar with the halting problem and its proof. However, I also understand that the proof is for any universal machine $U$; that is, the set ...
4
votes
2answers
62 views

Turing Machine Decidability

I have been working on this problem for few hours, but haven't been able to come up with a solution : Is the following problem decidable? Given a TM M, whether there is a w such that M enters each of ...
4
votes
0answers
134 views

Designing a turing machine for primality check.

I am designing some turing machines, so far I have made Binary Addition and subtraction. Now I've been thinking that what if turing machine can check if the number is prime or not. Lets suppose we ...
3
votes
4answers
128 views

Where does this argument showing there are uncountably many TMs fail?

This argument comes up once every while on Lambda the Ultimate. I want to know where the flaw is. Take a countable number of TMs all generating different bitstreams. Construct a Cantor TM which runs ...
3
votes
2answers
66 views

What's the significance of the Church-Turing Thesis?

My understanding is that the thesis is essentially a definition of the term "computable" to mean something that is computable on a Turing Machine. Is this really all there is to it? If so, what makes ...
3
votes
1answer
675 views

How can a turing machine solve the element distinctness problem?

I am reading an example in Sipser's famous book on the theory of computation. In this example, Sipser creates a turing machine M to solve the element distinctness problem. M is given a list of strings ...
3
votes
1answer
53 views

the time required to decide $L$

Suppose that a language $L$ is decided in space $S(n)$ by a DTM with alphabet  $\Sigma$ and set of states $\Gamma$. What upper bound can you give for the time required to decide $L$?
3
votes
1answer
155 views

Explain why if the language A is recursive, then A is reducible to 0*1*

I'm in a theory of computation class and there is a problem that I think I am way overthinking. Can anyone point me in the right direction with the following: Give a short justification of the fact ...
3
votes
1answer
73 views

Is it possible to show that a particular theorem or its negation is provable, without knowing which of the two is true?

I've been thinking about this for a while: as far as we know, is it possible that for a particular statement $\sigma$ of $\textsf{ZFC}$, we can prove that $(\textsf{ZFC} \vdash \sigma) \vee ...
3
votes
1answer
836 views

Designing a Turing machine for Binary Multiplication

I need help designing a turing machine that will compute the following $$f(x,y) = x\times y$$ How to approach this problem in binary base? This is a assignment so I don't want anyone to solve it ...
3
votes
1answer
61 views

Axioms defining a Turing machine

I have found the following characterisation in axiomatical terms of a Turing machine: $Q_0(q)\rightarrow T(q)$ $S_0(x)\rightarrow S(x)$ $C(x)\rightarrow S(x)$ $Q_0(q)\land T(qx)\land ...
3
votes
1answer
63 views

Is there a recursive injective and surjective function f:N→PRF?

It is well known and easy to see that it is possible to effectively number Turing Machine codes. That is, there is an injective and surjective recursive mapping $g:\mathbb N\to {\rm TM}$: each Turing ...
3
votes
1answer
74 views

A constructive algorithm for a jump of a low set.

Suppose we have an oracle Turing machine which, with $K$ (the halting problem) as an oracle, computes a low set $A$. ($A$ is low if $A'\equiv_T K$) Is there an algorithmic way of obtaining a Turing ...
3
votes
1answer
2k views

Build a deterministic turing machine to decide L = { ww }

As the title says. w is in {a, b}^*.Note that I am not looking for the non-deterministic one. Use a Turing machine of one tape and "pointer". An idea: I thought that I would do something like ...
3
votes
1answer
62 views

Are all constrtuctively describable functions continuous? Do they necessarily come with a topology?

In the paper "An injection from $\mathbb{N}^\mathbb{N}$ to $\mathbb{N}$" by @AndrejBauer, about the question whether there exists an injection $\mathbb{N}^\mathbb{N}\to\mathbb{N}$, we writes ...
3
votes
1answer
125 views

Why do complex grammars require powerful algorithms?

I am reading a fabulous book on Formal Languages and in the book it says: As the rewrite rules of a grammar become more complex, the algorithm for recognizing the associated language becomes ...
3
votes
1answer
127 views

Rice's theorem_Theory of computation

Is there any body tell me, where is wrong in this proof Problem: The set of number of turing machine that has 5 state is decidable or not? Answer: The set is obviously 'Set of partial computable ...
3
votes
1answer
144 views

Question about $\Sigma_n$-soundness

According to wikipedia (http://en.wikipedia.org/wiki/%CE%A9-consistent_theory#Definition): "$\Sigma_n$-soundness has the following computational interpretation: if the theory proves that a program C ...
3
votes
1answer
746 views

Baker-Gill-Solovay theorem

I have been trying to understand the proof of Baker-Gill-Solovay theorem as described in Complexity Theory: Modern Approach. I think I do understand most of it, but what troubles me is that let's say ...
3
votes
1answer
142 views

Using Extended Rice's Theorem to Prove Decidability

I have a Turing Machine M. Let L be the set of all strings representing the encoding of M that has input alphabet {1,2}, where M accepts infinitely many strings that start with 1 and finitely many ...
3
votes
0answers
67 views

Do there exist a pair of 'orthogonal' non-halting Turing machines?

I'll explain what I mean by orthogonal, which is probably a poor choice of words on my part. Given two Turing machines $\lambda $ and $\tau$,and two inputs $i$ and $j$. lets say $\tau(i) \preceq ...
3
votes
2answers
74 views

NP-Complete and Poly Time Reduction Problems [closed]

I Took Some Priminlairity Learning Method on Complexity Theory. I get trouble with some definition. anyone could help me, Why the mentioned statement is True? if a Problem A can be reducible to ...
3
votes
0answers
84 views

Show that minimal CFG is undecidable (Sipser 5.36)

Question: Say that a CFG (context-free grammar) is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{\text{CFG}}$ = $\{\, \langle G \rangle$ | $G$ is a ...
3
votes
0answers
138 views

Whats the connection between Turing machine and First order logic?

Today in my Computing class i came across the theorem which states that., If language $L$ and $\Sigma^*\setminus L$ are recursively enumerable then L is recursive (total turing machine). Which looks ...
3
votes
1answer
153 views

Challenge on Some Language and PDA

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
3
votes
0answers
77 views

Maths, esp. Godel, and poetry

At the risk of being an interloper: I'm a poet with a bit of mathematical training. Right now I've got a grant from the Arts Council of Northern Ireland to write a collection (loosely) based on the ...
3
votes
0answers
182 views

Proving a language is not recognizable

I have the following question that I just want to verify I have done correctly. Let $L$, $L_1$, $L_2$ $\subseteq \Sigma^*$ such that $L = L_1 \cup L_2$, and $L_2$ is decidable. Prove that if $L$ is ...
2
votes
1answer
96 views

Showing this language is not decidable by rice theorem or reduction

Consider this language: L = {<M1,M2> : M1 and M2 are TMs and L(M1) contained in L(M2) contained in {1}*} Intuition says that it's undecidable, though can ...
2
votes
2answers
1k views

Why is showing a language is Turing recognizable trickier than showing Turing decidable?

I have written a proof to show that a Turing Decidable languages are closed under union (amongst other things). Later, I have written a proof to show that Turing Recognizable languages are closed ...
2
votes
1answer
61 views

Zermelo–Fraenkel Set Theory

So I'll try keeping this real short and simple. Assume that language $L$ is defined as $\{ x\in \{0,1\}^* \}$ (finite binary strings) such that $x$ encodes a proof in ZFC that 4 is a prime number. I ...
2
votes
1answer
84 views

Unknown symbol '#' in set

I am reading a text on Complexity theory. There is a set whose notation I cannot understand: "Let $\sum$ = {0,1,#}" From the context, and given that the book is used computer science courses, it ...
2
votes
1answer
437 views

Is this undecidable language recognizable?

Is this language: $L = \{\langle M\rangle : \text{$M$ is a Turing machine and $L(M)$ is decidable}\}$ which I know that is undecidable, turing-recognizable? Is its complement recognizable? ...
2
votes
1answer
39 views

Can a halting turing machine write any combination on a tape before halting?

Assume, a halting turing machine uses $n$ items of the tape. Can it write every possible combination on this $n$ items before halting ? We start with a blank tape. Example $n=2$ , alphabet $0,1$ ...
2
votes
1answer
25 views

Turing machine that goes left on first symbol

I have a turing machine with transitions given by the following table I'm inputting the string aaaa. So if I look at the first symbol "a" in state A, it says to replace it with an X, go into state ...
2
votes
1answer
54 views

Given a single taped deterministic turing machine what's the least amount of calculations needed in order to receive the language

Given a single taped deterministic turing machine what's the least amount of calculations needed in order to receive the language $L_k=${$0,1$}$^*0${$0,1$}$^{k-1}$. My intuition says that i'll need ...