User antonio e. porreca - MathOverflow

Answer by Antonio E. Porreca for What is some good introduction to lambda calculus?

2011-07-02T19:32:39Z

An introductory book that seems very nice to me is Lambda-Calculus and Combinators. An introduction by J. Roger Hindley and Jonathan P. Seldin.

Has there ever been a weaker Church-like thesis?

2010-07-06T19:38:49Z

Background. The Church-Turing thesis, in one of its many equivalent formulations, states that the intuitively computable arithmetical functions are exactly those computed by Turing machines.

According to Alan Turing’s classic paper On computable numbers, with an application to the Entscheidungsproblem, “intuitively computable” refers to a human computer having access to enough scratch paper to hold the intermediate results.

This thesis has been extremely successful among logicians first (including Kurt Gödel), and computer scientists later; some authors even extended it to include all functions that can be computed by any effectively realizable physical system.

Nonetheless, the Church-Turing thesis is, at least in principle, falsifiable: it is enough to describe a non Turing-computable function admitting another kind of computation procedure, executable by the above-mentioned human computer. Of course, no such function is known to exist; however, consider the following “weaker computability thesis” for the sake of argument:

Every intuitively computable arithmetical function is primitive recursive.

This is falsified by Ackermann's function, which is clearly computable (both intuitively and by a Turing machine) although not primitive recursive.

Question. Has a similar, provably weaker “computability thesis” ever been proposed before Church’s and Turing’s? As an alternative, can we reasonably argue that no such statement was ever made?

Arithmetic of ordered sets more general than ordinals

2010-09-12T10:04:32Z

Motivation. Having read about infinite time Turing machines and ω-languages, I was thinking about more general notions of languages and “computation time”. Languages over strings of length greater than ω seem reasonably easy to define, and using larger ordinals to measure time is quite standard.

However, I’m interested in more general, non necessarily well-founded ordered sets. Using ordered sets to keep track of time seems to require suitable notions of arithmetic operations. For example, it’s easy to generalise sum and multiplication of ordinals to arbitrary totally ordered sets (though, of course, these operations are not defined by transfinite recursion); I’m not sure about exponentiation and other operations.

Question. Is there any good literature about arithmetic of (some classes of) non well-founded ordered sets?

Answer by Antonio E. Porreca for Interesting complexity classes $PR \subsetneq c \subsetneq R$

2010-08-13T14:01:02Z

First of all, it’s certainly possible to obtain some intermediate class by taking a language that only computes PR functions (say, an imperative programming language using only for loops) and adding any total computable but non PR function (e.g., Ackermann’s function). The resulting language L is non-universal, because it only computes total functions: you can still construct a computable but non-L-computable function by diagonalisation. However, L is clearly more powerful than the original language.

As for “interesting”, I guess it really depends on what you mean by that.

If “interesting” means “of practical use”, then one could answer that all computable functions of practical use are PR, since a non-PR function requires an amount of time to compute that is not, in turn, PR. Considering that time bounds such as 2ⁿ, 2^2ⁿ, 2^{2^2ⁿ}, …, are all PR, you see that there isn’t much hope to compute non-PR functions for large values of n.

If “interesting” means “logically interesting”, then I think the answer is “yes”. I’m somewhat familiar with Girard’s System F (also called “second order λ-calculus” or “polymorphic λ-calculus”), described for instance in Girard’s Proofs and Types (freely available here). The functions that can be computed in F are “exactly those which are provably total in [second order Peano arithmetic]” (page 123), and among these we have Ackermann’s function. There is an explicit λ-term for it on these slides (page 20).

If I recall correctly, the standard calculus of constructions includes System F and only computes total functions, so it also provides an example.

Answer by Antonio E. Porreca for post correspondence problem

2010-08-12T23:03:56Z

As Tsuyoshi said, it doesn’t make sense to search for an undecidable instance of a problem. It’s only the problem itself that can be undecidable.

In particular, for every instance of PCP (or any other problem for that matter) there trivially exists an algorithm that gives the correct answer for that particular instance. If we’re dealing with the decision version of the problem, it’s either the algorithm that always answers “yes”, or the algorithm that always answers “no” (granted, this is not a constructive proof).

On the other hand, you might find specific instances of PCP without a known answer, for example by exploiting any open problem of mathematics and the fact that the halting problem reduces to PCP, say via a many-one reduction R.

Consider the Turing machine M that searches for a proof of the Riemann hypothesis by enumerating all proofs, and halts when it finds it. If RH is provable, this machine will halt in a finite amount of time, otherwise it will run forever. You can use the reduction from the halting problem to construct a PCP instance R(M) = x. Now, by deciding whether x is a positive or negative instance of PCP, you also decide RH. But that’s an open problem, and so the status of x also is.

Answer by Antonio E. Porreca for The best text to study both incompleteness theorems

2010-08-01T11:29:47Z

Speaking as a beginner myself:

I haven’t read it all yet, but An Introduction to Gödel’s Theorems by Peter Smith seems like a good candidate, and it doesn’t have many prerequisites. Smith also wrote a series of shorter handouts on the topic, Gödel Without (Too Many) Tears.

There’s also Godel’s Theorem: An Incomplete Guide to Its Use and Abuse by Torkel Franzén, which is much less technical and primarily concerns false myths about the incompleteness theorems; in my opinion, it is a good companion (not a substitute) for Smith’s book.

Answer by Antonio E. Porreca for What is the history of the Y-combinator?

2010-07-14T19:54:24Z

The paper History of Lambda-calculus and combinatory logic by F. Cardone and J.R. Hindley is a good starting point for answering such a question, and many others (it has 38 pages of bibliography). There’s a brief account on fixed-point combinators on page 8, although it doesn’t seem to settle the question completely.

Answer by Antonio E. Porreca for Can I have an LL grammar for every deterministic context free language?

2010-07-13T18:47:38Z

I’m not an expert on this topic, but I found these course notes (including some bibliographical references) which state that the language L = {xⁿ : n ∈ ℕ} ∪ {xⁿyⁿ : n ∈ ℕ} has no LL(k) parser, while being deterministic context-free (see pp. 24 and 27).

Edit: I found a better reference. The paper Two iteration theorems for the LL(k) languages by J.C. Beatty contains a proof that the LR language L = {aⁿbⁿ, aⁿcⁿ : n ≥ 1} is not LL (see Theorem 5.2).

Answer by Antonio E. Porreca for Lower Bounds in Theoretical Computer Science

2010-07-11T21:08:17Z

No EXPTIME-complete problem can be solved in polynomial time as a consequence of the time hierarchy theorem. Of course, the same holds for harder problems, such as problems complete for exponential space, doubly exponential time, etc. These results are unconditional (i.e., they do not depend on P ≠ NP or other conjectures).

There are some interesting problems which provably lie outside P; one of them concerns the equivalence of regular expressions (see these slides for an introduction), and some kinds of game are also very hard to solve.

Answer by Antonio E. Porreca for Are there complexity classes with provably no complete problems?

2010-06-09T19:39:12Z

Another class without complete problems w.r.t. logspace or polytime reductions (not an union of classes TIME(f) for some family of polynomially related functions f, but still relatively natural in my opinion) is

ELEMENTARY = TIME(2ⁿ) ∪ TIME(2^2ⁿ) ∪ TIME(2^{2^2ⁿ}) ∪ TIME(2^{2^{2^2ⁿ}}) ∪ ⋯

If L were ELEMENTARY-complete, then it would belong to some level of this hierarchy, and all problems above could be reduced to it. But this hierarchy is known to be proper (time hierarchy theorem), contradiction.

Answer by Antonio E. Porreca for Which math paper maximizes the ratio (importance)/(length)?

2010-05-21T21:21:35Z

Two fundamental papers in computational complexity theory and the theory of formal languages are very short:

Neil Immerman, Nondeterministic space is closed under complementation, SIAM Journal on Computing 17(5), 935–938, 1988 (four pages);
Róbert Szelepcsényi, The method of forcing for nondeterministic automata, Bulletin of the EATCS 33, 96–100, 1987 (five pages).

Both papers independently prove what is now called the Immerman-Szelepcsényi theorem, i.e., that nondeterministic space complexity classes are closed under complement, and in particular that context-sensitive languages are closed under complement. The authors shared the Gödel Prize in 1995 for their result.

I’ve never read Szelepcsényi’s version, but Immerman’s is so short and sweet that I found it hard to believe at first that it actually works as a proof of such an important theorem.

Answer by Antonio E. Porreca for Resources for learning domain theory?

2010-05-15T08:57:57Z

I used the book The Formal Semantics of Programming Languages by G. Winskel for an undergraduate course, and I found it a reasonably good introduction to the topic; it also covers operational semantics and its relationship with denotational semantics, which I found quite enlightening since the former one is probably easier to grasp initially.

Answer by Antonio E. Porreca for reversible Turing machines

2010-05-10T12:04:22Z

I think your map K_S also needs to take the position of the tape head as input, or am I missing something?

The classic paper Logical reversibility of computation by C.H. Bennett defines reversible Turing machines as

a finite set of n-tape quadruples, no two of which overlap either in domain or range

which should imply your notion of reversibility, assuming you allow an arbitrary alphabet instead of just Σ = {0, 1}.

Answer by Antonio E. Porreca for What is the intuitive meaning of star and box in a pure type system?

2010-04-29T21:49:48Z

I seem to recall there’s a really good explanation of kinds and sorts in Sørensen and Urzyczyn’s Lectures on the Curry-Howard Isomorphism (a previous version is available online).

Answer by Antonio E. Porreca for Proofs of if and only if statements

2010-04-17T22:01:24Z

I think that, in most proofs of equivalence between models of computation (“a function can be computed by an automaton of type A iff it can be computed by an automaton of type B”), both directions usually offer some insight.

This is a simple but fundamental example from complexity theory. Define NP to be the class of languages (equivalently, decision problems) recognised by nondeterministic Turing machines operating in polynomial time. Then:

Theorem. A language L is in NP iff there exist a deterministic Turing machine M operating in polynomial time and a polynomial p such that, for each string x,

if x ∈ L then there exists a string y with |y| ≤ p(|x|) such that M accepts (x, y);
if x ∉ L then M rejects (x, y) for all strings y with |y| ≤ p(|x|).

The deterministic Turing machine M can be called a verifier, and the strings y accompanying each string x ∈ L that make M accept are called short certificates: they constitute an easily verifiable proof of membership of x in the language; no string outside L possesses such a membership proof.

For a proof of this theorem see, for instance, this page on Wikipedia; notice that both implications have an easy but not completely trivial proof.

The proof of “L has short certificates ⇒ L ∈ NP” shows how the “magic” of nondeterminism can be used to guess a certificate (if it exists for a particular input string).

The proof of “L ∈ NP ⇒ L has short certificates”, on the other hand, shows that nondeterminism, which might appear an unrealistic notion, implies the very concrete existence of short, easily checkable proofs for some properties of the input that might be too hard to decide efficiently.

Answer by Antonio E. Porreca for What is your favorite "strange" function?

2010-04-22T16:37:49Z

The Busy Beaver function

Let Σ be a finite alphabet, for instance {0, 1}; let M be the set of Turing machines with alphabet Σ, and let H ⊆ M be the set of Turing machines that halt when given the empty string ε as input.

For each M ∈ H, Let s(M) be the number of steps performed by M before halting (when given ε as input).

Finally, let S : ℕ → ℕ be the function defined by

S(n) = max {s(M) : M ∈ H and M has n states}

Notice that S is well-defined, since only finitely many Turing machines with n states exist.

In other words, S(n) is the maximum number of steps performed on ε among all halting Turing machines with n states. S is called the Busy Beaver function.

It turns out that S is uncomputable because it grows faster than any computable function, that is, for all recursive functions f : ℕ → ℕ we have S(n) > f(n) for large enough n, and in particular f is o(S).

Answer by Antonio E. Porreca for Provability of termination. Whats wrong with my reasoning?

2010-04-16T22:34:58Z

It is true that $H(A)$ implies that we have a proof of $H(A)$, and we can find it by enumeration: as you noted, a proof of $H(A)$ is just a finite sequence of configurations or states of program $i$ on input $x$, each one of them reachable from the previous one according to the rules described by program $i$ itself (hence, such a proof is algorithmically verifiable).

The problem with your argument is that $\neg H(A)$ does not necessarily imply that we have a proof of it, as you assume when saying “But now we have a proof of $\neg H(A)$”. Some programs can indeed have a non-termination proof; for instance, a finite sequence of configurations of the program that repeat cyclically. But other programs can go through an infinite number of non-recurring configurations: thus, the notion of non-termination proof as a finite sequence of configurations is flawed.

Even by giving a lot of thought to the question, you won’t probably find any satisfying notion of “non-termination proof” applicable to all programs. The reason is that such a notion is provably nonexistent (formally, the set of non-halting programs is not recursively enumerable).

Answer by Antonio E. Porreca for Typesetting mathematics: how do {\em you} convert text into pdf?

2010-04-15T15:12:27Z

You can do margin kerning (aka “protrusion”) and font expansion in pdfLaTeX simply by loading the package microtype (i.e., by adding

\usepackage{microtype}

to the preamble). I also suggest using the tracking option for small-caps, which increases the space between letters (which is typographically correct, but only for small-caps and all-caps text):

\usepackage[tracking=smallcaps]{microtype}

For further information (and for several fine-tuning options) you can consult the microtype manual.

Edit: Yes, in my opinion and (I think) in a typographer’s opinion, these features do make a lot of difference. Margin kerning and font expansion help pdfLaTeX typeset the text, producing a lot less over/underfull hboxes. Letterspaced small-caps are also more legible and much more aesthetically pleasing.

Answer by Antonio E. Porreca for Is there a "primitive-recursively enumerable" set whose complement is not such?

2010-04-12T12:26:07Z

This is an interesting question. From B. Rosser, Extensions of some theorems of Gödel and Church:

Corollary I. If a class can be enumerated (allowing repetitions) by a general recursive function, it can be enumerated (allowing repetitions) by a primitive recursive function.

Hence any complete recursively enumerable set (such as K) should work.

Comment by Antonio E. Porreca

2010-09-14T10:37:43Z

Does non-well-founded set theory provide a more appropriate setting for non-well-founded orders, e.g., for finding canonical representatives of each order type? I’m not familiar with the subject.

Comment by Antonio E. Porreca

2010-09-14T10:18:44Z

Thanks, I’ll take a look at it.

Comment by Antonio E. Porreca

2010-09-14T10:18:10Z

Joel, me and one of my colleagues were just toying with that idea; we’re not sure about the interpretation either (except maybe for a “universe without a beginning” where time has the same order type as ℤ).

Comment by Antonio E. Porreca

2010-08-13T14:08:40Z

Sorry, I answered before your edit to the original question; now I see you already excluded the “PR + Ackermann” case. :-)

Comment by Antonio E. Porreca

2010-08-13T13:35:56Z

Could you please edit the original question according to your last comment?

Comment by Antonio E. Porreca

2010-08-13T10:59:18Z

Maybe I misunderstood something, but you seem to claim that membership in PR is decidable. It is not (see Rice’s theorem). I’m not sure, but it might be possible if your programs are written in some non-Turing-equivalent programming language. Could you clarify?

Comment by Antonio E. Porreca

2010-08-13T00:48:18Z

I guess the point of confusion here is that, even when you’ve fixed a group G, you still have another input to give to the hypothetical algorithm (the “word” to check), and the same reasoning applies: you cannot find a specific “undecidable word”. A specific group having undecidable word problem and a specific “undecidable PCP instance” are two very different objects.

Comment by Antonio E. Porreca

2010-08-13T00:42:32Z

I’m not sure I’ve ever met this argument before, thanks!

Comment by Antonio E. Porreca

2010-08-12T23:14:58Z

By the way, it seems to me that the “computability-theory” tag is more appropriate than “cs.cc.complexity-theory”, as we aren’t dealing with complexity matters here.

Comment by Antonio E. Porreca

2010-08-01T12:11:17Z

No, Franzén doesn’t give full proofs; it might be interesting, however, for some philosophical discussion (which, I think, is missing in Smith’s handouts).

Comment by Antonio E. Porreca

2010-07-20T20:08:51Z

I like your last sentence very much.

Comment by Antonio E. Porreca

2010-07-19T16:06:04Z

Probably the question becomes less interesting this way, but I’d go as far as to say that the encoding is itself part of the statement of the problem (particularly when we describe decision problems as languages).

Comment by Antonio E. Porreca

2010-07-14T19:56:53Z

Dan, according to the paper by Cardone and Hindley I posted in my answer, that doesn’t seem to be the case.

Comment by Antonio E. Porreca

2010-07-12T19:09:36Z

Emil, can NC be determined in nondeterministic polytime? If so (as in the NC = 3-colourability example) then it seems to me that Problem 2 does belongs to NP: just ignore the “promise” or any NC certificate given as input, and recheck the property before testing 3-colourability. On the other hand, if NC is too hard (e.g., NEXPTIME-complete) you have to “trust” the promise, because you don’t have the time to verify it (and the problem is not in NP).

Comment by Antonio E. Porreca

2010-07-11T21:27:49Z

I’ve always found this result fascinating: less than log log n tape is no better than no tape at all.