All Questions
Tagged with computability-theory computer-science
96 questions
5
votes
1
answer
469
views
Is the set of generalized Fermat triples computable?
Is $\;\big\{(a,b,c)\in\mathbb{N}^3: \big(\exists m,n,\ell \in (\mathbb{N}\setminus\{0,1,2\})\big): a^m + b^n= c^\ell\big\}\;$ computable?
- 48.9k
3
votes
0
answers
146
views
Lower Bound of Solutions to P=NP?
Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with ...
- 3,029
2
votes
0
answers
78
views
Is this variant of post correspondence problem undecidable?
The post correspondence problem, as defined by wikipedia, is undecidable. The problem is defined as follows.
Let $A$ be an alphabet with at least two symbols. The input of the problem consists of ...
- 21
35
votes
3
answers
5k
views
Using Busy Beavers to prove conjectures
I've been pondering some stuff on Shtetl Optimized where Yedidia and Aaronson construct Turing machines that will only halt if (e.g.) the Riemann Hypothesis is false, or Goldbach's conjecture is false....
- 483
3
votes
1
answer
308
views
Root finding algorithm for an analytic function
Given an analytic function $f(x)$. What is the best algorithm to find roots on the interval $[a,b]$ inside the radius of convergence> What is its complexity with respect to the length of input of ...
- 81
4
votes
0
answers
214
views
Computational complexity of zeros of an analytic function
The work of Friedman and Ko, page 342, Corollary 4.3.1
states that all zeros of analytic polynomial time computable function are polynomial time computable, but for me that is not clear how it could ...
- 81
1
vote
0
answers
116
views
Sudden drop in complexity class due to the more general correlations
Recently I was asking about the impact of the groundbreaking result MIP*=RE on logic and proof theory (see this discussion). Surprising as it is I got confused with the following: MIP* is a ,,quantum''...
- 9,330
4
votes
4
answers
472
views
Automatically generating combinatorial conjectures
It very often happens that one reduces a problem to a bunch of combinatorial data, and need to sift through this data for patterns, which form conjectures on which to do "real" mathematics. ...
- 341
0
votes
1
answer
115
views
Non-isomorphic graphs with identical iterated degree matrix
If $G = (V, E)$ is a simple, undirected graph and $T \subseteq V$, let $$N(T) = \{v \in V: \{v, t\}\in E \text{ for some }t\in T\}.$$
Given $v\in V$ we let $N_0(v) = \{v\}$ and $N_{k+1}(v) = N_k(v) \...
- 48.9k
0
votes
1
answer
312
views
Can finite sets be non-c.e. depending on how they are presented?
I ask the question because of the following statement found in Mark Burgin's paper, "Algorithmic complexity of recursive and inductive algorithms", Theoretical Computer Science 317 (2004) 31-...
- 6,132
2
votes
1
answer
169
views
Busy beaver sequence for a simple tag-like system
This question arose in the context of tag-like systems, specifically Bitwise Cyclic Tag (BCT). Consider the following discrete dynamical system:
Let $\mathbb{B} = \{\mathtt{0}, \mathtt{1}\}$. Let our ...
- 2,203
2
votes
0
answers
133
views
Is this variant of bitwise cyclic tag Turing-complete? [closed]
Cross-posted from Theoretical Computer Science.
CT is an extremely minimalist programming language that can simulate arbitrary tag systems, and is therefore Turing-complete. A program consists simply ...
- 2,203
0
votes
1
answer
267
views
Algorithmically decide if an algorithm has optimal time complexity [closed]
Is there an algorithm with the following input and output?
INPUT: an algorithm computing a function $\mathbb{N}\to\mathbb{N}$. The algorithm is guaranteed to halt on all inputs.
OUTPUT: "YES"...
- 1
2
votes
1
answer
361
views
Can primitive recursive functions be simulated in the smallest reasonable primitive recursive group?
Second Edition, completely rewritten with unchanged questions.
The said questions are motivated by the bizarre wording of the concluding § in A Class of
Reversible Primitive Recursive Functions by L. ...
- 347
2
votes
1
answer
278
views
Is good reduction decidable?
Let $X$ be a smooth projective geometrically connected variety over $\mathbb{Q}$. It is said to have good reduction at a prime $p$ is there is a smooth projective $\mathcal{X}\to \mathrm{Spec}\:\...
user158636
34
votes
9
answers
6k
views
Decision problems for which it is unknown whether they are decidable
In computability theory, what are examples of decision problems of which it is not known whether they are decidable?
0
votes
1
answer
81
views
Normal $0,1$-sequence with infinitely many frequent finite substrings
Let $\mathbb{N}$ denote the set of non-negative integers. We can identify every bitstream, i.e. a function $s:\mathbb{N}\to \{0,1\}$, with some $A\in{\cal P}(\mathbb{N})$: take $A = s^{-1}(\{1\})$.
...
- 48.9k
4
votes
1
answer
160
views
Is sum-balanceability computable?
Let $\mathbb{N}$ denote the set of positive integers, and let $G=(V,E)$ be a finite simple, undirected graph. Given $f:V\to \mathbb{Z}$ we define the neighborhood
sum function $\mathrm{nsum}_f:V\to\...
- 48.9k
2
votes
0
answers
103
views
Buridan's principle in computable analysis
In (Lamport, 2012), Lamport proposes the principle
A discrete decision based upon an input
having a continuous range of values cannot be made within a bounded length of time.
I think it could be ...
2
votes
1
answer
152
views
Computationally random bitstreams and normalcy
Let $\mathbb{N}$ denote the set of non-negative integers. We can identify every bitstream, i.e. a function $s:\mathbb{N}\to \{0,1\}$, with some $A\in{\cal P}(\mathbb{N})$: take $A = s^{-1}(\{1\})$.
...
- 48.9k
13
votes
0
answers
257
views
Is the set of power matrices decidable?
Let $\text{Mat}(n\times n,\mathbb{Z})$ denote the collection of integer $n\times n$ matrices. We say $M\in \text{Mat}(n\times n,\mathbb{Z})$ is a power matrix if there is an integer $k>1$ and a ...
- 48.9k
3
votes
1
answer
767
views
does recursive (decidable) languages closed under division (Quotient) with any language?
I need to prove or disprove that R languages are closed under divison.
I have managed to prove thet CFL are't closed under division. I read in wikipedia that RE languages are closed, but I didn't find ...
- 51
2
votes
1
answer
69
views
Compute the hull of nonnegative linear combinations of a finite set, and the extreme points of the intersection of two polyhedra
Let $\mathbb{R}^d$ be $d$-dimensional Euclidean space
Let $\Delta=\{x\in\mathbb{R}^d_+:\sum_{i=1}^dx^i\leq1\}$ ($x^i$ is the i-th coordinate of $x$)
(Equivalently, $\Delta$ is the convex hull of $\{(0,...
- 159
2
votes
1
answer
162
views
Is this cycling problem computable?
We have a group of $n$ people who must make a journey of length $d$. They are to start together, and their goal is to arrive at the destination at same time. They have a single bicycle, which they ...
- 48.9k
27
votes
3
answers
2k
views
Defining computable functions categorically
Computable functions may be defined in terms of Turing machines or recursive functions, or some other model of computation. We normally say that the choice doesn't matter, because all models of ...
- 1,344
6
votes
1
answer
216
views
A "dense" extension of the set of primitive recursive functions
Let $\mathcal{PR}$ be the set of primitive recursive functions. Let $\mathcal{PR}(f)$ be $\mathcal{PR}$ which we have amplified by adding (a recursive) $f$ the in the set of initial functions. To make ...
user39297
4
votes
2
answers
591
views
Connection between countable ordinals and Turing degrees
$\omega^{CK}_1$ is the supremum of all the recursive ordinals, where an ordinal $\alpha$ is recursive if there is a computable ordering of a subset of the naturals with order type $\alpha$.
For a ...
- 6,353
2
votes
2
answers
169
views
Decidability of matrix problem in ${\mathbb Z}/p{\mathbb Z}$
Let $p$ be a prime number, $n$ be a positive integer, and let ${\mathbb Z}_p^{n\times n}$ denote the set of $n\times n$-matrices over ${\mathbb Z}/p{\mathbb Z}$.
Suppose we are given an integer $m>...
- 48.9k
20
votes
2
answers
2k
views
Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$
As we know, there are lots of consequences with the presupposition of the Riemann Hypothesis.
Similarly, are there any important consequences with the presupposition of $\mathbf{P} \neq \mathbf{NP}$ ?...
5
votes
1
answer
277
views
Program analysis for Turing machines
What is considered the state-of-the-art on program analysis (static and dynamic) for Turing machines? What references can I consult for this problem?
I am thinking of things like determining whether ...
- 2,203
6
votes
2
answers
251
views
Are there recursive sets $X$ with Property A that contain infinitely many incompressible strings?
Let us say a set $X$ satisfies Property A if$$\liminf_{n \to \infty} {{\left|X^{\le n}\right|}\over n} = 0.$$Are there recursive sets $X$ satisfying Property A that contain infinitely many ...
- 63
2
votes
0
answers
113
views
Description of all total recursive functions where operator is effective?
What is a description of all total recursive functions $g(x)$ for which the operator$$\Phi_g: \mathcal{F}_2 \to \mathcal{F}_1$$defined by the formula$$\Phi_g(f)(x) := g(\mu y(f(x, y) = 0))$$is ...
- 45
-2
votes
1
answer
252
views
why do the Computability theory choose the natural number as the object of study? [closed]
I am wondering why the computable function is defined in the natural number set. Can people give me the answer or some resources that can solve my puzzle.
- 23
7
votes
2
answers
599
views
Is there a noncomputable set which can be described by a probabilistic Turing machine with bounded error?
Does there exist any noncomputable set $A$ and probabilistic Turing machine $M$ such that $\forall n\in A$ $M(n)$ halts and outputs $1$ with probability at least $2/3$, and $\forall n\in\mathbb{N}\...
- 2,130
-3
votes
3
answers
338
views
Can we decide whenever a function is the derivate of another function in this Language?
Our EXP functions are made in the following way:
Any constant $ \in \Bbb R$ is a EXP
$X \in \Bbb R$ is a EXP
$sin( g(x))$, $cos( g(x))$ are in EXP if $g(x)$ is a EXP
$tan( g(x))$ is a EXP if $g(x)$...
4
votes
2
answers
155
views
Are there complexity classes X weaker than the linear time hierarchy such that any r.e. set is a coordinate projection of a set in X?
If $A\subseteq\mathbb{N}$ is recursively enumerable, then there is a $\Delta^0_0$ set $B\subseteq\mathbb{N}^2$ such that $A=\{x|\exists y\;(x,y)\in B\}$. $\Delta^0_0$ consists of exactly the sets in ...
- 2,130
23
votes
1
answer
6k
views
What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?
In this article, Scott Aaronson talks about using Turing Machines for proving the Rosser Theorem.
What is the relationship between the numbering that Gödel used in his proof of incompleteness and ...
- 333
18
votes
1
answer
1k
views
Is it possible to make an algorithm that could predict the likelihood that a program will halt?
Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...
- 313
2
votes
2
answers
624
views
Time Hierarchy Theorem and P vs NP
One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...
- 99
16
votes
2
answers
816
views
Can a stochastic Turing machine output a consistent extension of PA with positive probability?
Suppose that we interpret the output tape of a Turing machine as an assignment of true or false to all sentences of PA, taking the $n$th output bit as the truth value of the sentence with Goedel ...
- 163
4
votes
1
answer
176
views
What class of probability distributions do probabilistic turing machines induce? [closed]
What class of probability distributions is induced by the class of probabilistic turing machines? Is there a precise characterization?
- 41
15
votes
0
answers
425
views
Complexity classes for BSS machines
Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where
Cells on the tape can hold arbitrary elements of $\mathcal{S}$.
The ...
- 21.2k
3
votes
1
answer
446
views
floating point representation via the perspective of TTE/computable analysis
Floating point numbers are not compatible with the usual theory of type 2 theory of effectivity (TTE), and not even the real-RAM model; there are functions that are computable in one model but not ...
- 459
-1
votes
1
answer
550
views
Are limits decidable? Should definitions be decidable? [closed]
This question is about the Turing computability of the $\epsilon-N$ definition of a limit of an infinite sequence $S$. First, a proposition:
There cannot exist a Turing Machine $M$ which, given a ...
- 718
7
votes
1
answer
258
views
Oracle queries asked in parallel
Definition: Assume that $\phi(q)$ is of the form $\exists y \leq 2^{p(n)} \varphi(q,y)$, where $p$ is a polynomial and $n = |q|$ (i.e. $n$ is the length of the binary representation of $q$). Then a ...
11
votes
2
answers
950
views
Define Turing machine with algebraic concepts/structures
Usually, during lectures Turing Machines are firstly introduced from an informal point of view (for example, in this way) and then their definition is formalized (for example, in this way).
Is it ...
user60665
0
votes
0
answers
105
views
Counting path generating sentences in a specific formal language
Given a formal grammar of a language or an Turing machine of the language, can we count the path that generating sentences of the language?
For example, we know that if the grammar is context-free ...
- 3,094
-1
votes
2
answers
534
views
Can an algorithm decide whether a program computes all strings? [closed]
I am interested in the type of program, which is given as input to a Universal Turing Machine (UTM) with language $L$, and for which it holds that every possible finite string $s$ of symbols in $L$ ...
- 67
2
votes
2
answers
181
views
Background for Kierstead terms
I was looking at some slides of John Longley's here, where he mentions "the Kierstead functional"
$$\lambda f.f(\lambda x.f(\lambda y.x)) \ ,$$
(where $f$ should be of type $2$, and $x,y$ of ground ...
- 269
1
vote
1
answer
185
views
Total conditional complexity
By $C(|)$ denote conditional complexity.
By $CT(|)$ denote total conditional complexity.
For every n there exist two strings $x$ and $y$ of length $n$ such that $C(x|y) = O(1)$
but $CT(x|y) \ge n $.
...
- 2,576