50
votes
Accepted
What functions can System F not compute?
System $F$ is quite expressive. As proved by Girard here, the functions of type $\mathbb{N}\rightarrow\mathbb{N}$ (where $\mathbb{N}$ is defined to be $\forall X.\ X\rightarrow (X\rightarrow X)\...
- 13.2k
48
votes
Accepted
A total language that only a Turing complete language can interpret
This is a badly phrased question, so let's first make sense of it. I am going to do it the style of computability theory. Thus I will use numbers instead of strings: a piece of source code is a number,...
- 26.7k
22
votes
A simple decision problem whose decidability is not known
It is unknown whether or not
it is decidable to determine if a given shape can tile the plane,
even for polyomino tiles.
(...
- 3,703
22
votes
Accepted
How exactly does lambda calculus capture the intuitive notion of computability?
You're in good company. Kurt Gödel criticized $\lambda$-calculus (as well as his own theory of general recursive functions) as not being a satisfactory notion of computability on the grounds that it ...
- 26.7k
21
votes
A total language that only a Turing complete language can interpret
Any language which is not Turing complete can not write an interpreter for it self.
This statement is incorrect. Consider the programming language in which the semantics of every string is "Ignore ...
- 2,725
21
votes
Importance of irrational numbers in computer science
The question displays a fundamental misunderstanding about the nature of what can be done with computers. To correct this misunderstanding, I suggest getting a copy of the computer algebra software ...
- 6,898
18
votes
Accepted
Is there algorithmic mathematical analysis?
Check out
the Computability and Complexity in Analysis network. Quote:
The topics of interest include foundational work on various models and approaches for describing computability and complexity ...
- 4,400
18
votes
Importance of irrational numbers in computer science
You're assuming that numbers can only be represented as fractions (either literally, by having a datatype storing integer numerator and denominator, or implicitly by using some kind of floating point ...
- 2,725
18
votes
Accepted
Is Hartmanis-Stearns conjecture settled by this article?
First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn".
Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in ...
- 6,898
17
votes
Accepted
For a random oracle R, does BPP equal the set of computable languages in P^R?
Yes.
First, since it took me a minute to figure this out myself, let me formalize the difference between your question and $\mathsf{AlmostP}$; it's the order of quantifiers. $\mathsf{AlmostP} := \{L :...
- 35.8k
17
votes
Why study type theory?
Type theories in which every type is inhabited are far from being useless. True enough, through the eyes of logic they are inconsistent, but there are other things in life apart from logic.
A general ...
- 26.7k
17
votes
Accepted
Is the Kolmogorov complexity of the truth tables of the halting problem known asymptotically?
Hmm, turns out there's actually an matching upper bound that isn't too hard:
To produce the truth table $HALT_n$ in a finite amount of time, the only information that is needed is the number of ...
- 371
17
votes
Accepted
Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)
The two words do not refer to the same thing. Hilbert's Entscheidungsproblem was the question whether there is an algorithm that decides the universal truth of first-order logical sentences, which was ...
- 4,511
16
votes
Accepted
To what extent can the mathematics of Reals be applied to Computable Reals?
The real numbers may be characterized in a couple of ways, let us work with the Cauchy-complete archimedean ordered field. (We need to be a bit careful how exactly we say this, see Definition 11.2.7 ...
- 26.7k
16
votes
Accepted
A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise
This is not a research-level question, but since the general level of interest seems high, here is an answer. I cannot guess from your question whether you're shooting for something that will result ...
- 26.7k
15
votes
Importance of irrational numbers in computer science
I can see why the question is being downvoted, but this is too good not to post. Suppose you have a coin with bias $p\in[0,1]$, which might be rational or irrational. Question: using only finite ...
- 10.1k
14
votes
Accepted
Was bombe machine turing complete?
No, the bombe was very specific. It consisted of a bunch of enigma machines hooked together. It was very limited in its use. A more interesting question is whether the Colossus computer, also used in ...
- 14.1k
14
votes
Does the uncomputability of Kolmogorov complexity follow from Lawvere's Fixed Point Theorem?
EDIT: Adding the caveat that Roger's fixed-point theorem may not be a special case of Lawvere's.
Here is a proof that may be "close"... It uses Roger's fixed-point theorem instead of Lawvere's ...
- 8,273
13
votes
How to judge the definition of computational complexity of reals is natural or suitable?
I am not exactly sure what the question is here, but I can try to say a bit to clean up possible misunderstandings.
First of all, if we are talking about complexity of a map $f : \mathbb{R} \to \...
- 26.7k
13
votes
Is there a result in computability theory that does not relativize?
Higman's Embedding Theorem: The finitely generated computably presented groups are precisely the finitely generated subgroups of finitely presented groups. Furthermore, every computably presented ...
- 35.8k
13
votes
Is there a notion of computability on sets other than the natural numbers?
This question is not research-level, but since it is receiving answers, I would like to offer an answer that may actually clear things up a bit, and provide references.
There is an entire area of ...
- 26.7k
13
votes
Accepted
Computability and continuity
Let $L_1 = L_2 = \mathbb{N}$ and let $M \subseteq \mathbb{N}$ be a maximal set and let $L = \mathbb{N} \setminus M$ be its complement. Recall that $L$ is infinite, and that every computably enumerable ...
- 26.7k
12
votes
Is there algorithmic mathematical analysis?
(Disclaimer: I am not an expert, feel free to suggest corrections, or write a more comprehensive answer if you are.)
Extending computability and complexity to the real numbers (which is a first step ...
- 18k
12
votes
Accepted
Is there a useful notion of being “approximately computable”
If the family function $f(x,n)=f_n(x)$ is computable then these are exactly the $\Delta^0_2$ functions, or equivalently, the functions that are Turing reducible to the halting set $0'$, which are very ...
- 4,400
12
votes
Why/when do we ever need transfinite loop variants?
You are correct when you observe that for any particular terminating loop $L$ we may simply define the invariant "we're getting one step closer to termination". But proving that this is indeed a valid ...
- 26.7k
11
votes
A simple decision problem whose decidability is not known
A problem from Automata Theory.
Input: A DFA $D$ over a binary input alphabet.
Question: Does there exist a bit string $x$ such that $D$ accepts $x$ and $x$ represents a prime number in binary? In ...
- 4,900
11
votes
What functions can System F not compute?
It is somewhat misleading to say that Haskell's typing system is "the hinley-milner type system". Haskell's types are much more powerful, including, among others, higher-kinded types. Indeed the ...
- 10.3k
11
votes
Accepted
Proof for Kolmogorov complexity is uncomputable using reductions
You can find two different proofs in:
Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Program-size Complexity Computes the Halting Problem. Bulletin of the EATCS 57 (1995)
In Li, Ming, Vitányi, ...
- 22.3k
11
votes
An example where smallest normal lambda term is not fastest
Blum’s speedup theorem is usually stated in the language of partially recursive functions, but up to trivial differences in notation, it works just the same in the language of $\lambda$-calculus.
It ...
- 14.8k
11
votes
Accepted
Equilibrium in a Halting Game
Even if you have a one-player game there is no computable equilibrium. Consider nature putting probability $1/2^i$ on program $i$. Any computable strategy will achieve some value strictly less than ...
- 8,546
Only top scored, non community-wiki answers of a minimum length are eligible