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)

0
votes
3answers
186 views

Why are the primitive recursive functions a subset of the recursive ones?

I am trying to show, that the set $PR$ of primitive recursive functions is a subset of $R$, the recursive functions. Could someone help me, complete the proof of that assertion ? My idea: Since $PR$ ...
1
vote
2answers
176 views

Why is the set of primitive recursive functions well defined?

The set of primitive recursive functions is defined as the smallest subset $F\subseteq \cup _{k\in \mathbb{N}} \{f:\mathbb{N}^k \rightarrow \mathbb{N}\}$, satisfying the properties 1) $F$ contains ...
8
votes
4answers
457 views

Consequences of solving the Halting problem

What impact would a device (ie super-computer or relativistic computer or other method) that solves the halting problem have on math? Would there be any mathematical problems left to solve? What ...
10
votes
4answers
565 views

What is undecidability

What does it mean that some problem is undecidable? For instance the halting problem. Does it mean that humans can never invent a new technique that always decides whether a turing machine will ...
1
vote
1answer
198 views

Does this number exist?

Consider the finite algorithm A, and the real number $0<T<1$. The output of A on input T is all possible theorems and provable propositions in ZFC, and only that. Q1. Can such an algorithm and ...
3
votes
3answers
426 views

Growth rate of primitive and $\mu$-recursive functions

Functions that are not primitive recursive but $\mu$-recursive are said to grow too fast to be primitive recursive. Are there functions $f$ and $F$ such that a function is primitive recursive ...
15
votes
5answers
1k views

Is it possible to solve any Euclidean geometry problem using a computer?

By "problem", I mean a high-school type geometry problem. If no, is there other set of axioms that allows that? If yes, are there any software that does that? I did a search, but was not able to ...
4
votes
2answers
779 views

Is this function a primitive recursive function?

Let $t \in \mathbb{N}$ and consider the function $f: \mathbb{N} \rightarrow \mathbb{N}$, defined by $f_t (m)= 2 \uparrow^{m} t$, where "$\uparrow$" is Knuth's up-arrow notation (which can be ...
3
votes
4answers
446 views

Recursion theory text, alternative to Soare

I want/need to learn some recursion theory, roughly equivalent to parts A and B of Soare's text. This covers "basic graduate material", up to Post's problem, oracle constructions, and the finite ...
2
votes
2answers
179 views

Recognizable or not?

This is related to a homework question for a class that I am TAing for. I'm using Sipser terminology here (recognizable for computably enumerable, decidable for computable). Given that $w^r$ is the ...
7
votes
1answer
8k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
5
votes
3answers
202 views

Approachable = provably approachable?

Question: Let’s call a real number $x$ approachable if there exists a Turing machine $M$ such that $M(1), M(2),\dots$ is a sequence than converge to $x$. If we can prove (edit: In ZFC) that the ...
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
655 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
794 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
516 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
465 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
855 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
209 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
250 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
687 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
378 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
341 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
682 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
432 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$ ...