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)

0
votes
1answer
40 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
19 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
21 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
75 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
30 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
34 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
29 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
53 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
50 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
63 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
74 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
44 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
87 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
96 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
41 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
25 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
34 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
23 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
44 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
39 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 ...
21
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
181 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
33 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
70 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
14 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
50 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
46 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
77 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: ...
2
votes
3answers
117 views

A mathematically mature introduction to Turing Machines and Computability [reference-request]

In the computer science course for mathematicians held at my university Turing Machines have been presented very briefly. So much so that I didn't quite get why they are relevant to mathematics. I did ...
1
vote
2answers
44 views

let A be a $2\times 2$ matrix . Then the smallest number $n\in \mathbb N$ such that $A^n=I$ is

let A be a $2\times 2$ matrix $\begin{pmatrix} \sin \frac \pi {18} & -\sin \frac {4\pi} {9}\\ \sin \frac {4\pi} {9}&\sin \frac \pi {18}\end{pmatrix}$. Then the smallest number $n\in \mathbb N$ ...
7
votes
1answer
83 views

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal?

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal? If so, is there a nice proof of this?
1
vote
1answer
43 views

Can differential calculus (limits, integrals, derivatives) be encoded in lambda calculus?

I am wondering, if the Church-Turing thesis holds (all effectively calculable functions are computable by Turing machines/lambda calculus) and I can compute the limit of a function by hand, what is ...
0
votes
1answer
37 views

Help understanding a 'reversing a string' Turing Machine

I am having a bit of a confusion understanding some transitions in a Turing Machine. Its an example from Introduction to Languages and the Theory of Computation by John C. Martin. I've attached the ...
1
vote
0answers
40 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
6
votes
1answer
150 views

Turing invariance on large sets

Definition: A function $f: 2^{\omega} \rightarrow 2^{\omega}$ is Turing invariant if $x \equiv_T y \rightarrow f(x)\equiv_T f(y)$. Question I (under $ZFC$): Let $f: 2^{\omega} \rightarrow 2^{\omega}$ ...
1
vote
2answers
58 views

Are there undecidable problems for which a solution has been found?

I mean are there examples of problems that have been proven to be undecidable, in the sense that it would not be possible to devise a deterministic computer program that outputs a solution for an ...
0
votes
0answers
81 views

could a machine $\mathfrak{D^+}$ be made to produce $\beta$ so the diagonal argument could be used on computable numbers?

I was reading Turing's paper "On computable numbers, with an application to the Entscheidungsproblem" and while reading $\S\ 8$ (his proof that computable numbers are enumerable) and his proof that ...
2
votes
1answer
68 views

Prove a set is not recursive / recursively enumerable

I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$? $B-A$ is obviously recursively ...
0
votes
1answer
19 views

complexity question regarding whether it is decision problem

When self teaching complexity theory and seeing arguments that were made online. I get some confusion. In the class, we classify problems into P: can be computed polynomially NP: given a claimed ...
1
vote
0answers
39 views

Find a $w$ such that $wxy = xyy$

Let $n,m \in \mathbb{N} \cup \{*\}$ and define $$nm = \begin{cases} \varphi_n(m) &\mbox{if } \varphi_n(m) \mbox{ converges} \\ * & \mbox{otherwise, including } * \in \{n,m\} \end{cases}$$ ...
1
vote
1answer
39 views

Is universality decidable?

Is there a turing machine which can take any other TM T as input and decide whether T is a universal turing machine?
1
vote
2answers
24 views

Question regarding the arithmetic hierarchy notation used in the corollary of Post's theorem

A set $B$ is $\Delta_{n+1}$ if and only if $B \leq_T \emptyset^{(n)}$. More generally, $B$ is $\Delta^C_{n+1}$ if and only if $B \leq_T C^{(n)}$. This is from ...
0
votes
1answer
60 views

Relationship between the Turing Machine and RAM Models

Could you tell me which is the relationship between the Turing Machine and RAM Models??
1
vote
1answer
43 views

Are these two notions of “computable function” the same or related?

From http://en.wikipedia.org/wiki/Semicomputable_function, we have: "If a partial function is both upper and lower semicomputable it is called computable." Is this the same kind of "computable ...
0
votes
1answer
34 views

Recursively enumerable sets: the halting set

Wikipedia on the Halting Problem: The conventional representation of decision problems is the set of objects possessing the property in question. The halting set $K := \{ (i, x) ~|~ \textrm{program ...
0
votes
0answers
11 views

Turing machine that modifies each cell that contains a certain input one time at most

If I have a single tape turing machine running on some input $x$, where it modifies each part of the tape with $x$ one time at most...would the TM be decidable? Any advice or guidance appreciated; ...
1
vote
2answers
37 views

What is effectively continuous?

In Soare's book Recursively Enumerable Sets and Degrees I saw a sentence: $\Phi_e$ is an effectively continuous functional from the Cantor space $2^\omega$ to itself. What does it mean for a ...
1
vote
1answer
29 views

Is it decidable that any two computable function over reals $ f(x_1,x_2,\dots,x_n)\equiv g(x_1,x_2,\dots,x_n)$

Is it decidable that any two computable function over reals or over sphere of complex $ f(x_1,x_2,\dots,x_n)\equiv g(x_1,x_2,\dots,x_n)$ ?
2
votes
1answer
43 views

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 ...
2
votes
1answer
40 views

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?