Can the halting problem be solved for any non-turing languages?

The halting problem cannot be solved for turing complete languages and it can be solved trivially for some non TC languages like regexes where it always halts.

I was wondering if there are any languages where it has both the ability to halt and not halt and there is also an algorithm that can determine whether it halts.

From stackoverflow

• The halting problem does not act on languages. Rather, it acts on machines (i.e., programs): it asks whether a given program halts on a given input.

  Perhaps you meant to ask whether it can be solved for other models of computation (like regular expressions, which you mention, but also like push-down automata).

  Halting can, in general, be detected in models with finite resources (like regular expressions or, equivalently, finite automata, which have a fixed number of states and no external storage). This is easily accomplished by enumerating all possible configurations and checking whether the machine enters the same configuration twice (indicating an infinite loop); with finite resources, we can put an upper bound on the amount of time before we must see a repeated configuration if the machine does not halt.

  Usually, models with infinite resources (unbounded TMs and PDAs, for instance), cannot be halt-checked, but it would be best to investigate the models and their open problems individually.

  (Sorry for all the Wikipedia links, but it actually is a very good resource for this kind of question.)

  FryGuy : Can't all machines be represented as the set of inputs that they accept, i.e. a language?

  A. Rex : @FryGuy: but you can't give this information to a program, because that representation is infinite.

• The short answer is yes, and such languages can even be extremely useful.

  There was a discussion about it a few months ago on LtU: http://lambda-the-ultimate.org/node/2846

• Yes. One important class of this kind are primitive recursive functions. This class includes all of the basic things you expect to be able to do with numbers (addition, multiplication, etc.), as well as some complex classes like @adrian has mentioned (regular expressions/finite automata, context-free grammars/pushdown automata). There do, however, exist functions that are not primitive recursive, such as the Ackermann function.

  It's actually pretty easy to understand primitive recursive functions. They're the functions that you could get in a programming language that had no true recursion (so a function f cannot call itself, whether directly or by calling another function g that then calls f, etc.) and has no while-loops, instead having bounded for-loops. A bounded for-loop is one like "for i from 1 to r" where r is a variable that has already been computed earlier in the program; also, i cannot be modified within the for-loop. The point of such a programming language is that every program halts.

  Most programs we write are actually primitive recursive (I mean, can be translated into such a language).

  obvio171 : Wait, so are regular expressions of the kind that *always halt* (as the OP says), or of the kind that may not halt, but one can always say if it does or not? Asking because of this question: http://stackoverflow.com/questions/1241215/do-all-regular-expressions-halt

  A. Rex : I don't know if I would say regular expressions actually define a model of computation. In any case, it is always possible to tell in finite time whether a given string matches a given regular expression.