Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [computability]

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

2395 questions
2
votes
1 answer

A question on essentially undecidable first-order theories

I am trying to show the following equivalence: a (consistent) first-order theory $T$ is essentially undecidable if and only if every complete extension of $T$ is undecidable. By "$T$ is essentially undecidable" I mean that any consistent extension…
CWcx
  • 608
2
votes
1 answer

$A_n$={$x \in \mathbb{N}\mid n \in W_x $} and computation questions?

I‌ prepare for Final-Exam on Complexity Course. in one of my prof. old-exam I see this question: Suppose $A_n$={$x \in \mathbb{N}\mid n \in W_x $}. Which of them is false? 1) Set $A_n$ for each natural number is r.e 2) $ \forall n A_n =_m K$ (K is…
user223522
2
votes
2 answers

Showing a set $\Sigma^0_n$ subset of $\mathbb{N}$ is $\Sigma^0_n$-complete

This is both a general and specific question in basic computability theory. Broadly speaking, I am not very comfortable with showing whether or not a subset of $\mathbb{N}$ is $\Sigma^0_n$ (or $\Pi^0_n$) complete. I am struggling with several such…
CWcx
  • 608
2
votes
1 answer

Help on two exercises about computability theory

In Cooper's book, I can't think out the solutions of two exercises. 1.show that there exists a simple set S contains the set of all even numbers. 2.show that each creative set is contained in some simple set. By the way,they are not homework…
user25494
  • 21
  • 1
2
votes
1 answer

Using the recursion theorem

The Recursion theorem states that if $f$ is a (total) computable function, then $f$ has a fixed point in the sense that there exists an $e$ such that $\varphi_e = \varphi_{f(e)}$. I have the following corollary to the Recursion theorem which I can't…
user151850
  • 87
2
votes
1 answer

Are fixed-point combinators general recursive?

I'm not even sure if I'm asking the right way, but here's what I'd like to know: If your language has fixed-point combinators, is it automatically Turing complete?
sdleihssirhc
  • 121
2
votes
1 answer

Computable function that enumerates the primitive recursive functions

I'm trying to construct a computable function $f:\omega^2\to\omega$ such that For all $e\in\omega$, $x\mapsto f(e,x)$ is primitive recursive. If $g:\omega\to\omega$ is primitive recursive, then there exists $e\in\omega$ such that $f(e,x)=g(x)$ for…
user188201
1
vote
0 answers

How to track unboundedly many changes?

Suppose that I have a piece of paper with 0 on it (and nothing else). Suppose that, at each instant, I can either replace what is on the paper by writing either 0 or 1. I say that I change the value on the paper if I replace 0 by 1 or if I replace 1…
MatteoBianchetti
  • 436
  • 3
  • 10
1
vote
0 answers

What would an "algebraic axiomatization of the partial recursive functions" be?

Hartley Rogers in his "Theory of recursive functions and effective computability" (page 55 in the first edition) writes "What resemblance types are also isomorphism types? A final answer to this question has not been given. The only cases…
Peter Percival
  • 11
1
vote
0 answers

It is undecidable if The Intersection between Context Free Language and Context Sensitive Language is the empty set

I'm trying to show that the following problem is undecidable: The intersection between a Context Free Language (CFL) and a Context Sensitive Language(CSL) is the empty set. I know that is undecidable if a CSL is the empty set, but how can I reduce…
Henry Park
  • 21
1
vote
0 answers

Decidability involving functions

I'm trying to figure out how to resolve this exercise. $$ \Sigma = \{a,b\} $$ is a set while $$ \mathcal{P}(\Sigma^*) $$ is the partition of sigma star. I have a function f: $$ f: \mathcal{P}(\Sigma^*) = \mathcal{P}(\Sigma^*)$$ such that for all…
Henry Park
  • 21
1
vote
1 answer

Partial recursive functions as products of sets of total recursive functions?

Let C be a collection of two or more total recursive functions. Define ϕ(x) as the function which is undefined if any two members of C give different values for x as input, and whose output is the same as the output of a member of C, if all members…
MikeC
  • 1,473
1
vote
1 answer

Is the given Language decidable or recognizable?

Let M be a machine that takes a natural number as input and outputs a natural number. Let L = $\{M:\;M(n)\;outputs\;a\;prime\;greater\;than\;n\;for\;every\;n\}$ Is L decidable? Is L recognizable? Intuitively, my thoughts are that L is neither…
user137481
  • 2,605
1
vote
0 answers

Is a set $\{ e \in \mathbb{N} | \#\{x \in \mathbb{N} | \phi_e(x) \downarrow \} = \#\mathbb{N}\}$ computable?

Denote every partial computable function $f$ with its Godel number $e \in \mathbb{N}$ by $\phi_e$. Then let the halting set of $\phi_e$ be $W_e=\{x \in \mathbb{N} | \phi_e(x) \downarrow \}$ where $f(x)\downarrow$ means that $f$ halts on the input…
Dávid Natingga
  • 2,889
  • 2
  • 27
  • 41
1
vote
2 answers

Proof that INF (the set of indices of Turing Machines that halt on infinitely many inputs) is not computably enumerable, I.e. $\not \in \Sigma_1^0$

I got curious about this today when looking for sets to proove aren't $\Sigma_1$ as exam prep. Unlike with its complement, FIN, a run of the mill contradiction was not easy to come by (perhaps I'm being stupid), and the infinite domains of the…
G. H. Faust
  • 1,766
1 2 3
…
19 20