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)

-1
votes
0answers
7 views

many one reducibility with non r.e. sets

I need to show that $\{x: \phi_x$ is total and constant$\} \leq_m \{x : W_x$ is infinite$\}$ But I am having a hard time defining a function $f$ such that $\phi_{f(x)}$ has finite domain if $\phi_x$ ...
0
votes
0answers
8 views

Projection functions are representable in Axiom System Q

Wish to prove that the projection function is represented in Q by the formula ($x_{1}$= $x_{1}$) & ($x_{2}$= $x_{2}$) & ... & ($x_{k+1}$= $x_{i}$). Basically have to show 2 conditions: If ...
3
votes
2answers
32 views

How does undecidability of 'theoremhood' imply that human ingenuity is necessary in mathematics?

In Robert Stoll's "Set Theory and Logic", there is the following passage on effectiveness of theorems (p. 375) : Mathematical logicians have shown that for many interesting axiomatic theories ...
1
vote
0answers
13 views

Clarification of the argument for the set of total recursive functions not being recursively enumerable?

I read that the set of partial recursive functions is recursively enumerable while the set of total recursive functions is not. Isn't the set of total recursive functions a proper subset of the set of ...
2
votes
2answers
116 views

How can the Gödel sentence be Pi_1

The Gödel sentence must be provable or unprovable by itself - you have to resolve all definitions until it only uses the elementary symbols of Peano arithmetic. What is the correct way to resolve ...
1
vote
1answer
39 views

Are all polynomial-bounded functions computable? [closed]

Let $f = O(g)$, where $g$ is a polynomial. Then is $f$ computable? Let $K(s)$ be Kolmogorov complexity of a string $s$. It's an incomputable function. No. Let $f(x) : \Bbb{Q} \to \Bbb{R}, \ f(x) = ...
0
votes
3answers
64 views

Having trouble understanding Cantors proof that real numbers are uncountable

I found this video very easy to follow and understood the proof. https://www.youtube.com/watch?v=mEEM_dLWY0g However, I am still having trouble understanding the proof presented to me in my csmath ...
0
votes
0answers
25 views

Not every polynomial in $\Bbb{Z}_p[x]$ can be factored, but can you do next best?

If $f \in R = \Bbb{Z}_p[x]$ is irreducible or doesn't have many factors then it could be hard to compute? Possibly, I'm not saying, but... any way, what if $f = h - g$ where $h, g$ are heavily ...
0
votes
1answer
22 views

Any problem computable in $k$ memory slots can be computed with polynomials.

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, ...
0
votes
1answer
66 views

Let A, B be infinite recursive sets with infinite complements. Show that A≡B.

My question is from Hartley Rogers' textbook (1967). Here's how I'm thinking about this so far. I know given infinite recursive sets A, B with infinite complements by theorem II of the current ...
2
votes
1answer
86 views

$\textbf{Q}$ fails to prove some correct $\forall$-rudimentary sentence

Show that the existence of a semirecursive set that is not recursive implies that any consistent, axiomatizable extension of Q fails to prove some correct $\forall$-rudimentary sentence. I ...
1
vote
3answers
29 views

Reducing a Decidability Problem to the Halting Problem

Let $L = \{(M, n): M$ halts on less than $n$ elements from a set S $\}$ I'm trying to come up with a generalization on how to solve these types of problems so I have not defined what S is. Since the ...
8
votes
4answers
538 views

Why isn't there a pumping lemma for recursively enumerable languages?

I'm studying the theory of computation, and I know there are pumping lemmas for regular and context-free languages, but why not for recursively enumerable languages? Is there something about a Turing ...
3
votes
1answer
49 views

How much information is in the question “How much information is in this question?”?

I'm actually not sure where to pose this question, but we do have an Information Theory tag so this must be the place. The "simple" question is in the title: how do I know how many bits of information ...
1
vote
1answer
44 views

A Question About Tennebaum's Theorem?

Tennenbaum's theorem proves there are no countable recursive nonstandard models of Peano arithmetic. It is a proof by contradiction. If our countable, nonstandard model is recursive, then, given a ...
6
votes
0answers
33 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 ...
1
vote
4answers
60 views

Examples of partial functions in which the domain is not known?

I was reading this, it mentions about a kind of function in which the exact domain is not known. The only example given is this one - and I'm not really sure I understood it. I got curious about it: ...
1
vote
1answer
23 views

A characterization of recursive functions via arithmetical formulas

Let $\mathcal{L}_A$ be the first order language of arithmetic with $+,\times,S$ and $0$. Let $\mathfrak{N}$ be the standard model of arithmetic. An $n$-ary relation $R$ on natural numbers is said to ...
0
votes
1answer
17 views

Prove uniqueness of recursive function

I am currently reading Cutland's Computability and would like to figure out how to solve Theorem 4.2 which states: Let $x=(x_1 \dotsc x_n)$, and suppose that $f(x)$ and $g(x,y,z)$ are functions; ...
2
votes
0answers
59 views

Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$ A_{0}(y)= y+1$$ $$ A_{x+1}(0)= A_{x}(1)$$ $$ A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
0
votes
0answers
20 views

Prove that div(x,y) is primitive recursive (integer division

Prove that div(x,y) is primitive recursive (integer division). I tried thinking about it, I just don't know how to write it formally. it is kinda obvious that I should subtract y from x several times ...
1
vote
1answer
33 views

Why one defines the proper complexity functions?

Definition: A proper complexity function is a function $f$ mapping a natural number to a natural number such that: $f$ is nondecreasing There exists a $k$-string Turing machine $M$ such that on any ...
3
votes
2answers
64 views

Mathematical intro to Turing machines

Is there a good mathematically rigorous introduction to computability theory based on Turing machines? I have looked at some CS books but found them quite unsatisfying for a mathematician (too wordy ...
0
votes
0answers
58 views

A Question Regarding Ordinal Turing Machines

Consider the following theorem of Koepke: 'A set x of ordinals is ordinal computable from a finite set of ordinal parameters if and only if it is an element of the constructible universe L". Taking ...
1
vote
1answer
46 views

Is the language $L=\{ww^f|w\in \{0,1\}^*\}$ CFL?

Where $w^f=$flipping the bits of w. For example, $(0010)^f=1101$, $(010111)^f=101000$ I tried to prove that $L$ is not CFL using the pumping lemma, with no succeed. In addition, I need to prove ...
0
votes
3answers
61 views

the difference between regex operations (math) and regex (unix/linux)

what is the difference between regular expression operations (union, concatenation, kleene star) and regular expression (implemented in UNIX and can be used together with the grep command)? Are there ...
1
vote
1answer
37 views

Is $L=\{w\mid \text{ same number of 010 and 101}\}$ regular?

I tried to prove that this language is regular using NFA or regular expressions and didn't succeed. I would like to see some solutions
0
votes
1answer
19 views

Program with no intermediary states

Every program P which built of function sequence (order counts): $F_1,..,F_n$, where $F_i$ returns $R_i$ and $F_{i+1}$ takes $R_i$ as an argument, can be shown as $F_1(F_2(F_3(...(F_n))))$, i.e. we ...
2
votes
1answer
30 views

Decidability of a set

A pair of twin primes is defined as (p, p+2) where both p and p + 2 are prime. Given $S = \{i\in Z^+ | i\, is\, one\, of\, a\, pair\, of\, twin\, primes\}$ Is S decidable? My understanding is that ...
0
votes
1answer
62 views

If the union of two languages is NP-complete, is one of them NP-complete?

Question 1) If $A\cup B$ is NP-complete, and $A$ is NP, and $B$ is P, then is $A$ NP-complete? I don't think so but I am unsure. When I try to reduce $A\cup B$ to $A$, I fail because strings in $B$ ...
0
votes
1answer
48 views

Using diagonal argument to prove that H(x)=μyT(x,x,y) has no total computable extension

Hello everyone just like the title says I want to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension such that if we had a function $BIG(x)$ that is both total and agrees with $H(x)$ ...
1
vote
1answer
88 views

Is the proof of the uncomputability of the following function correct?

Let the following function be given: $f(x) = \begin{cases} 1 & \mbox{if } \forall n \Phi_x(n+1) \uparrow \mbox{ or } \Phi_x(n+2) \uparrow \\ \uparrow & \mbox{otherwise} \end{cases}$ Define ...
1
vote
1answer
31 views

Showing a Problem Is Undecidable

How can I show that T is undecidable using only this information? $$T = \{\langle M, w, r\rangle \mid M \text{ accepts } w^r \text{ when it accepts } w.\}$$ So, what it's saying is that the machine ...
-1
votes
1answer
44 views

Reduction from HALT on any string to HALT on empty string

The title says it all (if I have phrased it properly). How can we show that HALT on any string is undecidable using a decider for HALT on empty string? I think this is written: $$ HALT \leq ...
0
votes
0answers
75 views

When is a Decidable Set Decidable?

Can the same set be decidable in a strong theory and undecidable in a weaker theory? Some possible examples. Goodstein's theorem says every Goodstein sequence, $g(n)$, eventually terminates. ...
0
votes
0answers
62 views

A is recursive iff A is the range of an increasing function which is recursive

Working a problem stated in Enderton, but stated better and apparently stronger in Soare. All citations hereon are for Soare (1987). Would appreciate help on the proof. I know there has to be a more ...
4
votes
2answers
75 views

Showing that a function is not computable.

the following function was shown not to be computable: $h(x) = \begin{cases} \mu n.\Phi_x(n) \downarrow & \mbox{if } \exists n \Phi_x(n) \downarrow \\ \uparrow & \mbox{otherwise} \end{cases}$ ...
0
votes
0answers
24 views

A turing machine which computes the same language as a “stay put” turing machine

Im not sure I really understand how stay put machines work. I know they are just like turing machines but with states. So they can "stay put". But what confuses me is when you define a FSA for a ...
0
votes
0answers
25 views

Polytime implementation of Discrete Log using primitive recursive functions

The primitive recursive functions are defined by Godel as: $z() = 0$ $s(x) = x+1$ $\pi_i(x_1, \dots, x_k) = x_i$ Plus closure under Composition: $h(x_1, \dots, x_m) = f(g_1(x_1, \dots, x_m), ...
7
votes
2answers
234 views

Existence of a utility function on the reals

Suppose I have $\preceq$, a total order on $\mathbb R^n$. I wish to show that there is a utility function $u:\mathbb R^n\to\mathbb R$ such that $x\preceq y \leftrightarrow u(x)\leq u(y)$. I came up ...
1
vote
2answers
47 views

Decidability of Recursively Enumerable Languages

I'm having trouble with this problem, I know that every decidable language is recursively enumerable but that not every recursively enumerable language is decidable. What are the steps involved in ...
2
votes
1answer
24 views

if I find a bijection, rather than it is computable or not even computable, then the set would be denumerable or not?

In "Computability: an introduction to recursive function theory", by Cutland, there is a theorem as follows: Theorem 2.4 $\mathcal{C}_n$ is denumerable. where $\mathcal{C}_n$ represents the set of ...
1
vote
1answer
33 views

Kolmogorov (Kolmogoroff- ) Complexity of infinite sequences, Request for Proof

Let $\xi \in X^{\omega}$ be an infinite sequence and denote by $\xi[1\ldots n]$ its length $n$ initial segment. Then (due to Martin-Löf) the following holds: For every $\xi \in X^{\omega}$ there ...
1
vote
1answer
21 views

Constructing function for set enumeration

Let $X$ be a set non-negative integers. Let $X^i$ denote $i$-th cartesian power of set $X$. Let $X^* = \bigcup\limits_{i=1}^\inf X^i$, i.e. all possible combinations of $X$'s elements. Let ...
1
vote
1answer
29 views

Direct proof that $K \leq_\mathrm{T} Rec$

Soare's Recursively Enumerable Sets and Degrees (1987) shows that $Rec = \left\{ e : W_e \text{ is recursive} \right\}$ is $\Sigma^0_3$-complete via its relationship to other index sets, namely $Cof$ ...
1
vote
1answer
48 views

Show that the Turing machine will solve the self-halting problem

Suppose we have Turing machine $M^*$ that: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Show that you cannot construct $M^*$. ...
0
votes
3answers
30 views

Figuring out the steps in a Recursive Function

I have the following recursive function: $f(0) = 7$ $f(n+1) = f(n) + 6n + 1$ for all integers $n => 0 $ I know the answer is $f(n) = 3n^2 + 2n + 7$ I would like to know the steps to get to this ...
0
votes
1answer
32 views

Kolmogorov (Kolmogoroff-) Complexity, Contradiction with Invariance Theorem.

Fix some programming languages $S$ which is rich enough such that one can write interpreters for $S$ in $S$. Define $$ K(w) := \mbox{length of a shortest program producing $w$}. $$ Now fix some ...
7
votes
1answer
82 views

Proof-theoretic characterization of the primitive recursive functions?

The total recursive functions are exactly those number-theoretic functions that can be represented by a $\Sigma_1$ formula of first-order arithmetic. Is there a similar characterization of the ...
0
votes
1answer
61 views

Show that $gcd(x,y)$ and $z = lcm(x,y)$ is primitive recursive

For the $gcd(x,y)$ we note: $gcd(x,0) = x$ $gcd(x,succ(y)) = gcd(succ(y),mod(x,succ(y)))$ $succ(x)$ and $mod(x,y)$ are both primitive recursive, so $gcd(x,y)$ must be as well. $z = lcm(x,y)$ if ...