Databases
StackOverflow2013
Postsdbo
POPractical non-Turing-complete languages?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POPractical non-Turing-complete languages?
    text
    copied!<p>Nearly all programming languages used are <a href="http://en.wikipedia.org/wiki/Turing_Complete" rel="noreferrer">Turing Complete</a>, and while this affords the language to represent any <a href="http://en.wikipedia.org/wiki/Computability_theory_(computer_science)" rel="noreferrer">computable</a> algorithm, it also comes with its own set of <a href="http://en.wikipedia.org/wiki/Halting_problem" rel="noreferrer">problems</a>. Seeing as all the algorithms I write are intended to halt, I would like to be able to represent them in a language that guarantees they will halt.</p> <p><a href="http://en.wikipedia.org/wiki/Regular_Expression" rel="noreferrer">Regular expressions</a> used for matching strings and <a href="http://en.wikipedia.org/wiki/Finite_state_machine" rel="noreferrer">finite state machines</a> are used when <a href="http://en.wikipedia.org/wiki/Lexing" rel="noreferrer">lexing</a>, but I'm wondering if there's a more general, broadly language that's not Turing complete?</p> <p><strong>edit:</strong> I should clarify, by 'general purpose' I don't necessarily want to be able to write all halting algorithms in the language (I don't think that such a language would exist) but I suspect that there are common threads in halting proofs that can be generalized to produce a language in which all algorithms are guaranteed to halt.</p> <p>There's also another way to tackle this problem - eliminate the need for theoretically infinite memory. Once you limit the amount of memory the machine is allowed, the number of states the machine is in is finite and countable, and therefore you can determine if the algorithm will halt (by not allowing the machine to move into a state it's been in before).</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload