Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
Jeffrey Shallit's user avatar
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 ...
David Richerby's user avatar
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 ...
Jeffrey Shallit's user avatar
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 ...
Chris Beck's user avatar
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 ...
Jan Johannsen's user avatar
16 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 ...
Aryeh's user avatar
  • 10.6k
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 ...
Andrej Bauer's user avatar
  • 29.1k
15 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 ...
Andrej Bauer's user avatar
  • 29.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 ...
Neal Young's user avatar
  • 10.8k
13 votes

How is proving a context free language to be ambiguous undecidable?

The answer by apolge presents the proof that it is undecidable whether an arbitrary context free grammar is ambiguous. The question of whether a context free grammar defines an inherently ambiguous ...
Michael Burke's user avatar
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 ...
Joshua Grochow's user avatar
13 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 ...
Andrej Bauer's user avatar
  • 29.1k
13 votes
Accepted

Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?

The answer is yes. This was proved by Hanf (Model-theoretic methods in the study of elementary logic, in the Theory of models volume). A "uniform" version of this result was conjectured by ...
Noah Schweber's user avatar
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 ...
Andrej Bauer's user avatar
  • 29.1k
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 ...
Bjørn Kjos-Hanssen's user avatar
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 ...
Lance Fortnow's user avatar
10 votes

Importance of irrational numbers in computer science

Even if you're not trying to compute them, irrational numbers arise throughout computer science, particularly in the analysis of the complexity of algorithms. For example, if you want to know how ...
Tad's user avatar
  • 239
10 votes

Does the physical Church-Turing thesis imply that all physical constants are computable?

You appear to be positing a universe where (a) the fine-structure constant has an exact value and (b) we can measure as many digits of it as we want. Thus, if a Turing machine cannot compute the exact ...
Peter Shor 's user avatar
10 votes

Does every computable function have infinitely many "non-padded" representations?

Given any computable function $f : \mathbb{N} \to \mathbb{N}$ the set of its indices $S_f = \{n \in \mathbb{N} \mid \phi_n = f\}$ is for all practical purposes "the set of all programs computing $...
Andrej Bauer's user avatar
  • 29.1k
9 votes

In the context of regular languages, must the alphabet be finite?

It makes sense in some contexts in mathematics to consider strings or languages over infinite alphabets. For instance, this concept is used in the strong version of Higman's lemma. But a finite ...
David Eppstein's user avatar
9 votes

Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?

The standard comparison-model lower bound for sorting, and most cell probe model lower bounds for data structures, are unconditional (for computing within the model but you could say the same about ...
David Eppstein's user avatar
9 votes
Accepted

Enumerating decidable languages

You can enumerate exactly the decidable languages. I've given this question as a homework problem so I'll just give a hint here: You can modify a TM $M$ to a machine $M'$ such that if $M$ is total (...
Lance Fortnow's user avatar
9 votes
Accepted

a polynomial representation of boolean functions

Well done on your independent discovery. This is a Hadamard matrix of Sylvester type, written in a different order. There is a massive literature on this topic. It is used in coding theory, ...
kodlu's user avatar
  • 2,070
9 votes
Accepted

Non-comparable natural numbers

When you say "undecidable" I assume you mean it is independent of a theory such as ZFC. There will be statements like $$B(m)>n$$ (for natural numbers $m$, $n$) that are not decided by ZFC, assuming ...
Bjørn Kjos-Hanssen's user avatar
9 votes

Why/when do we ever need transfinite loop variants?

I would like to add the following to Andrej's response (not enough rep for a comment). Indeed, we cannot avoid ordinals but we may hide them. One approach is to use some modal logic that takes ...
Henning Basold's user avatar
9 votes

Is there a difference between incompleteness and unknowable?

Yes, there is a difference. Incompleteness is a property of a formal system logic. Given a formal system $L$, we say that it is incomplete if there is a sentence $S$ such that $L$ does not prove $S$ ...
Andrej Bauer's user avatar
  • 29.1k
9 votes
Accepted

Proof and computational complexity

Maybe the keyword you are looking for is "Implicit Complexity". It is more general than Curry-Howard correspondence, but several lines of research investigate along the axis you are ...
Denis's user avatar
  • 8,893
9 votes
Accepted

What is the complexity class of higher-order primitive recursion?

If I understand correctly, the primitive recursive functionals defined in the Wikipedia page linked in the question coincide with Gödel's system T, which is well-known to correspond to the class of ...
Damiano Mazza's user avatar
8 votes
Accepted

Can all mathematical operations be encoded with a Turing Complete language?

But I've come away looking for proof. How do we know all this covers all computable functions? Is there an obvious branch of Mathematics for which this is not covered? Is there a shortcoming in Lambda ...
Neel Krishnaswami's user avatar
8 votes
Accepted

Is there any relationship of hardness between the two problems?

No, you cannot infer hardness of P1. (And your question looks suspiciously close to homework.) Consider the special case where $D$ is an undirected graph $G=(V,E)$ $x$ is a subset $E_x\subseteq E$ $...
Gamow's user avatar
  • 5,772

Only top scored, non community-wiki answers of a minimum length are eligible