6. TM Variants, Church-Turing Thesis 

That'd require the machine to know from the head's actual position which simulated tape it is on, ie. able to count and track the left-right movements. Not necessarily 'simpler'.

@@zsoltbr 1:10:00 can u guys solve this projection problem

Sounds simpler. You could also have each tape symbol be in the cartesian product of the given tape alphabets, e.g.: [a, A, 0][b, Q, 4][p, C, 8] Probably you want to wrap this in two special symbols "begin" and "end" (or "^" and "$" or whatever), and for each triple of symbols also have three bits saying whether head 1/2/3 is there. Then have the real head run back and forth between "begin" and "end", simulating each given machine when you encounter its head. Push out the boundary markers one step when one of the Turing machines reaches a new tape location. I believe every construction is messy. I'm not sure which is the least messy.

The way Turing was heinously abused always reminds me of Stephen Jay Gould's quote about the would-be geniuses of the world toiling in sweatshops and cotton fields. Not only do unrecognised and un-nurtured geniuses suffer, but so do contemporaneously-celebrated geniuses who possess any attribute offensive to the ruling class. Even Einstein *himself* was the subject of a 1,500-page dossier from the FBI for being a socialist (and a relatively non-revolutionary one, at that). The antisemitism that forced so many Jews, including Einstein, to flee Europe in WWII is still thriving today in the Allied countries which denied sanctuary to Jewish refugees. I hope one day we live in a world free from oppression and bigotry and stifling of intellectual progress. The fact that Churchill, the monstrous genocidaire who oversaw Turing's murder, is honoured on a banknote shows just how far we have yet to go. All programmers need to help the fight against homophobia, sexism, transphobia, racism, and autocracy, because our field is full of Churchills denying the discovery of Turings and Einsteins.

@@gloverelaxis very well said.

No because length of the string doesn't determine whether T.M will halt or not, it's the design of the T.M. itself and the set of strings that it reads that decide whether there are input that make it go in an infinite loop so if you go in a sequence for strings of a T.M. **Recognisable** language then there's a chance you come across a string that makes the machine never halt hence your proof or construction gets stuck

You're confusing a deterministic finite automata with a deterministic Turing Machine. If you given a DFA an input with finite length, it will certainly terminate and never get stuck. However, input string length for Turing Machines is irrelevant in determining whether or not the input string would halt or not. Since we are talking about Turing-recognizers, we have no guarantee that the Turing machine will halt on every string over the input language. So for any given w_i, it's always possible for the Turing-recognizer to loop given w_i as a string. The trick of running every input w_i in the input language "in parallel" circumvents the issue because string that cause the recognizer to loop will keep running (reject those strings via looping) and strings for which the recognizer does halt will be either accepted or rejected (and accepted or rejected respectively by the enumerator).

Couldn't that possible be circular logic? We use precisely the strings in a language that we are trying to show a machine accepts to show that that machine recognizes that language. I'm not sure though

I think it's because we need to simulate M's failures/rejections as well as its acceptances. If we only use strings inside A, the most we can prove is that our simulator accepts every string that M accepts - we can't prove our simulator rejects strings which M rejects.

A is the set which is defined by Sigma*, Sigma* is more descriptive as to what A consists of which is Star closure on the set of Alphabet including empty symbol

Very sad to think how much life was stolen from Turing (and how many potential developments were thus stolen from us all)

Sure you can and at the point where you state "consider this part of the tape as an outpur and print it" you'd have an enumerator.

Because an enumerator is a generator that takes no input and its output purely depends upon the construction of the T.M.