1
$\begingroup$

We know that any "effectively computable" process is computable by a Turing machine (Turing-Church thesis).

Although it seems that "effectively computable" is still open to discussion, the intuitive interpretation is that any process that is "mechanical enough" can be computed by a Turing machine.

Turing's initial objective was to axiomatise how humans do reasoning. Now what do you need to reason? Non-ambiguous definitions (axioms) and non-ambiguous rules. Then you are good to go. So in effect if TM successfully modelise how humans think, that's all they should need and hence natural languages should be quite a close candidate to become regular languages as long as we impose that words have just one meaning.

My question is then, intuitively, is it enough for a language to be "non-ambiguous" to be computed by a Turing machine? Or is there more intuitive properties that the language need to respect?

(I am currently trying to figure out if the laws voted in a parliament, although written in mundane English, have enough of these characteristics to be computed by an automaton).

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ What do you mean by "non-ambiguous" and "computed by an automaton" $\endgroup$
    – adrianN
    Commented Aug 15, 2016 at 11:11
  • $\begingroup$ A formal language is regular if it can be computed by an automaton. That's what I mean here. Non-ambiguous means that (I guess) it's a regular language understood in the way that the transition function is defined. In real life for example, you cannot write "she buy". The way you conjugate "to buy" after "she" is non-ambiguous: there is a function which defines the next word in a unique way. So my question is: is that the spirit of how Turing machines works? $\endgroup$
    – Jerome
    Commented Aug 15, 2016 at 11:25
  • 2
    $\begingroup$ So you want to talk natural languages. I second the query: what does it mean for a natural language to be computed by a TM? What does ambiguity mean in natural languages? (There is a formal meaning in formal languages; I guess you don't mean that.) $\endgroup$
    – Raphael
    Commented Aug 15, 2016 at 11:30
  • $\begingroup$ @Raphael. Agreed. I was only reducing the question to non-ambiguity as it seems to be the biggest hurdle a TM has to overcome when trying to compute a language. Also I think ambiguity in natural languages can be mapped to the existence of a transition function of a TM. Would that non-ambiguity be enough for a natural language to be computable? Or as you say, what characteristics does a natural language need to be computable by a TM? $\endgroup$
    – Jerome
    Commented Aug 15, 2016 at 11:35
  • 1
    $\begingroup$ Please clarify if you want to talk about syntax only or if the TM has to decide semantics as well. $\endgroup$
    – Raphael
    Commented Aug 16, 2016 at 15:47

2 Answers 2

Reset to default
1
$\begingroup$

Under reasonable assumptions, there is a TM which can decide whether something is a valid piece of English legalese. We can safely assume that the length of a law is bounded by some finite number $k$, say the number of characters the fastest human reader can read in less than two hundred years. There is then only a finite number of possible strings that might or might not be valid laws. Hence there is a lookup table of finite size that contains for every string of length at most $k$ the correct answer.

It is not settled whether humans can in fact recognize languages that TM can't recognize, so it's unclear whether the length restriction is truly necessary. See for example this question, or this question.

This is of course a boring answer, because this TM is completely impractical to construct. In actual practice you probably want to restrict yourself to a subset of English that can be parsed by an LL(k) parser (real English is not context-free), or go for a language specifically designed to be easy to understand to both humans and computers. @LukasBarth mentioned Lojban in the comments, but there are a number of such languages (programming languages are another example).

Improve this answer
$\endgroup$
6
  • $\begingroup$ @ adrianN thanks. I would have thought that could be much closer to the natural language. Of course I guess we would have to get rid of a lot of words (notably the subjective words i.e. with ambiguous meanings). But once you have done that, I am not sure what else you need to do. By the way I read about Lojban and they still use words like "Blue" which is subjective. And therefore non-suitable for a TM. $\endgroup$
    – Jerome
    Commented Aug 15, 2016 at 14:35
  • $\begingroup$ Deciding whether a word is in a language or not is a syntactic question. Semantics don't matter, so blue is fine. $\endgroup$
    – adrianN
    Commented Aug 15, 2016 at 14:37
  • $\begingroup$ Ah ok. But all English words HAVE a meaning. Of course if we ignore that meaning I imagine that we can code all words with 0s and 1s and as this is a finite language, it would instantly become TM-computable. But it would also lose all purpose as a TM presented with the word blue would just see 0s and 1s and not what it represents in the real world - which is the whole point of a natural language. $\endgroup$
    – Jerome
    Commented Aug 15, 2016 at 14:57
  • 1
    $\begingroup$ Then I guess I completely misunderstood your question. You want to know what it would take for a Turing Machine to understand English. That is totally different from deciding whether something is English. $\endgroup$
    – adrianN
    Commented Aug 15, 2016 at 15:02
  • 1
    $\begingroup$ @Jerome There, it's very different. Every reasonable English parser will say that "Yea, right." is a valid English expression. The meaning is not clear to humans, let alone the machine. $\endgroup$
    – Raphael
    Commented Aug 16, 2016 at 15:50
1
$\begingroup$

Since there is no reason to believe there is a mysterious, non-computable process which magically allows humans to recognize English, the CT thesis can actually be appealed to say that it is theoretically possible to build a machine that recognizes English at least as accurately as a chosen human.

In the most boring case, you can simply simulate the human brain to decide whether a particular string is valid English or not.

However, take into account that valid English is a much more fluent notion than that of a formal language (English can change through time, etc). Thus it does not have a nice mathematical characterization. The cleanest I can think of is defining English as whatever this particular brain in this particular state accepts as English, which is circular. However, it is a formal characterization anyway.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "you can simply simulate the human brain" -- we don't know how to do that yet, and we don't know if we ever will. $\endgroup$
    – Raphael
    Commented Aug 16, 2016 at 15:47
  • $\begingroup$ @Raphael My argument is that in principle it is possible. To argue otherwise one should provide evidence that there is an uncomputable process happening in the brain. $\endgroup$
    – Jsevillamol
    Commented Aug 16, 2016 at 17:34
  • $\begingroup$ There is no point in simulating whole brain to do that, hopefully this part is far easier because we need two small parts and fancy having three more. Back to argument - you have conjecture, which cannot currently be checked so you cannot require to give you contrarguments. We cannot simulate brain because we lack of blueprints and have small computational power. Also full eavesdropping is not possible - we cannot create powerful enough magnet, but if we could well, subject wouldn't survive like the city around... Other technologies are not any closer. $\endgroup$
    – Evil
    Commented Aug 16, 2016 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.