What is the simplest way to understand Turing machines and the busy beaver problem?
From quora.com:

A Turing machine is a computer (PC, Mac, iPhone or Conway's Game of Life - pick whichever is most familiar) with unlimited storage (memory, hard disk, doesn't matter). Assume you can program the computer in some programming language, and that you're interested in what it can and cannot compute. &quot;Compute&quot; means &quot;read some input, do stuff, write some output&quot;.
This is not the usual description of a Turing machine, of course, but for the study of computability - which is mostly what Turing machines are good for - it's completely equivalent.
The Busy Beaver problem is this: suppose I challenge you to write a computer program (again, pick your favorite programming language) whose sole purpose in life is to print a long string of dots and then stop. If the length of your program is limited to k characters, how long of a string can you make?
It should be clear that this question has an answer, for any choice of programming language and any given limit k. After all, there are only finitely many possible computer programs of length, say, 10,000 characters in, say, C++; some of them print finite strings of dots, and of all the ones that do, we can pick the one (or ones) that print the absolutely longest string.
If you happen to know something about programming, it should also be clear that as soon as k becomes reasonably large to accommodate some non-trivial programs, the answer will be incredibly humungous. It's quite easy, for example, to write a computer program that prints 100^{100} dots and then stops, and in most reasonable programming languages this shouldn't take up more than a few hundred characters to implement. With some cleverness you can get much higher numbers.
The Busy Beaver function is a table that lists, for any given k, the answer to this problem - the length of the longest string of dots you can achieve with a program of length k that prints such a string and stops. This function, or table, is pretty wild: it can be shown that it grows faster than any computable function. Therefore it is itself non-computable. It's unknowable in a pretty strong sense.
If you don't know what &quot;programming language&quot; means or what programming languages can do, you can just imagine that you're giving a friend a notebook with very precise instructions such that, if your friend follows those instructions, she will end up writing a great number of dots on a very large piece of paper. You needn't assume the friend is a math genius, but you may assume she's immortal, very patient and capable of following simple instructions like &quot;write the number 6 on the yellow sticky note&quot; or &quot;read the number on the orange sticky note, erase it and replace it with the next counting number&quot;. It's fine if she can't count beyond a billion herself: with enough sticky notes we can help her overcome that.