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.
Wouldn't the simulation of multi-tape Turing machine on the single-tape Turing machine be a lot simpler if the virtual tapes were just interleaved. Like [a][1][c][a][0][c][b][1][c]... Then you don't have to move anything around and it would be much simpler.
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'.
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.
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
I only use my favorite programming language. I never bothered with Turing Machines. They are crap. But not really Turing's fault. They did not have personal computers back in 1936 (for obvious reasons).
I can't understand why we introduce a new mechanism / model / "hardware" for enumerators - why do we need a "printer" mechanism when we can already write to the tape? We could just define some spans(s) of the tape as being the "output strings", no? That even happens to map directly to how most computer hardware lets the CPU communicate with peripherals - you simply write/read from a certain predefined address space in memory.
@55:13 You can feel Professor's heartache at this point. We all do. 😥
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.
Loved this lesson!
29:34
Making the NFA inside M to a DFA won't work because starting state is needed to process any further.
Wouldn't the simulation of multi-tape Turing machine on the single-tape Turing machine be a lot simpler if the virtual tapes were just interleaved. Like [a][1][c][a][0][c][b][1][c]... Then you don't have to move anything around and it would be much simpler.
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.
Minute 38:55 , why would M get stuck on a w_i? We have a DTM and the string w_i has a fixed length. So it would halt
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).
At 42:10, why is Zigma * used in simulating M, can't we just directly use A to do it?
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
legend
Church lived 2 of Turing's lifetimes 92 vs 42
Very sad to think how much life was stolen from Turing (and how many potential developments were thus stolen from us all)
I only use my favorite programming language. I never bothered with Turing Machines. They are crap. But not really Turing's fault. They did not have personal computers back in 1936 (for obvious reasons).
what are these obvious reasons?
I can't understand why we introduce a new mechanism / model / "hardware" for enumerators - why do we need a "printer" mechanism when we can already write to the tape? We could just define some spans(s) of the tape as being the "output strings", no? That even happens to map directly to how most computer hardware lets the CPU communicate with peripherals - you simply write/read from a certain predefined address space in memory.
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.
33:08
52:49
7:00
I didn’t expect that MIT open courseware offers Japanese subtitles
That’s automatic translation , maybe you are in Japan ?
Oh that was automatic translation
Michael, do you think Alan Turing was a top or bottom?