Tagged Questions

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).

115 views

Proofs about theorem-provers in ZFC, in ZFC

Is the following statement provable in ZFC for some $A$: "$A$ is an algorithm which, when given as input a proposition $p$ in the language of ZFC, outputs 'yes' only if $p$ is provable in ZFC, 'no' ...
21 views

Is there a typical amount of clauses (in a 3CNF SAT expression)? Do SAT solvers regularlary solve expressions (or attempt to) with many?

I'm curious as to in what settings we would be interested in finding out whether a boolean expression in 3CNF with a large number of clauses is satisfiable (I''m not sure how "large number" is defined ...
15 views

Does any non-admissible numbering form a PCA?

Given a numbering $\varphi_0, \varphi_1, \dotsc$ of the unary partial recursive functions, define a PAS as $\mathbb N$ with application $x \cdot y \simeq \varphi_x(y)$. If the numbering is admissible ...
93 views

Markov's paper on insolubility of the homeorphy problem

I am looking for an English translation of Markov's 1958 paper, On insolubility of the homeorphy problem, which I remember coming across on a website for a computational topology course (taught by ...
88 views

Is there a way to decide whether a differential equation is solvable or not?

Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson had negatively settled Hilbert 10th problem, I wonder if there is an analog result to the differential equations ?
100 views

Parity of TREE(3)?

The number TREE(3) is somewhat famous for being incomprehensible big. But since it's just a finite number it must have a parity. Is the parity of TREE(3) known?
36 views

Recursive languages , please check whether my explain is correct?

Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows. $$L = \begin{cases} (0+1)^* & \text{if } P = NP \\ \phi & \text{otherwise} \end{cases}$$ Which of the following ...
172 views

Anti-random reals

EDIT: This has now been crossposted at MO: http://mathoverflow.net/questions/219366/antirandom-reals. This is partially motivated by my question at mathoverflow: http://mathoverflow.net/questions/...
113 views

enumerability exercise in boolos book

problem 2.2 of Computability and Logic written by Boolos(p.20, fifth edition) Show that if for some or all of the finite strings from a given finite or enumerable alphabet we associate to the string ...
64 views

Proving finite-automata transition function for string concatenation

I'm having a few problems with this proof and I'm not sure where to start. In our class, a Deterministic Finite Automata, or DFA, is defined as a 5-tuple $$M = (Q,\Sigma,\delta, q_0, F)$$ Where $Q$...
37 views

Let $G(x,y)=2^x(2y+1)-1$ and show that $G$ is computable

Show that $G$ is a computable bijection and that the functions $G(G_1(z))$,$G_2(z))=z$ for all $z$ is computable. To show that it is computable, do we show that the above function $G$ is primitive ...
72 views

Show undecidability by reducing from Hilbert's $10^{th}$ problem

To show that the existential theory of $\mathbb{Z}$ in the language $\{0, 1; +, \mid , \mid_p\}$ (where $x \mid_p y \Leftrightarrow \exists r \in \mathbb{N} : y=\pm xp^r$) is undecidable we have to ...
76 views

Is the reduction correct?

Is the following formulation of the reduction correct? EDIT: Undecidability of an (positive) existential theory $T$ is proved often by reducing an other (positive) existential theory $T'$, which ...