Like any fsm, there is an initial state and a set of final states. The machine's read/write head is positioned at the start of its semi-infinite tape, which contains the binary input string at the far left. The rest of the tape is initialized to blank,a default readonly character. Based on the current state and input character, the tm enters a new state, writes a character (0 or 1) on the tape, and moves the head left or right. If the head moves off the left end of the tape the tm halts, and the word is not in the language.
Languages recognized by such machines are recursively enumerable, or re. We assume the machine terminates upon success, and since the machine may manipulate symbols for years after scanning the input string, we also include failure states that terminate. If a language is recognized by some tm that always halts, indicating failure or success, the language is recursive.
The complement of a recursive language is recursive; just reverse the outputs.
If the complement of an re language is re, we can run both tms in parallel to show that the language is actually recursive.
Recursive languages are closed under intersection. Run both tms in parallel and wait for both of them to say yes.
The read/write alphabet can include any finite number of symbols, say 2k. To simulate such a machine, let a binary tm read k bits as a block, proceeding to 1 of 2k states based on the state it started in. Having read the last bit in the block, it backs up to the beginning of the block, writing the new symbol in reverse. Then it moves left k squares or right k squares, ready for the next transition. We can return to our convention of using digits and upper case letters for the language alphabet, or any other finite set of symbols for that matter. Remember that there is also a blank symbol, which can be read, but cannot be written. This looks like k blanks in a block under our simulation. These are overwritten with zeros, and then the new symbol in reverse, as the tm makes its next block-step.
Now that arbitrary alphabets are permitted, let's bring in some new features.
One can simulate a bi-infinite tape tm by enhancing the alphabet of a semi-infinite tape tm, so that each character has two independent components, and the tape has two virtual tracks. When the head would be to the right of the origin, the simulater follows all the original transitions, modifying the upper track and preserving the lower track. A special marker at 0 allows the simulater to detect the left edge, and switch to the lower track. The state transitions are the same, but the directions are reversed, so that left means right and right means left.
A tm with k independent heads on k tapes can be simulated by a tm using k tracks on one tape. Each step involves a sweep from the leftmost head position to the rightmost, taking action wherever a head marker appears. Head markers must move with the heads, and a counter must determine when all virtual heads have been dealt with. Unlike the previous simulations, this represents a quadratic slow down. In other words, a tm that actually has independent heads can speed up certain computations.
What if a tm can move about in 2 dimensions, reading and writing characters on an infinite piece of paper? Just as a computer stores a k-dimensional array in linear memory, a tm can simulate a k-dimensional tm by defining delimitors that denote end of row, column, layer, etc. The entire tape must be reformatted when the virtual head leaves the established rectangular region in Rk, but nobody said the simulation was fast.
Finally, a tm can simulate a cpu, complete with instructions (opcodes), registers, and a random access memory. The input is a series of opcodes and data, similar to assembly language. If opcode 23 means fetch into register x, then 23,769 causes the cpu tm to magically fetch the integer from location 769 and stor it in register x. Arbitrary integers act as memory addresses and memory contents. The cpu includes arithmetic operations such as plus and times, and indirect reference, fetching or setting the contents of the address in a designated register. (These are pointers in C.) Suddenly we have jumped from a toy to a magical computer (sans peripherals), more powerful than any cpu on the market today. Still, it can be simulated by a tm.
The address/content pairs are stored on the tape, and there are only a finite number of them. (Our random access memory has become sequential.) The registers are just special memory locations, and are stored in pairs on the tape. The tm reads an opcode and moves to one of several action states. From there it scans the tape looking for the contents of the named register or memory location, and copies that data into, or adds that data to, or subtracts that data from, the contents of some other register or memory location. It has to perform these operations in finite chunks, analogous to bytes or words in today's computers. To copy a 50 byte number from one location to another, the simulator sweeps between the two locations 50 times, leaving markers to indicate where it left off. And if the destination only has space for 49 bytes, the tm has to clear that address/content pair and leave it empty, and move to the end of the tape to write a new address/content pair, with the new, larger integer.
The tm leaves a marker at the current opcode, similar to the instruction pointer in a modern cpu. When it finishes an instruction, it returns to its program and executes the next instruction, carrying the instruction pointer along.
The state machine for such a simulator is mind numbing in its complexity, but then again, the pentium chip has half a million transistors.
I'm not going to prove any of the above in rigorous detail; that would take volumes! If you walk away, and think about it for a few days, you will probably believe that it can all be done. The state machine would be huge, but an abstract computer with opcodes, and an unbounded random access memory, and an input program (software) on its tape, can all be simulated by a tm. If a computer can in turn simulate a neural net with 10 billion nodes, and if such a neural net is an accurate model for the human brain, (this last assertion is uncertain at best), then perhaps a tm can think, just like you and I.