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)

3
votes
0answers
52 views

Do there exist a pair of 'orthogonal' non-halting Turing machines?

I'll explain what I mean by orthogonal, which is probably a poor choice of words on my part. Given two Turing machines $\lambda $ and $\tau$,and two inputs $i$ and $j$. lets say $\tau(i) \preceq ...
1
vote
0answers
37 views

Need clarification on recursive functions.

Given any function $f: \mathbb{N}_0 \rightarrow \mathbb{N}_0$ and a recursive $h:\mathbb{N}_0 \rightarrow \mathbb{N}_0$ , I know that to prove $h\circ f$ is recursive I only need to prove that $f$ is ...
2
votes
1answer
46 views

Proof of the Computability of Polynomials

In studying properties of polynomial functions I have read that they are computable. The usage of the word read implies that I cannot prove this statement, and withhold using learned for this reason. ...
1
vote
1answer
48 views

What does Gödel mean by “constant” relating godel definition of recursion to the modern def.

In "On formally undecidable propositions..." he writes a function is recursive if "... it is a constant or the successor function" is he referring to the constant function c(x)=k, and if so, is this ...
0
votes
1answer
35 views

Errata for Rogers' Computability book

I would like to get the errata for the Theory of recursive functions and effective computability by Hartley Rogers, 1987 edition.
7
votes
2answers
250 views

Hamiltonian Weighted Graph and Decision Problems

I ran into a question on previous Mid-Exam. anyone could clarify me? Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight. Problem B: Given a Complete Weighted ...
3
votes
2answers
53 views

NP-Complete and Poly Time Reduction Problems [closed]

I Took Some Priminlairity Learning Method on Complexity Theory. I get trouble with some definition. anyone could help me, Why the mentioned statement is True? if a Problem A can be reducible to ...
0
votes
0answers
22 views

Excel: Paying off hypothetic loan in 25yrs vs 30yrs?

I am attempting to recreate an Excel Spreadsheet Dynamic Model (Figure 9.4) presented in my Data Warehousing Decision Support System course. I've uploaded a copy at the following link: Excel Link - On ...
2
votes
0answers
38 views

Is the probabilitistic distribution of the digits in the Chaitin's constant computable?

The Chaitin constant can in principle be computed with exponential effort on each sucessive digit by brute forcing all programs of a given length and simply proving special theorems on each case that ...
-5
votes
1answer
96 views

Some inference in Automaton and Decidable Problems [closed]

Anyone could correct me that the following inference is True: ( G is a Context Free Grammar) There is an algorithm that decides whether the complement of $L(G)$ (language generated by $G$) is empty ...
2
votes
1answer
41 views

Theory Of Computation - recognizable and decidable

How to prove that for any language $A$, if $A$ is recognizable and $A \leq_m A^\complement$, then $A$ is decidable. I know this theorem - A language is decidable iff both it and its complement are ...
3
votes
1answer
60 views

Axioms defining a Turing machine

I have found the following characterisation in axiomatical terms of a Turing machine: $Q_0(q)\rightarrow T(q)$ $S_0(x)\rightarrow S(x)$ $C(x)\rightarrow S(x)$ $Q_0(q)\land T(qx)\land ...
0
votes
1answer
44 views

Decision Problems and Poly Time

We have Two Decision Problem A and B. we know A is NP-Complete, but B can be solved in $O(n^2lg^4n)$, and we know $B \leq_pA $ (i.e each problem of B can be convert to a problem of A in Polynomial ...
1
vote
1answer
21 views

Language described by inverting accepting states of NFA

What is the formal language described by inverting accepting states of NFA? By inverting, I mean that rejecting states become accepting states and accepting states become rejecting states. Is there a ...
1
vote
1answer
31 views

$f \in \Sigma_n^1 \iff f \in \Pi_n^1$ in an analytical hierarchy

The proposition 1.7 in Higher Recursion Theory by Sacks states $f \in \Sigma_n^1 \iff f \in \Pi_n^1$ with the proof: Since $f$ is a function, then, $f(x)=y \iff \forall z. [y \neq z \implies f(x) ...
0
votes
1answer
24 views

What is a regressive set?

Several authors (e.g. Jockusch, Appel, McLaughlin) use a notion of a regressive set, however none of the authors gives a complete definition, they refer to the paper J. C. E. Dekker, Infinite series ...
8
votes
1answer
227 views

Gödel's Second Incompleteness Theorem and Arithmetically Non-Definable Theories

My recursion theory knowledge has become a bit rusty, so I will appreciate any corrections for misstatements. Gödel's incompleteness theorem is often exploited by philosophical discussions which ...
3
votes
1answer
52 views

Simple factorials

I've been doing some work with factorials and the normal way of calculating them is simply not working so well. When the numbers get really big, doing iterative multiplications is not viable and gets ...
1
vote
3answers
74 views

Examples (trivial and non-trivial) of computable functions whose inverse is not computable

Can you give some examples (some trivial and some non-trivial) of computable functions whose inverse is not computable?
4
votes
2answers
88 views

Is $\Delta_0=\Delta_1$ in arithmetical hierarchy?

I have seen a definition (e.g. http://www.math.ubc.ca/~bwallace/ArithmeticalHierarchy.pdf) of an arithmetical hierarchy in computability starting with: "let $\Delta_0=\Sigma_0=\Pi_0$ be the set of all ...
3
votes
2answers
50 views

Fibonacci recursive algorithm yields interesting result

After writing a program in Java to generate Fibonacci numbers using a recursive algorithm, I noticed the time increase in each iteration is approximately $\Phi$ times greater than the previous. ...
1
vote
0answers
49 views

A computable set of sentences neither probable nor disprovable from $PA$

I need to prove that, given a computable binary tree $T$ whose paths are exactly the complete extensions of $PA$ (via some Gödel coding), there is a computable $X\subseteq\mathbb{N}$ such that for all ...
1
vote
1answer
68 views

When is a total $F:\omega^\omega\rightarrow\omega^\omega$ said to be recursive?

Let $F:\omega^\omega\rightarrow\omega^\omega$ be a total function. According to definitions given by Sacks (Higher Recursion Theory) and Rogers (Theory of Recursive Functions) regarding recursive ...
0
votes
1answer
21 views

If a set $\Sigma$ of alphabets is of cardinality $k$, does $\Sigma^n$ have cardinality of $k^n$?

As title says, if a set $\Sigma$ of alphabets is of cardinality $k$, does $\Sigma^n$ have cardinality of $k^n$? This seems to be the case because for each character of the string of length $n$, you ...
0
votes
1answer
31 views

Proving that there exists a function $f: \mathbb{N} \rightarrow \mathbb{N}$ that is not URM-computable.

I'm trying to prove the statement given in the question title, and I'm unsure as to whether my approach is valid. A confirmation of my approach or a correction with a hint pointing me in the right ...
1
vote
1answer
81 views

There exist uncomputable integer numbers?

This question came from the answer I've given to the question An easy example of a non-constructive proof without an obvious "fix"?. Rereading my answer I had some doubt about the ...
2
votes
0answers
34 views

Decidability of given languages

Given are the following languages: $L_1 = \{0\}\\ L_2 = \{w \in \{0,1\}^{*} | L(M_w) = \{0\}\}\\ L_3 = \{w \in \{0,1\}^{*} | M_w \text{ stops at all entries }\} \\ L_4 = \{w \in \{0,1\}^{*} | ...
1
vote
1answer
47 views

Prove that $\{ww^R\#ww^R\}$ is not context free

I need to prove that $L = \{ww^R\#ww^R \; | \; w \text{ is in } \{a,b\}^*\}$ is not context free. I have tried using the pumping lemma for this. For $w=a^pb^pb^pa^p\#a^pb^pb^pa^p$. I have two cases ...
0
votes
1answer
31 views

Does stay put TM recognizes same languages as standard TM

I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or ...
1
vote
2answers
61 views

turing machine with exactly 42 states / state that is visited at least 42 times

I am trying to solve the following problems: Proof wether the following problems are decidable/undecidable: Given turing machine M: Does M have exactly 42 states? Given turing machine M: Does M ...
2
votes
1answer
60 views

Recursively enumerable sets are domain of partial recursive functions

My definition of recursively enumerable set is that it is the language recognized by some Turing machine. I want to show that this definition is equivalent to "a r.e. set is the domain of some ...
2
votes
1answer
72 views

Computable function with noncomputable set of fixed points

I'm looking for a computable function $f: \mathbb{N} \to \mathbb{N}$ such that the set of fixed points $\mathcal{F}_f = \{ e \in \mathbb{N} \mid f(e) \sim e \} = \{e \in \mathbb{N} \mid \forall x \in ...
3
votes
1answer
86 views

Applications of computer science to mathematics

I have been introduced to algorithms, computability and computational complexity (as part of my minor in CS). What are some mathematical topics that I can tackle with the new perspectives I ...
1
vote
2answers
51 views

Let $Q$ be an undecidable subset of $\mathbb{N}$ created by diagonalization. What's the problem with this “algorithm” for computing $Q$?

This is exercise 11 from Hodel, An Introduction to Mathematical Logic, section 1.7. I'm new to computability, so I'm not sure if I got things right. Define the set $Q$ as follows: first, let ...
0
votes
1answer
104 views

Set which has a finite bounded string length

I am trying to work on a proof. I know that using diagonalization argument, we can prove that set of languages over an alphabet is countable. But I am trying to prove that set of all languages over ...
0
votes
1answer
102 views

Existence of T-Vitali sets…

As I understand it Turing degrees are defined as the equivalence classes of sets under the equivalence relation defined by $x \sim y$ iff $x$ is Turing reducible to $y$ and $y$ is Turing reducible to ...
1
vote
1answer
53 views

Most “simple” $\mu$-recursive function that is not primitive recursive

Maybe the most prominent example of a $\mu$-recursive function that is not primitive recursive is the Ackermann function. But writing it out as a $\mu$-recursive function ("breaking it all the way ...
0
votes
1answer
28 views

Currying syntax clarification - how to work through an example of currying?

I understand currying from a computer science background, so I'm happy explaining currying with a before and after example in specific languages, eg, in Java ...
0
votes
0answers
45 views

Why are all computable functions representable in PA?

I'm trying to understand the proof of the first incompleteness theorem, and more specifically, the diagonal lemma. Suppose $GN(x)$ is the Gödel Number of a formula $x$. The first step of the diagonal ...
2
votes
0answers
24 views

Computability of determining whether an expression equals zero

Suppose we are given an expression composed of integers,$ +, *, -, /,$ elementary functions $(exp, sin, cos, tan)$ and their inverses (and for simplicity, assume each argument to these functions is in ...
3
votes
1answer
54 views

Is there an incomplete Turing degree that is not r.e.?

$\exists A \in \mathcal{P}(\mathbb{N}). (A \lt_T 0' \land \neg \exists B \in \Sigma_1. A \equiv_T B)$? In words: does there exist a subset of natural numbers that is Turing reducible to the halting ...
1
vote
1answer
48 views

two way infinite turing machine?

A Single tape turing machine is generally unbounded to right and starts from left. Read/write head moves to right from left after consuming a symbol. But what if we make left side unbounded too and ...
22
votes
8answers
3k views

There is a subset of positive integers which no computer program can print

It's said that a computer program "prints" a set A ($A \subset \mathbb N$, positive integers.) if it prints every element in A in ascending order (Even if A is infinite.). For example, the program can ...
0
votes
1answer
185 views

True or false? If $\eta$ is an explicitly defined incomputable number, then no formal system can pin down the value $\eta$ to arbitrary precision.

Let $\eta$ denote an explicitly defined incomputable real number (the bounty text is faulty, and does not mention incomputability of $\eta$). Then I think that no (recursively ennumerable) formal ...
0
votes
0answers
46 views

Well defined uncomputable numbers.

For any prefix-free universal computable function $F$ with domain $P_F$, the Chaitin’s constant $$ \Omega_F=\sum_{p\in P_F}2^{-|p|} $$ is a number $\in [0,1]$ and seems "well defined". But this ...
3
votes
1answer
78 views

Diagonalization

So off and on I've been studying basic recursion theory and I've realized that, at least when restricted to the basic stuff I've been learning, recursion theory is essentially the study of uses of ...
0
votes
0answers
15 views

program which it's power is equal to LBA

Can anyone give an opinion about this matter: what is the smallest program which it's power is equal to LBA Turing machine(Linear bounded automata are acceptors for the class of context-sensitive ...
1
vote
1answer
57 views

Example for 2 disjoint languages that cannot be separated by a decidable language

Question: Let A, B be languages such that A ∩ B = ∅. Say that a language C separates A and B if: A ⊆ C and B ⊆ $C^c$. Describe two languages A, B ∈ RE, that cannot be separated by any C, such that C ∈ ...
2
votes
1answer
50 views

What is a simple proof that something is np complete that does not use np completeness of something else?

What is a simple proof that something is NP complete that does not use NP completeness of something else? Every proof seems to reduce to something else being NP complete.
2
votes
2answers
83 views

Infinite sets having no RE subsets

I'm back trying to learn recursion theory on my own. I'd like to prove the following result: There exists an infinite set having no infinite R.E. subset. Constructive comments are appreciated. Proof: ...