Questions tagged [computability]
Computability theory a.k.a. recursion theory.
346
questions
1
vote
1answer
115 views
How come Wikipedia says that Random Turing Machines can provide uncomputable output?
Wikipedia article mentioned : Hypercomputation
The third paragraph starts off with:
Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses ...
1
vote
1answer
108 views
What kind of computational model is the brain? [duplicate]
I was wondering what kind of computational model is the human brain (as it seems superior to a Turing machine).
Another thing that should be a separate question, What would be a perfect computer model ...
12
votes
2answers
323 views
Complexity relative to the graph of the Busy-Beaver function
This question is inspired by the comments made on this other question that I asked, and by an attempt to provide an explicit example of a complexity question beyond the Turing degree $\mathbf{0}$. (...
5
votes
0answers
168 views
Has there been any development of complexity theory for other Turing degrees than 0?
(I'm not sure if this question is better suited for MathOverflow or here. I'll try here first, and move over to MO later if it appears to be more appropriate.)
Complexity theory can be very broadly ...
1
vote
0answers
47 views
Given a program specification, S, what can be said about the size and efficiency of programs that exactly satsify S, with respect to the size of S?
Suppose we are given a program specification, $S$, and we want to reason about programs $P$ that satisfy $S$. One might like to think that if the specification is 'simple', the the program should be '...
1
vote
0answers
74 views
Logic of learning
Does Robust logic (Leslie Valiant), Default logic (Raymond Reiter) and Circumscription logic (John McCarthy) have any relation?
I was Mathematician and Computer Science (dual degree undergraduate) ...
-2
votes
1answer
68 views
Definition of Omega Jump [closed]
In the book Computability theory (Rebecca Weber) I stumbled about Exercise 7.1.24 with the definition of the omega jump.
The book says:
The omega jump of $A$, $A^{(\omega)}$ is the join of all $A^{(n)}...
1
vote
0answers
29 views
Non Turing-Complete Models, Conditional-Complete function?
I know well the distinction between the class of Partial Recursive Functions, and $\mu$-Recursive, i.e. the latter is Turing Complete and the former is equivalent to the LOOP-Program model of ...
0
votes
0answers
76 views
Apredictable sets
Some strange recursion-theoretic notions I encountered, I am unable to make much sense out of them. Some concrete questions below, but I'm also interested in just connections to existing recursion ...
-3
votes
1answer
97 views
Is this a good definition of computability? [closed]
I still haven't found a good definition of computability. All the definitions are either too vague, or they delegate the definition to another loaded term like "anything that uses math to solve a ...
1
vote
1answer
141 views
Extended Church's thesis and internal parametricity
I am wondering if there is any known relationship between these 2 concepts in intensional MLTT as formulated here.
Does $Internal\ parametricity \implies ECT$ hold?
For forumlation of ECT see https://...
0
votes
2answers
157 views
Is the decidability of a language decidable? [closed]
Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language?
Comments + answer say trivially the answer is yes; however, I'm wondering here would ...
0
votes
2answers
146 views
Turing meta-oracle
Let H(P) be some program that given P('s source code) computes whether or not P terminates, i.e. solves the halting problem. H only needs to terminate if P terminates. (This disallows solutions like ...
1
vote
0answers
44 views
Is there an alternative technique to define computable functions other than their definition on natural numbers? [closed]
I am not completely sure that why computable functions is defined as a subset of all functions from/to Natural Numbers, but as far as I know, computation comes from real (physical) world so ...
5
votes
0answers
79 views
Are there languages require many variables to achieve $\Sigma_n^0$ completeness?
The proof of Post's Theorem that I am familiar with assumes you have access to as many variables as you wish in your language. Matiyasevich's Theorem by contrast gives a $\Sigma_n^0$-complete formula ...
-1
votes
1answer
126 views
Gödel-Numbering of the Context-Sensitive Languages
I would like to have a Gödel-numbering of the context-sensitive languages. Because there is no obvious syntactic distinction between LBAs and TMs, I cannot number the former in an immediate way. So I ...
6
votes
1answer
239 views
Uniform mortality problem for Turing Machines
Consider the following generalisation of the mortality problem for Turing Machines.
Given a Turing Machine $M$. Is there a bound $k_M$ such that starting
from any configuration $c$ machine $M$ ...
3
votes
2answers
166 views
Compactness of domino tilings
I've read in Lemma 2 of the paper 1 that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted. This sounds like a compactness property, ...
2
votes
0answers
78 views
how is time complexity defined in computational learning theory
In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$.
Now ...
-1
votes
1answer
142 views
Why does the Placid Platypus function grow faster than any computable function?
I came across the Placid Platypus function $PP(n)$ today, defined as the minimal number of states needed for a turing machine that prints a string of $n$ ones and halts. This function is claimed to (...
6
votes
1answer
298 views
Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?
Disclaimer: I am mostly unfamiliar with theoretical computer science, making it hard for me to navigate literature in the field. I ask the following out of curiosity.
Background/Motivation: Coming ...
5
votes
1answer
175 views
Minimal information needed for determine some function
From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of ...
1
vote
0answers
149 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
160 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
276 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
173 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
223 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
287 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\...
11
votes
1answer
533 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
159 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
166 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
670 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
733 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
227 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
345 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 ...
-5
votes
1answer
136 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
813 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 ...
10
votes
4answers
467 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 ...
3
votes
0answers
32 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
477 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-...
4
votes
1answer
773 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
252 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 ...
10
votes
1answer
244 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
88 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
111 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
69 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
75 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
139 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
478 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?
4
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....
