20

Your intuition sounds wrong to me. It's not surprising you couldn't prove it, because it isn't true. Roughly speaking, it is possible to find a computer that can simulate all other computers. A universal Turing machine can simulate any other Turing machine, and can be used to simulate any other program in any Turing-complete language. Thus, there is a ...


20

Languages that are guaranteed to halt have seen wide spread use. Languages like Coq/Agda/Idris are all in this category. Many many type systems are in fact ensured to halt such as System F or any of its variants for instance. It's common for the soundness of a type system to boil down to proving that all programs normalize in it. Strong normalization is a ...


11

No. Take any language $L$ over $\Sigma = \{0, 1\}$ that contains 0 and 1. Then $L^* = \Sigma^*$ (this is recursive, even regular), regardless of what $L$ might be. It could be a not even recursively enumerable language.


8

Different people have different views on what the definition of continuity should be, but the way I see it, we should define continuity to be computability relative to some oracle. For example: Definition: A function $f : \mathbf{X} \to \mathbf{Y}$ is continuous, if there is a computable partial function $F :\subseteq \mathbf{X} \times \mathbb{N}^\mathbb{N} \...


8

Arno's answer provides some very useful background reading material, I would just like to address your specific question about $\mathbb{R}$. Let us first recall a result by Peter Hertling, see Theorem 4.1 in A Real Number Structure that is Effectively Categorical (PDF here), about computable structure of the real numbers. Suppose we have a representation of $...


7

Here is one possible approach. Since $L$ is c.e., there is some enumerator that outputs a list of the word in $L$: $w_1,w_2,\ldots$. Let $D$ consist of all words $w_i$ which are longer than all words appearing before them. I claim that $D$ is infinite. If not, let $w_m$ be the last word in $D$. Then all other words have length at most $|w_m|$. However, this ...


7

We can have sets $A, B, C$ with linear-time computable maps $f : A \to C$ and $g : B \to C$ such that there exists a map $h : A \to B$ with $f = g \circ h$, but the needed time complexity/Turing degree for $h$ is as high as you want. Proof: Pick a map $H : \Sigma^* \to \Sigma^*$ which is hard in whatever sense you have chosen. Now let $A = C = \Sigma^*$, ...


5

Nice question! I think that your notion of an "effectively computable reduction" is interesting and worth studying, but not as fundamental as standard reductions. Let me provide some observations about this notion that may be illuminating: Observation 1: it does not make sense to talk about effectively computable reductions from one language to another; ...


5

Your argument "goes backwards." Note that your definition of $R$ depends on $D$ (step $2$). This means you can't conclude that no machine decides $A_R$, merely that $D$ specifically doesn't. Basically, what you've written looks like this: CLAIM: there is some $x$ such that no $y$ does [task involving $x$]. PROOF: picking some $y$, we build an $x$ such ...


5

The Wikipedia statement is informal and quite ambiguous. For example, let $A(n,n)$ be the Ackermann function, and consider the following program, where $n$ is the input: x ← 0 for i from 1 to A(n,n): x ← x + 1 return x This function is not primitive recursive, although there is a bound on the number of iterations which is known ahead of time. A better ...


5

There are no catches. Diagonalization is a very general proof technique that works in classical, constructive and computable setting. It is used to prove: that there is no surjection from a set to its powerset that the real numbers cannot be enumerated that the computable real numbers cannot be computably enumerated that the Halting oracle does not exist ...


4

I see two ways of interpreting this question, but the answer is essentially trivial either way. Interpretation 1: Can every hypercomputation model decide some language that cannot be decided by a Turing machine? Yes, because that is the definition of a hypercomputation model. A caveat: Technically, you could have a hypercomputation model that (as ...


4

Once you have proved that $|x-2^y|=0$ is a decidable predicate, the function $$\log_2(x) \equiv \mu y(|x-2^y| = 0)$$ should match the description of the function given and proves that it is recursive. Edit: To show that $|x-2^y|=0$ is decidable, show that $\overline{\text{sg}}(|x-2^y|)$ is recursive, which requires you to show that $|x-z|$, $2^y$, and $1 - \...


4

It's your second bullet point - something odd in the recursive relationship. The argument is trying to show a contradiction by exhibiting a finite language that is undecidable. In other words, the argument needs to show that there exists a finite language $L$ such that for every decider $D$, there is some input $w$ such that $D$ incorrectly decides whether ...


4

It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$. You have to be more careful about this statement. It's not true for any fixed Turing machine $M$ that the halting problem $\text{HALT}_M$ (deciding on input $w$ if $M$ halts on $w$) is undecidable. For example, if $M$ is a machine that always ...


4

First of all, if you can determine whether a graph $G$ contains an independent set of size $k$, then you can also find such a set efficiently. This is known as "search-to-decision reduction". Here is the basic idea. Choose an arbitrary vertex $v$, and remove it. If the graph still has an independent set of size $k$, then keep going. Otherwise, all ...


4

If we were to use the decimal expansion to represent real numbers, your reasoning would work. But that gives us a very badly behaved notion of computability: Proposition: Multiplication by 3 is not computable relative to the decimal representation. Proof: Assume the input starts 0.3333333... At some point, our computation needs to start outputting something. ...


4

Even though absolute comparisons may not converge, you should be able to narrow the argument into at least one of several partially overlapping ranges, such that you have a technique that works in that range. For example, you should be able to tell that $x$ definitely falls into at least one of the ranges $A = \left(0,\frac{3}{4}\right]$, $B = \left[\frac{1}{...


4

The point of the halting program IMO is not to show that you can't check whether an arbitrary program can halt--that's not a very interesting fact on its own. The point of the halting program, is to use "reduction", to go on and prove that a (very large number of) procedures you might like to have a tool do are also impossible in general: Deciding ...


4

Unfortunately, I don't possess a copy of Sipser, so I will just define all my notation. Let $T_0,T_1,\ldots$ an enumeration of all oracle Turing machines whose input is a word over some alphabet $\Sigma$. I will denote by $T_i^O(x)$ the output of the execution of $T_i$ on input $x$ with oracle $O$, or $\bot$ if the machine doesn't halt. We say that $T_i$ (...


3

A slightly weaker form of Gödel's first incompleteness theorem can be derived from the undecidability of the Halting problem with a short proof. The full incompleteness theorems also have a short proof which is similar to the one for undecidability of the Halting problem. I highly recommend the whole series (or at least the previous part) for context. The ...


3

Cook up some encoding of Turing machines so that if $n$ codes a machine, $2 n$ codes "the same" (perhaps use binary numbers ending in 1 as starting points, and 0s at the end are disregarded, thus making that odd $n$ and $n \cdot 2^k$ represent the same machine). Then use that e.g. $\operatorname{HALT}(M)$ (does $M$ halt if started on an empty tape?) isn't ...


3

Using the proof of the Cook–Levin theorem, for every input $x$ you can construct in polynomial time a SAT instance $\phi(r,z)$ which encodes "$M$ accepts when run on input $x$ and randomness $r$". Here $r$ is a vector of $m = \mathit{poly}(n)$ bits, representing the random bits of $M$, and $z$ is an auxiliary vector, with the following property: in any ...


3

The answer is yes, but for an unexpected reason. I believe the above comments are correct — given size_t is bounded, you cannot represent a turing machine with unbounded states by using C as intended. However, we can use C in a way which completely circumvents the size_t issue — using only the C preprocessor. I will not go over the whole proof here — ...


3

The Stanford Encyclopaedia of Philosophy has a summary of the history of recursive functions. In particular, in Section 1.8 we can read that Stephen Kleene explicitly defined the partial recursive functions, and showed them to be equivalent to several other notions of computable functions, in a series of papers between 1936 and 1954. For example, already his ...


3

Metric TSP is NP-complete - hence yes, assuming you can solve the metric TSP in $6(n^{12})$, this is good enough to prove $P=NP$. Giving a blackbox that can do that, would be a quite strong evidence (if it actually works). But there are some considerations one should take into account: it actually could be somewhat dangerous, as someone else could figure ...


3

Short answer: if you can solve the decision (yes/no) problem, calling that tells you if it has no solution; if there is a solution, pick a variable and set it to true, see if the result can be satisfied; if not, it has to be false. This way, with one call to the oracle per variable you get a "solution" (set of values of the variables making the expression ...


3

NP-completeness is a category of decision problems, that is, problems in which the answer is Yes or No. When we say that 3SAT is NP-complete, what we mean is that the decision version of 3SAT is NP-complete. There are other types of problems around. The three most common ones are optimization problems, function problems and search problems. Optimization ...


3

No, it is not necessarily recursively enumerable. There are languages that are recursively enumerable but not recursive. Thus, their complement is not recursively enumerable. From that, you should be able to prove that the answer to the question in the final sentence of your post is no (I'll let you fill in the details from there).


3

Philosophical answer The general philosophy in realizability theory (TTE is a special case of it) is that for a program $p$ realizes a map $f : A \to B$ then $p$, it should work correctly on realizers of arguments, i.e., if $r$ realizes $x \in A$ then $p\,r$ realizes $f(x) \in B$. It is quite unnatural to say anything about "non-realizers", for at least two ...


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