Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

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

2
votes
2answers
61 views

Arithmetical formalization of “F is sound”

In How subtle is Gödel's theorem? More on Roger Penrose, Martin Davis points out the fact that the statement F is sound $\implies$ G(F) is true where F is some recursively axiomizable extension ...
0
votes
0answers
16 views

Proving language is not context free using pumping lemma

Hi I'm completely stuck on an exercise which is to prove this language is not context free using pumping lemma for context free languages: ...
0
votes
0answers
17 views

Understanding the pumping lemma for CFL

I'm having a hard time with understanding the pumping lemma for CFL. I found this online and can't wrap my head around how it works. ...
0
votes
0answers
18 views

Computability: Proving a predicate is not recursively enumerable

Let P(p) <=> for each x, comp(p,x) is defined. Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
-3
votes
1answer
34 views

Is it possible to add two irrational numbers in finit time to infinite precision? [closed]

This question is related to Laplace's demon and the solar system as a chaotic system, as well as the paradox with the hare and the turtle (I think). Imagine you want to calculate the future of the ...
3
votes
1answer
58 views

Can we describe any subsets of $\mathbb{N}$ occurring in a late layer of the Constructible Universe?

There is a certain large countable ordinal referred to in the literature as $\beta_0$. It was first discovered by Paul Cohen, and here are some equivalent characterizations of it: The smallest ...
0
votes
1answer
32 views

Terminology: arithmetic vs. expressible vs. represented

A function $f:\mathbb{N}^k\rightarrow\mathbb{N}$ is arithmetic iff its graph is arithmetic, i.e., there is a formula $\psi(\vec{x},y)$ in the language of Peano arithmetic such that for all $\vec{a}$ ...
0
votes
1answer
26 views

Let $\sum =\{a, b\}$ and $L =\{aa, bb\}.$ Use set notation to describe $L$ complement.

So I know that I want to find $\sum^* - L$ , but I am at a loss regarding how to express that in compact set notation. Any pointers would be appreciated!
2
votes
1answer
36 views

Relationship between Post’s theorem and minimization

I am confused about the relationship between the quantifier complexity of formulae in the language of arithmetic and the computational classification of the sets those formulae define. Specifically, ...
0
votes
0answers
12 views

Computability: Primitive Recursive Predicate Existence iff computation is defined

If T is a primitive recursive predicate. How do I prove that if comp(p,x) is defined ⇔ ∃y. T(p,x,y) I thought of a function with x as input for each q,y, if the T(q,y,x) holds then it is defined, ...
0
votes
1answer
22 views

Prove the following language is not regular using the Pumping Lemma for Regular Languages

I am trying to use the Pumping Lemma to prove the language $$L=\{a^nb^mc^md^n\}$$ is not regular. However, I am having trouble when selecting the values of x, y, and z to show that xyz is contained ...
0
votes
1answer
20 views

is it possible to convert assignment of a set of boolean variables into a 3cnf propositions in polynomial time?

very interested in knowing if this conversion is possible, i.e if we can create a function that can be computed in a polynomial time is respect to the input size, so that for an input of boolean ...
1
vote
0answers
69 views

Simple examples of the diagonal lemma

According to Boolos' Computability and Logic, the diagonal lemma states: Let $T$ be a theory containing $\mathbf{Q}$. Then for any formula $B(y)$ there is a sentence $G$ such that $\vdash_T\,G\...
0
votes
0answers
30 views

Confused about non-computable real numbers and countability. Is Cantor diagonalization a computation?

Suppose I start with the set of computable real numbers between 0 and 1. Now these are countable. So I follow Cantor's diagonalization argument to construct a real number B between 0 and 1 outside ...
1
vote
1answer
39 views

Proving undecidability of group isomorphism problem from an unsolvable word problem

From The Princeton Companion to Mathematics, IV Branches of Mathematics, pages 126-127: Suppose that $\Gamma = \langle A | R \rangle$ is a finitely presented group with an unsolvable word problem, ...
8
votes
2answers
232 views

Why does this procedure terminate? Or are there any numbers for which it doesn't?

I don't really have good formal education in theoretical mathematics, so please don't be upset if this is obvious question, but on the other hand I don't believe I am the first one to think of such ...
-1
votes
1answer
37 views

If a length is 1 and then it's elevated to two then what is it? [closed]

If $x=1$, then that means that $x^2 = 1$, also. Is the case the same if it has to do with lengths? That's if I got the $|x| = 1$ and then I raised to the power of two so $|x|^2= ...$ will it then be 2 ...
0
votes
2answers
32 views

Can a regular language contain non regular strings?

Check this problem (1.71 from Sipser 3rd edition): Let $\sum = \{0,1\}$. Let $A =\{0^ku0^k \ | \ k \ge 1 \ and \ u \in \sum^*$}. Show that $A$ is regular. $u$ can be $\{0,00,000,...,01,011,...,1,11,...
4
votes
1answer
55 views

One to one correspondence between transcendental and uncomputable numbers

I know that both sets are uncountable infinite but the transcendentals are not a subset of the uncomputables. I don’t know if there exist uncomputable numbers that are not transcendental. But my ...
0
votes
0answers
43 views

Can I reverse this notation?

I don't know this is a proper question on this forum but I was reading about computability theory and computational complexity theory and I saw the reduction concept and its notation like this: A ≤p ...
0
votes
0answers
47 views

Cardinality of uncomputable functions

Let's denote the set of all computable functions from $\mathbb{N} \to \mathbb{N}$ as $F$. Now, by any Gödel numbering, $F \simeq \mathbb{N}$. However, $\mathbb{N}^\mathbb{N} \simeq \mathbb{R}$. It'...
2
votes
1answer
47 views

Decidability of Gödel sentences.

Letting $\text{Pr}(x)$ be a formula that weakly represents the set $\{x:x\text{ is a Gödel code of a provable sentence in PA}\}$, where PA means Peano Arithmetic. Gödel's first incompleteness theorem ...
2
votes
2answers
65 views

Correspondence between a countably infinite set A and the set of positive integers

I'm currently taking a course on logic & computability and they're using as a manual the famous "Logic and computability" by Boolos, Burgess and Jeffrey. The last week I've been trying to solve ...
3
votes
1answer
88 views

In what way is the structure of the Turing degrees “extremely complicated”?

The Wikipedia article on Turing degrees states "One general conclusion that can be drawn from the research is that the structure of the Turing degrees is extremely complicated." They claim this is ...
1
vote
0answers
24 views

Non existence of certain hyperarithmetical functions

In what follows, $\phi_n$ is the $n$th partial recursive function, and $\phi_n^g$ is the $n$th partial recursive function with oracle $g$. We say $x\in\mathbb{N}$ is pre-total if the following two ...
0
votes
3answers
48 views

How is it possible that some infinite sets are decidable?

Note: as you can probably tell, I'm a layman without mathematical maturity but very interested in the foundations of math. Def. A set is decidable if and only if there is an effective method for ...
2
votes
1answer
148 views

prove/disprove: If the language $L$ is such that for every $CFL$ $L'$ , the language $L \cap L'$ is $CFL$, then $L$ is regular?

Hey guys I got this question in my homework and I can't figure out what to do: If the language $L$ is such that for every $CFL$ $L'$ , the language $L \cap L'$ is $CFL$, then $L$ is regular? I sat ...
0
votes
2answers
51 views

Inequalities between large numbers?

It's been shown Gaham's Number g₆₄ is way larger than Moser's Number (< g₃), itself larger than Skewes' Number {≈(10↑↑4)34}. How about the position of Grahal g₁ = 3↑↑↑↑3 (or Triteto) with respect ...
2
votes
1answer
36 views

Deterministic rule sets and unique $\Phi$-proofs

I'm studying generalized inductive definitions and I got the following question; here, I use the "rule" definition of a g.i.d., instead of the monotone operator approach. So let $\Phi$ be a set of ...
3
votes
2answers
79 views

Arity of Primitive Recursive Functions

I'm currently working through a few books on computability and I am having a little bit of trouble with the primitive recursive scheme. When defining the primitive recursive scheme for unary functions ...
0
votes
0answers
45 views

what is the mapping reduction of $A_{TM}$ to $\overline{CF_{TM}}$

first post here :) I am trying to find a reduction from $A_{TM}$ to $\overline{CF_{TM}}$. definitions: $CF_{TM}\:=\:\left\{<M>| M\:is\:a\:TM\:and\:L\left(M\right)\:is\:a\:context-free\:...
2
votes
0answers
47 views

Diagonalization/fixed point lemma in logic vs computability theory

The fixed point/recursion theorem in computability theory and the diagonalization lemma in logic are really similar and the standard proofs of these theorems can be mapped in a one-to-one way (I tried ...
0
votes
1answer
30 views

Application of Generalized Rice's Theorem

I'm trying to understand how to apply the generalized Rice's theorem to prove that a problem is Turing-Recognizable. Suppose that I have two TMs and I have to evaluate if there exists a string that ...
1
vote
0answers
12 views

Question about Proof: Semi-decidable => Recursively Enumerable

Def. A set A is recursively enumerable if $A = \emptyset$ or if there exists a total computable function $g$ such that $A = R(g)= \{z | \exists x. g(x) = z \}$. Def. A set A is semi-decidable if ...
0
votes
1answer
28 views

Compute a series from a sequence

Let's say I have a sequence $s_n$ of numbers, and I want a series $a_i$ which computes the sequence; that is $\sum_{i=0}^\infty a_i n^i = s_n$ Clearly $a_0 = s_0$, but after that I am stuck. I need ...
1
vote
0answers
35 views

Make the language of First Order Logic uncountable

The question is in regards to The Lowenheim-Skolem theorem and the question asks to give a set of sentences that is only true in an uncountable domain. My teacher told me to solve this by "relaxing" ...
0
votes
1answer
28 views

is there a linear bounded automaton the decides $A_{nfa}$?

first post here :) I was wondering, since regular languages are context sensitive, and since linear bounded automatons can act as an acceptors for context sensitive language, is it possible or is ...
19
votes
0answers
229 views

Does “every” first-order theory have a finitely axiomatizable conservative extension?

I've now asked this question on mathoverflow here. There's a famous theorem (due to Montague) that states that if $\sf ZFC$ is consistent then it cannot be finitely axiomatized. However $\sf NBG$ ...
2
votes
0answers
34 views

Is every degree above ${\bf 0''}$ PA over something close to itself?

The low basis theorem says that there are PA degrees which are low - that is, which satisfy ${\bf a'}={\bf 0'}$. Appropriately relativized, given a degree ${\bf a}$ there is a degree ${\bf b}$ "not ...
2
votes
1answer
77 views

What does this notation mean? $\Phi(x) \downarrow, \Phi(x) \uparrow$

I'm not sure how I am supposed to know this, I have never used notation like this in my previous school. Is this notation logic or is it something I should have learned in math class? What I am ...
1
vote
1answer
42 views

What is a “n-valued function”?

Has $n$ parameters? i.e. 0-valued function: $f(\emptyset)=2$ 1-valued function: $f(x)=x$ 2-valued function: $f(x,y)=x+y$ 3-valued function: $f(x,y,z)=x+y+z$ Not sure
0
votes
0answers
12 views

Proof Using Strong Reducibility

I read the following proof so many times and I could not, for the life of me, figure out how the professor went from (1) to (2). I know to prove $\overline{K} \le A$ , where $\overline{K}=\{x:\...
3
votes
1answer
39 views

Diagonal argument applied to computable numbers

Upon applying the Cantor diagonal argument to the enumerated list of all computable numbers, we produce a number not in it, but seems to be computable too, and that seems paradoxical. For clarity, ...
3
votes
1answer
30 views

Redundant definition of computable function on $[a,b]$ in Pour-El and Richard book?

In Pour-El and Richard Computability in Analysis and Physics page $25,$ they defined computable function on $[a,b]$ as follows: Let $[a,b]$ be such that $a$ and $b$ are computable real numbers. A ...
0
votes
1answer
40 views

Definition of Productive set

I don't understand the definition of Productive Set in the Cutland's Computability book. DEFINITION: A set $A$ is productive if there is a total computable function $g$ such that whenever $W_{x} \...
0
votes
0answers
75 views

Counting the points of intersection

A set of equations is given as follows: $$ x^{\Omega}+y^{\Omega}=1 $$ $$ (1-x)^{\Omega}+y^{\Omega}=1 $$ $$ x^\Omega+(1-y)^\Omega=1 $$ $$ (1-x)^\Omega+(1-y)^\Omega=1. $$ $(\Omega\subset\Bbb Q) =\{...
0
votes
0answers
42 views

Is $\{x_{nk}\}$ defined by $x_{nk} = \frac{k}{k+n+1}$ computable?

Currently I am reading Pour-El and Richard Computability in Analysis and Physics. In Chapater $0$, they give a definition of computable double sequence. Definition: A double sequence will be ...
1
vote
1answer
75 views

Does the sequence $(\frac{1}{n})_{n=1}^\infty$ converge to $0$ effectively?

Question: Does the sequence $(\frac{1}{n})_{n=1}^\infty$ converge to $0$ effectively? The definition of effective convergence that I am using is: There exists a computable function $e:\mathbb{N}\...
1
vote
1answer
22 views

A question about the non-transitivity of $\leq_{w\alpha}$

A very natural question when reading about $\alpha$-recursion theory is why and when the weak $\alpha$-reducibility is not transitive. A complete answer to this question can be found in the paper The ...
0
votes
0answers
15 views

How to show directly that Fin = $\{e \colon W_e\textrm{ is finite}\}$ is not c.e.?

How can I show directly that Fin = $\{e \colon W_e \textrm{ is finite}\}$ is not a computably enumerable set? I have been trying to do this directly without alluding to the arithmetical hierarchy and ...