Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computability]

Computability theory a.k.a. recursion theory.

-2
votes
0answers
74 views

Is it there any cellular automata model of the universe where uncomputable things could happen?

There are several papers that propose that the universe itself is analogous to a cellular automata. Obviously, these papers assume that the universe is computable. But is it there any cosmological ...
6
votes
1answer
202 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 ...
-2
votes
0answers
52 views

Is this paper proposing to study uncomputable simulations?

In this paper: https://arxiv.org/abs/1205.1407, the author proposes to study the universe (and possibly multiverses) through computer simulations of universes. But there's one thing I still don't ...
5
votes
1answer
148 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
93 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
115 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
249 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
155 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
192 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
259 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
257 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
82 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
81 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
428 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
515 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
180 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
303 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
139 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
545 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
327 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
446 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
302 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
230 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
101 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
97 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
287 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
415 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
363 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
168 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
85 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
64 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
124 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
514 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
114 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
242 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
294 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
309 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
585 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. -...