8

If recollection serves the answer is yes, although it is definitely not easy (so far as I know). The question was first posed by Shoenfield in the final paragraph of his paper Degrees of unsolvability associated with classes of formalized theories. I believe it was first answered by Peretyat'kin, who has proved a number of deep results about the model- and ...


7

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 language is inherently ambiguous is a separate one. The undecidability of inherent ambiguity of a CFL was proved by Ginsburg and Ullian (JACM, January 1966). https://dl.acm.org/doi/10.1145/321312.321318


7

It's not uncommon for Wikipedia to say dubious things. Don't trust it as a primary reference. Beware that hypercomputation is potentially a "crank-adjacent" subject, so the Wikipedia article on it might be especially at risk of containing material of uncertain reliability. When you find something in Wikipedia you don't understand, my advice is ...


6

Really nice question(s). I don't fully follow Denis’ answer, so I'm going to try my own. For question 1, I’m going to assume that you are familiar with Kolmogorov complexity (otherwise I could write a proof heavily using Kleene’s fixed point theorem, but such proofs tend to look like black magic, while Kolmogorov complexity is rather natural). Assume for the ...


5

Here is a negative answer to question 1. Let us assume that there is a computable function $f$ such that there is a Turing machine $M$ recognizing $H$ in time $f(n)$ with oracle $\Gamma_{BB}$. Let $g$ be a computable function bounding the maximal integer that $M$ can write on its tape on input of size $n$, for instance with binary encoding $g(n)=2^{f(n)}$. ...


4

Internal parametricity does not entail any version of extended Church's thesis. To see this, consider a presheaf model of internal parametricity, for example this one, and observe that in any presheaf model of type theory the extended Church's thesis fails (both the internal and the external one) because the object $\mathbb{N}^\mathbb{N}$ has uncountably ...


4

The short version of this answer is: Degree theory (e.g. the study of the first-order theory of the partial order of Turing degrees) yields examples of non-relativizing statements, although these statements are of course highly technical. One useful tool for understanding this situation is the cone theorem ... which also limits the extent to which this ...


2

First of all, the place for this question is cs.se, not here. But since I've already written an answer, I'll leave it. There is a formal definition of computability: a function $f$ is computable if there is a Turing machine that, given input $x$, always halts with $f(x)$ written on its tape. You could of course define more general computability, which uses ...


2

This is pretty much an open problem and subject to active research. There are a few proposals available. Here are some of the latest ones: Brain computation by assemblies of neurons Christos H. Papadimitriou, Santosh S. Vempala, Daniel Mitropolsky, Michael Collins, Wolfgang Maass Proceedings of the National Academy of Sciences Jun 2020, 117 (25) 14464-14472;...


1

I am going to answer the question from your title in a slightly facetious way: Computable maps are closed under composition, and the identity map is computable, therefore the collection of all computable maps $\mathbb{N} \to \mathbb{N}$ forms a monoid with respect to composition. Perhaps you meant to aks whether there was a monad involved, in which case: ...


1

The union is not a good idea because you cannot tell, if a number is in the union, whether the number got in because it is an element of $0^{(n)}$ or $0^{(n+1)}$, etc. Instead, if you take the union of the $<n,a>$ where $a$ is an element of $0^{(n)}$ then you can keep them separate.


1

Here is another way to think about the question, that does not mention types or higher-order functions. As Andrej pointed out, translations or encodings do a lot of computation. Of course, this can't be avoided when comparing models but we can ask if a double translation e.g. from lambda-calculus to Turing machines and back again, is definable or computable ...


1

Sure. There are Turing machines that always reject or always accept... So, one of them is surely correct...


1

Such an $H$ would let us solve the halting problem: We begin by running $H(H(P))$ until it halts (which it does by assumption on $H$). If the output of $H(H(P))$ is "doesn't halt," then we know $H(P)$ doesn't halt, and so by assumption on $H$ we know that $P$ doesn't halt. If the output of $H(H(P))$ is "halts," then we subsequently run $H(P)$ until it ...


1

This is course on Arithmetic Circuit Complexity, offered by Prof Nitin Saxena (the S of AKS primality test). The syllabus and pre-requisites can be found here.


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