2
$\begingroup$

Let's say that I want to restrict certain features of a common programming language--for instance, C--such that the result is decidable, and thus no longer Turing-complete. What language features, at minimum, would I need to remove to make a given programming language decidable?

For the purpose of this question, let's assume the following:

  • The original language in question is imperative.
  • We're not restricting memory in any meaningful way.
  • The result isn't hideously crippled (e.g. no subsets of C that only consist of printf calls).
$\endgroup$
  • 2
    $\begingroup$ The question isn't well-defined: the subset of languages features to remove is not unique (there are probably many subsets you could remove to make the resulting language decidable). Also, it's not clear to me what "not restricting memory" means precisely, nor what counts as "hideously crippled". $\endgroup$ – D.W. Jan 11 '16 at 5:01
  • 2
    $\begingroup$ Arguably, taking a Turing-complete language and removing features until termination becomes decidable is hideously crippling it! Actually, I wrote "until termination becomes undecidable" but it's not clear from your question what property you want to be decidable. $\endgroup$ – David Richerby Jan 11 '16 at 6:04
  • $\begingroup$ Partial duplicate: cs.stackexchange.com/questions/19591/…, something else that's worth lookup up is "total functional programming". See en.wikipedia.org/wiki/Total_functional_programming. Epigram, Charity, and Coq are examples of languages where every program either terminates or coterminates. $\endgroup$ – Pseudonym Jan 11 '16 at 6:19
  • $\begingroup$ The way you phrase your question, it's very illposed -- most programming languages are decidable! Note that in formal languages, "decidable" means that you can decide membership; that's a task every compiler performs. Why do you tag halting-problem? $\endgroup$ – Raphael Jan 11 '16 at 7:34
  • $\begingroup$ @Raphael OP is asking about the computations performed by the programs, not about whether well-formedness is decidable. As a language, any programming language itself is assumed to be decidable! $\endgroup$ – BrianO Jan 11 '16 at 22:30