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
vote
2answers
100 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
104 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
46 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
583 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
52 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
56 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
47 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
71 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
28 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
27 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
86 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
90 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
39 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
119 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
63 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
50 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
106 views

What is the difference between regex operations in math and regex in 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
40 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
32 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
92 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
93 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
35 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 ...
0
votes
1answer
66 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
86 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
86 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
85 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
28 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
1answer
41 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
252 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
61 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
33 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
37 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
27 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
30 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
57 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
36 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
36 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
108 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
99 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 ...
1
vote
3answers
70 views

How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
1
vote
1answer
76 views

Problem from Cutland's Computability: 3.2. problem 3

The problem goes as follows. Let f: N --> N, such that f is partial, N is the natural numbers, and let m $\in$ N. Construct a non-computable function g such that g(x) = f(x) for x$\le$m. Proof: By ...
0
votes
2answers
55 views

Understanding second axiom of Primitive recursion

I read about Primitive recursion and was able to understand most of it. However I am finding it very difficult to understand the second axiom of primitive recursion. I can make out that it helps in ...
0
votes
1answer
70 views

Complexity of Recursively Inseparable Sets

I am interested in examples of recursively inseparable sets. A standard example is the set of positive integers encoding a Turing machine that halts in an odd number of steps on blank input versus ...
1
vote
1answer
36 views

Function composition in computability

I have been reading Cutland's computability book, which is really good! However, I have found myself thinking way too much about one little passage in the the third section of the second chapter (the ...
0
votes
3answers
47 views

A multivariate function, computable for any fixed first argument, is computable

Claim: If $f:\mathbb N^{k+1}\to\mathbb N$ is a function such that for all $x_0\in\mathbb N$, $\lambda x_1,\dots,x_k.f(x_0,x_1,\dots x_k)$ is a partial recursive function then $f$ is also partial ...
1
vote
1answer
49 views

Non-computable c.e. sets are Kurtz random

I'm trying to directly show that non-computable c.e. sets are Kurtz random, without using the concept of genericity, but to little success. I assume by way of contradiction that $\emptyset'$ (for ...
2
votes
1answer
44 views

The “computability” of fundamental physical constants

I would like to ask if any of the fundamental physical quantities like the speed of light or plancks constant (all measured according to a common standard of of units) can be classified as computable ...
19
votes
2answers
2k views

Are transcendental numbers computable?

Wikipedia states: "The computable numbers include many of the specific real numbers which appear in practice, including all real algebraic numbers, as well as e, π, and many other transcendental ...