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

0
votes
0answers
8 views

pspace-complete definition variation with cubic space(theoretical)

i've been wondering: if we change the definition of a PSPACE-COMPLETE definition to the following: A language B will be called PSPACE-COMPLETE if: for each language A in PSPACE: $A \leq _{CS} B$ ...
1
vote
0answers
32 views

Who wins Life and Antilife?

In Life and Antilife, players A and B take turns changing up to $n$ and $m$ cells respectively in an $s$ by $s$ toroidal grid. If after any turn, running a Conway's Game of Life simulation with that ...
0
votes
1answer
46 views

Issue regarding computable functions in Godel's Incompleteness Theorem.

$L$ is the set of all finite length strings. Some subset of $L$ are legitimate computer programs, call this set $F$. Some subset of $F$ are functions that turn a Natural Number into a 1 or 0, call ...
0
votes
1answer
21 views

What are the conclusions we can draw from Kleene's Recursion Theorem regarding computability?

Kleene's Recursion Theorem in his Introduction to Metamathematics $\S66$ is written Theorem XXVI: For any $n\geq0$, let $\textbf{F}(\zeta;x_1,...,x_n)$ be a partial recursive functional, in which ...
1
vote
0answers
25 views

Is every not recursively enumerable set also productive?

I understand that every productive set is not recursively enumerable, but is the other way around also true? If not, what is an example of a set which is not r.e. but not productive? Update: The ...
0
votes
0answers
31 views

is there a definition of Turing computability for multivariate functions?

Suppose we have a function $f:\omega^{n}\rightarrow\omega^{m}$ with $n,m\in\omega$ with $n,m\geq 1$ for which there exists a Turing machine that on input $(k_{1},...,k_{n})$ produces $f(k_{1},...,k_{n}...
2
votes
2answers
71 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
23 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
21 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
19 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
39 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
65 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
33 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
27 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
38 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
14 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
71 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
35 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
234 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
39 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
33 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
58 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
91 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
50 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
49 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
67 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
93 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
54 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
156 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
52 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
38 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
81 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
51 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
33 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
13 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
29 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
37 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
29 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
239 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
36 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
78 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
43 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
13 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
41 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 ...