partial recursive functions

Question

Since the partial recursive functions are those that can be computed by a Turing machine, it seems that there ought to be a simple set of restrictions that can be placed on them to get the subset of functions that can be computed by a finite state machine, but I cannot find any such set of restrictions anywhere in the literature. Is there any straightforward way of doing this?

Answer 1

I am admittedly not an expert on this .... but it strikes me that the differences between a Turing-machine and a finite-state machine are such that this is going to be more than a 'straightforward' set of 'restrictions'

First of all, without an ability to write, but just having an ability to 'accept' or 'reject', any function that is computed will have to be a function with a binary range.... functions with a 'yes' or 'no' output, or '0'or '1'.

Now, you could actually see this as a 'straightforward' restriction on the functions it computes, but there is also this: without the ability to write, the finite-state machine effectively has no working memory and, with that, loses any ability to 'recurse'.

In other words, I would argue that we're really not talking about a 'subset of the recursive functions' anymore ... but really about a different class of functions altogether. Yes, technically they would be a subset of the 'recursive functionz', but there is nothing 'recursive' about it anymore ... and given the highly restrictive nature of the output, it's not even 'functional' in a very interesting way; it doesn't do addition, multiplication, division, or anything else we normally envision when talking about 'computing functions'.