in development

SECTIONS

FUNDAMENTAL... OVERSIGHTS IN AUTOMATA THEORY

NON-COMPUTABLE FUNCTIONS

FUNDAMENTAL... OVERSIGHTS
      IN AUTOMATA THEORY

Automata theory is very young, but so far it has developed — let’s not say evolved just yet — along lines suggested by other much older branches of mathematics. But not entirely. There is an interesting discrepancy between a fundamental proof of automata theory and a very similar one in set theory and real number theory, one that Cantor popularized.

The discrepancy leads to a traditional can of worms. The can of worms is difficult to explore, to be sure, but the discrepancy is trivial to detect, and that it would lead to a can of worms should have been noticed since the introduction of this standard proof of a fundamental result in automata theory.

SECTIONS

FUNDAMENTAL... OVERSIGHTS IN AUTOMATA THEORY

NON-COMPUTABLE FUNCTIONS

NON-COMPUTABLE FUNCTIONS

Functions in automata theory are — or seem to be — simple things compared to functions (studied in the branch of mathematics known as analysis) of real or complex variables. (The fact that this is actually a deceptive simplicity will not concern us here.) They are functions with a domain and range (now almost outdated terminology) over the set of all natural numbers, Á 4 {1,2,3...}.

A subclass of these functions are “computable”, which means that they have an associated algorithm and associated machine (at least one of each) which will compute the value according to that algorithm. (Many different approaches were tried, and many of them were later shown to be equivalent. This is why we have so many concepts floating around: machine, algorithm, recursive functions, neural nets, etc.)

The question came up early on: are all functions computable?

There is a standard result in automata theory that says there exist functions that are non-computable, i.e. for which there exists no algorithm (and associated machine-automaton) that will compute it. A standard proof of this (back in the ’60s) used an argument based on Cantor’s famous diagonalization technique.

Step 1: One makes a “list of all computable functions”: cf₁, cf₂, cf₃... (implicitly if not explicitly “assuming” in the standard mathematical sense that there are only countably infinitely many computable functions)

Step 2: Then one uses this “list of all computable functions” to generate a new function that is not in “the list”. Starting with 1, one takes the first function in “the list” and applies it to the number 1, giving us some number cf₁(1). We want a function that is not in “the list”, so we make our new function take a different value at 1, nf(1) = cf₁(1) + 1. (All the values of the functions are usually considered to be finite, thus avoiding any problems of the kind you may have just thought of.)

Step 2 (cont.): Continuing on, we do the same for every function in “the list of all computable functions” and its corresponding natural number. Our new function, nf, differs from each function in “the list” for at least one value in their shared domain ({1,2,3...}), and so is not in “the list”. Since “the list” is (ostensibly) a “list of all computable functions”, our new function cannot be computable because it is not in “the list”, so there exist non-computable functions, QED. Or so the standard proof goes. (We can see that the initial assumption of the countability of computable functions has not yet been questioned.)

There are problems, but how fatal they seem depends on how far one is willing to go into the can of worms mentioned above.

• The first problem: Cantor’s famous diagonalization technique.

Cantor’s diagonalization technique was applied by him to a list of real numbers (between 0 and 1), giving a number which differed from the first one in the first decimal place (or binary place), the second in the second, and so on, for all the infinity of decimal places to the right of the decimal point.

The discrepancy is... that the number Cantor obtained as different from every other real number in the list was considered to be a real number, and the fact that it wasn't in the list (ostensibly) meant that there were uncountably infinitely many real numbers. But in automata theory, this same diagonalization technique proves that the function is NOT computable, corresponding to Cantor actually having proven that there existed numbers that weren't real.

Cantor’s argument makes more sense in that the new number is an infinite decimal expansion just as all the numbers in the countable list are. And it is this infinite decimal expansion that makes a number “real”. (Actually, there exist other definitions of real numbers, all considered to be equivalent. But the very existence of real numbers by any definition can be called into question.) But...

• One must ask: why didn’t the use of the diagonalization technique in the automata theory proof prove that there were uncountably infinitely many computable functions?!

There is the assumption that such a “(countably infinite) list of all computable functions” “exists” or “can exist”. This was never properly addressed. For example:

• Is the “list of all computable functions” itself computable?!

We get into trouble 3 different ways. First, if “the list of all computable functions” is itself computable, then there exist uncountably infinitely many computable functions, and automata theory is in trouble since it says the opposite. (The diagonalization of that list to produce a function not in the list is obviously a computable function. I.e. the function nf(n) = cf_n(n) + 1 is computable if both the function cf_n is computable and the list of such functions is computable.)

Second, if “the list of all computable functions” is itself computable, then we probably have a solution to the halting problem, and automata theory is in trouble.

Third, if it isn’t, then... it gets wormy.

If “the list of all computable functions” exists, and can be used to compute-construct nf in the way it was used in the standard proof mentioned above, then it would seem that nf itself must be a computable function, even if it is not in the (ostensible) “list of all computable functions”; after all, we just “computed” it (given “the list”). It would have a certain similarity to a Universal Turing Machine, except that the encoding of the computable function would not be given with the input for the function on the tape that the UTM starts with, but would rather already be built into “the list”.

It seems:

• We have to somehow say that:
  “the list of all computable functions” can exist without being computable; i.e. it is the value of a function that is non-computable, but we didn’t have to compute it because we... uhh... it was handed to us on 2 stone tablets!

• And, more importantly, that:
  “the list of all computable functions” can be used by us to compute “a function that is not computable” in the way we use it without the list itself becoming computable.

• Noting that automata theory is on the whole very finitistic with regard to space-like and time-like considerations, e.g. a computable function must have a finite state machine (albeit with a potentially infinite tape or stacks, but without an infinite amount of tape being used to hold an infinite program to compute function values on that tape), we can further note that an infinite “list of all computable functions” runs distinctly counter to this finitism. This suggests definite theoretical problems with the theoretical existence of such a list.

• We also have the problem that if “the list of all computable functions” cannot exist theoretically (or if it exists theoretically but cannot be used in the way we used it above in the standard proof of the existence of non-computable functions), then in that same standard proof we were engaging in reasoning from false premises. This is standardly acceptable in a proof by “reductio ad absurdum”, i.e. in a “proof by contradiction”, where one attempts to derive a contradiction that proves the initial (and non-standard) assumption (or set thereof) false (still considered a standard method of proof despite Gödel). But it is not acceptable to make a proposition thus proved a theorem of the theory. This needs to be studied deeply and thoroughly.

• And of course we never questioned the initial assumption that computable functions were countably infinite and therefore could (possibly) be put in a list (which by definition is countable, either countably finite or countably infinite).

This situation is not as bad as the situation that set theory finds itself in, but it should give people food for thought, and produce a raft of articles and even several PhD theses to resolve it.