Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

learn more… | top users | synonyms (1)

3
votes
1answer
165 views

Reducing the complexity of a turing machine algorithm

i'm trying to solve this question: Given a turing machine that is decidable by at most 50 * n^4 steps, can we build a dif algorithm that can decide it in n^4 steps? Me and my friends thought about ...
3
votes
1answer
647 views

Turing machine configuration and computation history

These are a series of questions about Turing machines. First, are the number of a given Turing machine configurations (state + tape) countable? Secondly, given that a computation history is a ...
2
votes
1answer
121 views

Graph enumeration problems which admit recursive solutions

This is an attempt to refine my previous question into something precise enough to admit a resolution. Let $P\;$ be a graph property, let $T_n\left(P\;\right)$ be the set of isomorphism classes of ...
3
votes
2answers
778 views

Undecidable languages and mapping reducibility

I am using Sipser terminology here. Can anyone give examples of languages A and B such that we can prove B is undecidable using A in a proof by contradiction but we A is not $\leq_m$ B. An example ...
1
vote
2answers
147 views

Nondeterminism and computational models

So it is clear than the nondeterministic versions of computational models such as the Turing Machine is equivalent in "power" to the deterministic model. Other than showing this fact, what would be ...
1
vote
1answer
257 views

Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?

Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}? One case this is possible is when ...
5
votes
2answers
515 views

Example of an UnDecidable Logical Theory which is an extension of a Logical Decidable Theory?

Let $T_1$ and $T_2$ be two first-order logical theories (over the same signature) such that $T_1 \subseteq T_2$ and both are recursively axiomatized. My question is the following: is it possible that ...
8
votes
2answers
461 views

Is the group isomorphism problem decidable for abelian groups?

According to wikipedia the group isomorphism problem is an undecidable problem. When we restrict to (countable) abelian groups does it become decidable or does it remain undecidable? In case it ...
5
votes
4answers
837 views

The word problem for finite groups

The word problem for finite groups is decidable. Is it obvious that this is true? In particular, I'm not entirely sure about what it means for the problem to be decidable (in this case---I think I ...
3
votes
1answer
152 views

Algorithms to prove that polynomials don't have integer solutions

OK, I know that Matiyasevich's solution to Hilbert's 10th problem shows that there is no algorithm to decide whether or not a polynomial $p(x_1,\ldots,p_n)$ with integer coefficients has a solution ...
3
votes
1answer
208 views

Can a polynomial size CFG over large alphabet describe any of these languages:

Can a polynomial size CFG over large alphabet describe any of these languages: Each terminal appears 0 or 2 times Word repetition {www* | w \in \Sigma *} (word repetition of an arbitrary word w) ...
2
votes
1answer
249 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
5
votes
5answers
686 views

Can a polynomial size CFG over large alphabet describe a language, where each terminal appears even number of times?

Can a CFG over large alphabet describe a language, where each terminal appears even number of times? If yes, would the Chomsky Normal Form be polynomial in |Σ| ? EDIT: What about a language where ...
3
votes
1answer
351 views

Diophantine equation and Turing Machine

If a Diophantine equation is: exists v, p(x,v) = 0 (where v is a vector of finitely many integers) for some polynomial p, is there a Turing machine which prints out all values of x?
2
votes
1answer
2k views

Quotient of a regular language

According to wikipedia the right quotient of a regular language with ANY other language is regular. I have not been able to find a proof of this fact. All the sources talk about quotient with another ...
3
votes
3answers
244 views

Are there problems that can't be expressed as languages?

OK, so I was told in CSTheory that I should be asking here. So my question is the following: I've taken my first course on Language Theory and we saw the "standard" classification of languages. We ...
6
votes
1answer
338 views

Is there an infinite set of strings whose Kolmogorov complexities are computable?

Is there an infinite set of strings whose Kolmogorov complexities are computable?
9
votes
2answers
667 views

Can we reduce the number of states of a Turing Machine?

My friend claims that one could reduce the number of states of a given turning machine by somehow blowing up the tape alphabet. He does not have any algorithm though. He only has the intuition. But ...
2
votes
1answer
179 views

Hint on Kleene's O

I figured out this order on $\omega^2$: elements of different columns are ordered by their column number; within column $m$, the order is $0 \gt 1 \gt 2 \gt \cdots \gt n$, where $n$ is the first such ...
4
votes
1answer
250 views

(Semi-)Decidability of Turing-completeness of cellular automata

This is a follow-up to the question Undecidability in Conway’s Game of Life I posted at mathoverflow. For some cellular automata it can be proven that they can simulate a Turing machine, normally by ...
2
votes
2answers
241 views

Does this proof for the undecidability of the halting problem violate the axiom of regularity?

One proof of the halting problem goes by contradiction like this : Assume there is a Turing machine $H$ that can decide the halting problem, then construct a Turing machine $Q$ that takes as input a ...
11
votes
7answers
1k views

“Proof” that ZFC is inconsistent using Turing machines

I came across the following "proof" for the inconsistency of ZFC and can't find the flaw in it (if there is one...): Construct a Turing machine A which sequentially runs on all proofs in ZFC and ...
7
votes
4answers
361 views

Are the computable reals finitary?

In the comment thread of an answer, I said: The computable numbers are based on the intuitionistic continuum, and are not finitary. To which T.. replied: Computable numbers are not based on ...
7
votes
3answers
427 views

Why are $\Delta_1$ sentences of arithmetic called recursive?

The arithmetic hierarchy defines the $\Pi_1$ formulae of arithmetic to be formulae that are provably equivalent to a formula in prenex normal form that only has universal quantifiers, and $\Sigma_1$ ...