Questions tagged [computability]
Computability theory a.k.a. recursion theory.
1
vote
0answers
86 views
Solving the Halting problem for most inputs [closed]
Is it possible to solve the following version of the Halting problem : given any Turing machine and some input tape, the program should answer if this pair halts or not except possibly for one Turing ...
11
votes
0answers
112 views
Can two-tape read-only Turing machines recognize any recursive language?
Suppose that a $k$-tape read-only Turing machine receives its input on each $k$ tapes.
It cannot write on the tapes, but it can move on them in both ways, even move off from the input.
So for example, ...
6
votes
2answers
246 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
153 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
189 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
257 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
254 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
77 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
79 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
423 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
508 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
179 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
300 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
136 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
40 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
116 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
535 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
325 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
31 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
443 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
294 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
226 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
203 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
76 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
100 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
61 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
71 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
95 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
269 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
1k 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
398 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
357 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
167 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
84 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
61 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
120 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
507 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
112 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
241 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
291 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
308 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
173 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
579 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
85 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
237 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
365 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.
...
