Articles of computability

Showing that a function is not computable.

the following function was shown not to be computable: $h(x) = \begin{cases} \mu n.\Phi_x(n) \downarrow & \mbox{if } \exists n \Phi_x(n) \downarrow \\ \uparrow & \mbox{otherwise} \end{cases}$ using the following auxiliary function: $f(x,y) = \begin{cases} 0 & \mbox{if } y > 0 \mbox{ or } \Phi_x(x) \downarrow \\ \uparrow & \mbox{otherwise} \end{cases}$ My question is […]

Is every context free language equivalent to one whose grammar has only one non-terminal symbol?

A context free language is generated by a context free grammar, which can be expressed in the Backus-Naur form e.g. I believe that if we only allow one nonterminal symbol in the grammar, the resulting languages must be simpler, possibly even regular. I don’t see how to prove this yet, so can you help me: […]

The word problem for finite groups

The word problem for finite groups is decidable. Is it obvious that this is true? In particular, I’m not entirely sure about what it means for the problem to be decidable (in this case—I think I understand what decidable means in general). I assume it means that we are given a fixed group G (do […]

Are all computable functions continuous or vice-versa?

A famous result in intuitionistic mathematics is that all real-valued total functions are continuous. Since the requirements for a function to be admitted intuitionistically is that it must define a procedure or algorithm, all functions are computable. This seems to suggest that all computable functions are continuous. My questions are: Is this true for all […]

The Entscheidungsproblem and the notion of decidability in first order logic

The Entscheidungsproblem asks if we can find an effective procedure to decide for every formula of first-order logic if its true or false, or what is the same with regard to its completeness, if it is provable or not. This could be read on wikipedia. This problem was answered in the negative by Church and […]

A is recursive iff A is the range of an increasing function which is recursive

Working a problem stated in Enderton, but stated better and apparently stronger in Soare. All citations hereon are for Soare (1987). Would appreciate help on the proof. I know there has to be a more elegant proof than what I have attempted, assuming my proof is correct (it may not be). The problem is stated […]

Why is the following language decidable? $L_{one\ right\ and\ never\ stops}$

I can’t understand how the following language can ever be decidable: $L= \{ \langle M \rangle | M \ is \ a \ TM \ and\ there\ exists\ an\ input\ that\ in\ the\ computation\ $ $of\ M(w)\ the\ head\ only\ moves\ right\ and\ M\ never\ stops \}$, but apparently it is. We need to approve […]

Image of a strictly increasing computable function is computable?

I’m trying to show that if $f:\mathbb{N}\rightarrow\mathbb{N}$ is computable and strictly increasing, then $f(\mathbb{N})$ (the characteristic function of its image) is computable. My problem is that it seems too straightforward: if $f$ is strictly increasing, doesn’t that just immediately provide a bound for existential quantification? So we have $g(y)=1\ iff\ \exists x\leq y: f(x)=y$ be […]

Simplifying Relations in a Group

Let $K$ be the group generated by four elements $x_1,\cdots,x_4$ with relations that any simple commutator with repeated generator is trivial; for example, $[[x_2,[x_1,x_3]],x_3]=1$. As I have asked here, I am trying to use GAP to do some calculation with $K$. Now one problem is that there are too many relations. For example, all following […]

Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this

Suppose we have a computable function $f$, say over the naturals, and a decidable set $S$ of naturals, such that $f(x) \in S$ for all $x$. In this case, for any specific $x$, there is some specific number $y$ such that Peano arithmetic proves $y = f(x)$. (This follows from the fact that $f$ is […]