Computability theory a.k.a. recursion theory.
6
votes
2answers
226 views
Algorithm for identifying unprovable statements
I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms?
For example: If there ...
2
votes
1answer
148 views
Is there a difference between incompleteness and unknowable? [closed]
Godel proved that there are statements that are true but not provable. Unproven conjectures such "Twin Primes" might fall into such a class, as I understand. If so, does it mean that we will never ...
6
votes
3answers
180 views
Why/when do we ever need transfinite loop variants?
I do not understand why one would ever need a transfinite loop variant.
Why do natural-number-valued variants not suffice? My simple (but perhaps too naive) argument is: if a loop $L$ terminates ...
5
votes
1answer
247 views
Is there a useful notion of being “approximately computable”
It seems that we can define a notion of being “approximately computable” where a set, $S$, is approximately computable if there is a family of computable functions $f_n(x)$ such that $$\lim_{n\to\...
8
votes
1answer
252 views
Non-comparable natural numbers
The "name the biggest number game" asks two players to write down a number secretly, and the winner is the person who wrote down the larger number. The game commonly allows players to write down ...
4
votes
1answer
64 views
Complexity of type-checking in relation to complexity of normalization
In order to verify that a terminating program terminates, one thing that can be done is to actually run the program. That may take a lot of time. If the program is typed in a total type-system, we can ...
2
votes
3answers
72 views
Reference request: Arithmetic circuit complexity
I am completely new to this field. I want to read the prelims and unfortunately, I don't see any book written for a beginner in this area. Can anyone give me some basic starting points/references(text/...
-1
votes
2answers
402 views
Are these problems in NP class?
${\bf New\ version}$ [Version 1.2]
Let $f: \mathbb{N} \to \{0,1\}$ be a computable function, ${\bf Fin}(\mathbb{Z})$ be the set of all finite subsets of $\mathbb{Z}$, and $W: {\bf Fin}(\mathbb{Z}) \...
6
votes
2answers
493 views
a polynomial representation of boolean functions
I came up with this linear transformation to map boolean functions to polynomials and it seems to have some nice properties. I was wondering if there is any reference describing this (and/or similar) ...
1
vote
2answers
172 views
Is true randomness and the physical Church-Turing thesis incompatible?
As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are ...
3
votes
2answers
296 views
Does the physical Church-Turing thesis imply that all physical constants are computable?
The physical Church Turing thesis is a conjecture that any physically computable algorithm can be computed by a Turing machine.
Let us create a machine that, for example, outputs the digits of the ...
-3
votes
1answer
118 views
Is the function undefined everywhere computable? [closed]
We could build the function like these:
$\phi = \lambda x,y.5$
$\psi = \lambda x.(\mu y.(\phi(x,y)=0)$
$\psi$ is a $\mu-recursive$ function so it is computable and its undefined everywhere, but I ...
0
votes
0answers
36 views
Define recursive binary successors and usual successor mutually
It can be read in "Computation Models and Function Algebras", Peter Clote that the class of Polynomial Time functions (PTime) can be defined through the following Function Algebra:
$[z,s_0,s_1,smash,\...
-5
votes
1answer
115 views
Are there proofs which show that AIs are bound to be “worse” than the human brain? [closed]
I was talking with two PhDs (both teach IT related subjects) about artificial intelligence the other day. They were in agreement that an AI can never reach the level of the human brain, but failed to ...
4
votes
2answers
509 views
Enumerating decidable languages
[The assumption in this question is wrong. It is possible to enumerate exactly the decidable languages with semideciders.]
Lets say we have a TM $M_E$ enumerator that writes out codes of TM's on a ...
7
votes
4answers
313 views
Is there a notion of computability on sets other than the natural numbers?
Is there a notion of computability on sets other than the natural numbers? For the sake of argument, let's say on sets $S$ that biject with $\mathbb{N}$.
It's tempting to say "yes, they are those ...
3
votes
0answers
30 views
references for optimal computation under memory constraint?
Can someone help me find some references for finding good execution schedule given memory constraint? Assuming computation graph is simple in some sense (ie, small tree-width)
There is this reference ...
8
votes
4answers
437 views
Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?
In Computability, if we want to prove that a problem is not recursive or not recursively enumerable, we can use e.g. reductions from other non-recursive or non-r.e. problems, Rice's theorem, Rice-...
5
votes
1answer
262 views
Show that minimal CFG is undecidable via mapping reduction
Actually the problem below is an exercise in Sipser's textbook (Problem 5.36). However, from my perspective, it is not so trivial so that I post this question on this site instead of CS.SE.
The ...
13
votes
0answers
222 views
Computability of a “weird” set
The starting point of this question is the observation that the smallest positive integers $a,b,c$ satisfying
$$\frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} = 4$$
are absurdly high. This leads to ...
9
votes
1answer
201 views
Equilibrium in a Halting Game
Consider the following 2-player game:
Nature randomly picks a program
Each player plays a number in [0, infinity] inclusive in response to nature's move
Take the minimum of the players’ numbers, and ...
-1
votes
1answer
75 views
What is the relation between P-immune languages and NP-complete languages? [closed]
Can a NP-complete language be P-immune?
Why can't existence of P-immune languages separate NP from P?
1
vote
1answer
96 views
Set of languages that can represent every c. e. languange
Could we find any set of languages $S$, such that it can represent every c. e. languange as it's union, intersection, complement, production(times of element ), and $S\subset X$, where $X\subseteq c.e....
3
votes
1answer
60 views
Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?
Suppose $L$ is a computably enumerable language, can it be decompose into infinite CFLs with infinite words ?
$$L=\bigcup_{L_i\in CFL }^{\infty}L_i$$
Second question: if it is possible that every $L$...
-1
votes
1answer
69 views
Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?
Is there inherently ambiguous language which can not be recognized by Deterministic LBA?
For example, $L=\{wv: w,v=(x|y)^*, w=w^R,v=v^R\}$, is there any deterministc LBA that recognizes $L$ ?
0
votes
1answer
91 views
Is the relation decidable?
Given an ideal $I$ over $\mathbb{C}$ and P, a polynomial, is it decidable whether $P\in I$?
2
votes
1answer
239 views
Computability Theory prerequisites
What are the prerequisite disciplines for Computability theory? How much is Theory of Computation, Automata Theory, etc and how hard would it be studying it without those prerequisites?
5
votes
1answer
995 views
Is Hartmanis-Stearns conjecture settled by this article?
The paper
"On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited"
by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec
https://arxiv.org/abs/1601....
4
votes
1answer
363 views
Original proof that “almost all decision problems are uncomputable”?
Who gave the original proof that "almost all decision problems are uncomputable"? Any hint at the original paper appreciated, thanks!
12
votes
1answer
349 views
Compressing information about the halting problem for oracle Turing machines
The halting problem is well-known to be uncomputable. However, it is possible to exponentially "compress" information about the halting problem, so that decompressing it is computable.
More precisely,...
8
votes
0answers
165 views
What are considered to be the most canonical and important consequences of the recursion theorem?
The recursion theorem in computability states that, for any computable map $f : \mathbb{N} \to \mathbb{N}$ there exists $n \in \mathbb{N}$ such that $\varphi_{f(n)} = \varphi_n$, where $\varphi$ is a ...
6
votes
0answers
79 views
Small universal monotone Turing machines
This paper surveys small universal Turing machines. What are some examples of small universal monotone Turing machines, as described by Schmidhuber? Which of these are efficient (polynomial time) ...
1
vote
0answers
69 views
Question on Turings Dissertation *Systems of Logic based on Ordinals*, Axiomatic Properties [closed]
I have a question on Alan Turing's Dissertation Systems of Logic Based on Ordinals, a scanned copy you can find here, or rewritten in LaTeX here, and also a copy of the published version here (but in ...
1
vote
0answers
55 views
Relation between MDPs and non-deterministic finite automatons
I'm confused as to the relation (computability-wise) between markov decision processes and NFAs. Are finite state MDPs expressible as regular grammars? If so, are markov decision processes thus ...
1
vote
0answers
119 views
An alternative model of a probabilistic Turing machine [closed]
A probabilistic Turing machine operates with an additional tape of random bits, and its output is a random variable with some distribution over the random bits. Is it also useful to talk about the ...
1
vote
1answer
85 views
Is there a relativized form of Rice Theorem?
Suppose $P_1$ and $P_2$ are nontrivial semantic properties of Turing Machines, and suppose that $P_1\wedge P_2$ is nontrivial given $P_1$. Can one claim that $P_1\wedge P_2$ is undecidable given an ...
2
votes
1answer
484 views
Is simply typed lambda calculus equivalent to primitive recursive functions
It's well known that the computation models untyped lambda calculus and $\mu$-recursive function are equivalent in terms of computability (in fact they are both Turing complete.) It is also well known ...
6
votes
0answers
83 views
Which computational models support bigotous programs?
A bigotous program is a program which decides if its input is semantically equivalent to itself. Of course, this is impossible in a Turing complete language due to Rice's theorem.
In fact, its pretty ...
2
votes
1answer
111 views
About the decidability of sets enumerated in non decreasing order
It is well known that a set of numbers enumerable in nondecreasing order is
decidable. However, the typical proof, by cases on the finiteness of the
enumerated set, is not constructive. In general, it ...
3
votes
0answers
236 views
A sequence wherein the Kolmogorov complexity of the terms does not increase
I am looking for an algorithm $A$ - which for any non-null input string $s_1$ produces a sequence $s_1, s_2...$ such that :
It can be proved in some axiomtic system $S$ that: $\...
13
votes
1answer
286 views
Gap between $BB(n)$ and “second largest” $BB(n)$
If $HT(n)$ is the set of halting times of $n$-state Turing machines on a binary alphabet with empty initial tape, then $BB(n) = \max HT(n)$.
What can we say about the second largest number in $HT(n)$...
7
votes
1answer
302 views
Where does the “intuitive” understanding of Kolmogorov complexity fails
Often, the Kolmogorov complexity of some string $x$ is defined as the length of the shortest program producing $x$, for example on wikipedia.
So to give this more formal meaning, define
$$
K'(x) := ...
7
votes
1answer
170 views
Is there a formulation of Rice's Theorem that does not involve admissible (or Gödel) numberings?
It is an easy task to devise an encoding for a computing formalism (such as Turing Machines) that has a function with fixed encoding. That is, the encoding is a numbering $\psi : \mathbb{N} \...
18
votes
1answer
566 views
Does the uncomputability of Kolmogorov complexity follow from Lawvere's Fixed Point Theorem?
Many theorems and "paradoxes" - Cantor's diagonalization, undecidability of hatling, undeciability of Kolmogorov complexity, Gödel Incompleteness, Chaitin Incompleteness, Russell's paradox, etc. -...
0
votes
1answer
81 views
Enumerator for the language w#w^R? [closed]
I'm trying to build a Turing machine diagram for the language w#w^R, where w^R is the reverse of w, and w is a word made up of 0's and 1's. I'm trying to think of an algorithm but I can't think of ...
11
votes
1answer
236 views
Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)
The first term is used by Hilbert in his 1928 work, but in Gödel's later work, the same thing is referred to as Unvollständigkeitssatz ("incompleteness theorem"). For today's German CS researchers, it ...
6
votes
2answers
322 views
In the context of regular languages, must the alphabet be finite?
In The Theory of Parsing, Translation, and Compiling, Volume I, Section 0.2.1 (p.15 / 1972), Aho and Ullman casually write that "[a]n alphabet need not be finite or even countable, but for all ...
9
votes
1answer
118 views
About the origin of the names “immune” and “simple”
I have been wondering for a while about the origin of the names "immune"
and "simple". I also posed the same question to Andrea Sorbi, who in turn
involved a few more colleagues in the discussion.
...
2
votes
1answer
58 views
Characterisation of computability of partial functions from infinite words into finite words by functions with prefix-free domain
The following is taken from K. Weihrauch, Computable Analysis, page 21. The notation $f : \subseteq A \to B$ means a partial function. By $\Sigma^{\omega}$ and $\Sigma^{\ast}$ we denote the set of ...
5
votes
1answer
158 views
Is the Komolgorov complexity of the truth tables of the halting problem known asymptotically?
Let $HALT_n$ denote the string of length $2^n$ corresponding to the truth table of the halting problem for inputs of length $n$.
If the sequence of Komolgorov complexities $K(HALT_n)$ were $O(1)$, ...
