0
$\begingroup$

Some people believe the human mind is a finite state machine, making references to the Bekenstein bound. I've read that Turing himself imagined the human as FSM with unbounded paper to construct the turing machine.

However, FSMs cannot recognize this simple language: {0^n 1^n| n ≥ 0}. It's obvious that a human could easily recognize this language, so isn't it the case that humans are not FSMs?

-Edit-

It's true that I cannot simply count the number of 0's or 1's because that requires unbounded memory. However, if somebody presents to me this input, I can easily skip to the middle and begin counting pairs of 0/1s.

$\endgroup$
1
  • $\begingroup$ You may be conflating the formal notion of 'finite state machine' with the informal notion. For instance, it's not hard (*) to recognize that language with a computer, either, but I think you would agree that computers are finite entities. $\endgroup$ Commented May 15 at 23:18

4 Answers 4

2
$\begingroup$

Recognizing a language means recognizing all cases correctly, not just the few specific cases you have in mind when you say it's obvious that a human can recognize the language.

The reason a finite state machine can't recognize that language is that it has to remember how many 0s it saw so that it can compare that to the number of 1s. With only finitely many states it can only remember finitely many different counts. That doesn't mean it can't remember a very large number of different counts—more than the largest number you've ever counted to.

The measured value of the cosmological constant plus the Bekenstein bound together suggest that the universe can be in very roughly $2^{10^{120}}$ different states. To show that your mind isn't subject to that bound, you'd have to count past $2^{10^{120}}$ without losing count. No one has lived long enough to attempt that, so there's no evidence that it's possible to succeed.

$\endgroup$
4
  • $\begingroup$ Am I not allowed to read the input out of order, so that I get pairs of 0 and 1 as input? $\endgroup$ Commented May 16 at 0:53
  • $\begingroup$ @JobHunter69 The proof that no FSM can recognize the language applies only to left-to-right scanning order. If you supply the input in first, last, second, next-to-last, ... order then a FSM can recognize it. (Also, the more flexible you make the reading order, the more it resembles cheating, since you're effectively using the position(s) within the string as extra memory.) $\endgroup$
    – benrg
    Commented May 16 at 4:27
  • $\begingroup$ Sure, but in reality I can have an FSM read in arbitrary order. (The state that the written input takes up does not count towards the state of the FSM). So why are we falsely declaring a limit to their computational power? $\endgroup$ Commented May 16 at 5:32
  • $\begingroup$ @JobHunter69 That might be a good question for this stack exchange, in a form like "how much more powerful are FSMs if you relax the input-reading requirements?". Some versions have been asked already, e.g. Single-tape Turing Machines with write-protected input recognize only Regular Languages. $\endgroup$
    – benrg
    Commented May 17 at 1:57
1
$\begingroup$

I think whether you believe that a human can recognise a non-regular language like $L = \{0^n1^n : n \geq 0\}$ depends somewhat on your philosophical convictions.

Indeed, it is easy to design a general algorithm to recognise $L$. But if you implement this algorithm on a real machine, you will find that you can only recognise a finite subset of $L$, at some point the memory to count $0$s and $1$s will run out. This process might not feel to you like designing a FSM, but if you list all states of your computer (i.e. all configurations of your RAM) and how these configurations change depending on input from your mouse, a hard drive etc., you will find that you have drawn a FSM.

The Bekenstein bound, as I understand it, seems to imply that the memory of all real machines must be finite. So all real machines can be viewed as a FSM in the sense above.

Now, if you believe that the human mind isn't a part of physical reality, like a some religious communities do, you might not think that these bounds also apply to the human mind. If you believe that the human mind is just a function of the brain, then the brain probably only has access to a finite memory and so could be described as a FSM.

$\endgroup$
10
  • $\begingroup$ I updated my question. I don't understand why the method I mentioned doesn't work $\endgroup$ Commented May 16 at 2:07
  • $\begingroup$ The problem about skipping to a point in a string is that you already need to have memorized the string. If you want to find the point where the string switches from $0$ to $1$ you either need to have the string written down or remembered up to that point. So you're limited either by the amount of paper in the universe or your (possibly finite?) memory. $\endgroup$
    – Knogger
    Commented May 16 at 2:18
  • $\begingroup$ But isn't it the case that the large piece of paper in which the string is written down on is not part of the finite state machine's memory? The input/paper is not part of the FSM itself. $\endgroup$ Commented May 16 at 2:29
  • $\begingroup$ The tape wasn't what was meant there. You, or the machine, get drip fed 0s and 1s one at a time from the tape. You only ever have access to one symbol. So to find the middle of your string, you need to memorize the 0s and 1s, and only once you've read the whole string you can know where the middle is. $\endgroup$
    – Knogger
    Commented May 16 at 2:44
  • 1
    $\begingroup$ There's no difference in reading the whole string one symbol at a time and writing it down, and already having it written down. Either way, you are limited by the finite amount of paper, you can't write down all words in $L$ with finite memory (paper) 😅. $\endgroup$
    – Knogger
    Commented May 16 at 2:55
0
$\begingroup$

Here, $L=\{0^n1^n\mid n\ge 0\}$ is not a regular language (it is a context-free one). Thus, $L$ cannot be recognized by a DFA (or NFA). But a Turing machine (TM), which is a more powerful FSM than DFAs or NFAs, can easily recognize this. Even a deterministic pushdown automaton (DPDA) can recognize $L$. DPDAs are less powerful than TMs, but of course they are more powerful than DFAs (or NFAs).

$\endgroup$
0
$\begingroup$

You say you jump to the middle of the input. How exactly do you propose to do that with finite memory? You’ll have to remember the first n 0s, not just the number n.

$\endgroup$
2
  • $\begingroup$ You can jump to the middle of the input by simply reading 0s until you encounter a 1 $\endgroup$ Commented May 17 at 2:04
  • $\begingroup$ And then you don’t know how many 0s you had and you are stuck. It works for 0^n 1^m where the number of 0s doesn’t matter but not for 0^n 1^n. $\endgroup$
    – gnasher729
    Commented May 17 at 7:51

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.