20:56 From a "practical programing point of view" all this comes from the diference between "read the string" and "execute/print the string" (B "figures out" A by execution of the string B which is on the tape). But what confuses me about this "simple" example, is that you need someone to give you the function out of the system (or ) .. It's like you are running the program in an execution environment whit some built in functions that you can use. The turing machine only reads/writes but it doesn't have built in the execute/print instruction ..
This is a lecture with many confusing proofs. To prove SELF, we can use a standard programming language to open its own source code and print it. So using the lemma, Pw = "Print w on the tape and halt". I claim P_ is a SELF program. This is almost the same as later recursive proofs that defines TM R = "Get own description then print ". I was confused that why the size of MIN_{TM} is infinite necessary means there is an arbitrary length TM. But I think the reason is the number of any finite length TM is finite, so infinite number of MIN_{TM) must include any length TM. But then the gap will be why MIN_{TM} is infinite? It probably is easy to create a minimum TM of any length such as print a sequence of random numbers, but any better argument? Overall with R = "Get own description , ... " recursive proof become easier to construct. So to facilitate easier construction of proofs one probably is worthwhile to study what are allowed (macro) actions inside a Turing machine, such as "get own description", "run", "enumerate", "print"?
You can’t just read a program’s source, that’s basically cheating as now you ask the OS to give you that code. The whole point of all this is that a program can self replicate without relying on any other external mechanisms, just by itself, only having the ability to write something. You can read a wiki article about quines which explores this topic.
1:14:50 i have been thinking about this question for days which is related to pset2 #4 [projection of decidable iff T-recognizable].How can we be sure that proofs itself doesn't cause looping.In the sense of projection problem How can i be sure that recognizable T is trying new inputs and not wasting its time with a pointless circles in specific pair of (x,y)
i think all of those unprovable, but true statements are non-constructive, meaning they will never be of any relevance for what we humans use maths for.
I'm confused by the proof of the fixed-point theorem. What happens if f is the identity transformation? Then, R will go into an infinite loop. Or, what if f adds the line "print 'hello'" or adds 1 to whatever R computes? The proof doesn't seem to cover that possibility either.
If f is an identity transformation, that only means every points are fixed points. You can pick any f, but you can not specify R. R has to be specific as shown in the proof. Simulate and simulate (S, w) in the proof did give the same result. But I agree, if you want to implement the same thing on a standard computer, it will be very confusing. So it probably is fair to ask what does such theorem really mean?
was watching some gaming vids, fell asleep with autoplay on and woke up to this
This must've been an awesome video to wake up too.
Incredibly fascinating! Probably the best course I have seen on this channel.
as reference to self reproduction part see Douglas Hofstadter's Godel Escher Bach( self-reference, self-reproduction)
20:56 From a "practical programing point of view" all this comes from the diference between "read the string" and "execute/print the string" (B "figures out" A by execution of the string B which is on the tape). But what confuses me about this "simple" example, is that you need someone to give you the function out of the system (or ) .. It's like you are running the program in an execution environment whit some built in functions that you can use. The turing machine only reads/writes but it doesn't have built in the execute/print instruction ..
Ok, the lemma seems to be the built in Print function availabe..
This is a lecture with many confusing proofs.
To prove SELF, we can use a standard programming language to open its own source code and print it. So using the lemma, Pw = "Print w on the tape and halt". I claim P_ is a SELF program. This is almost the same as later recursive proofs that defines TM R = "Get own description then print ".
I was confused that why the size of MIN_{TM} is infinite necessary means there is an arbitrary length TM. But I think the reason is the number of any finite length TM is finite, so infinite number of MIN_{TM) must include any length TM. But then the gap will be why MIN_{TM} is infinite? It probably is easy to create a minimum TM of any length such as print a sequence of random numbers, but any better argument?
Overall with R = "Get own description , ... " recursive proof become easier to construct. So to facilitate easier construction of proofs one probably is worthwhile to study what are allowed (macro) actions inside a Turing machine, such as "get own description", "run", "enumerate", "print"?
You can’t just read a program’s source, that’s basically cheating as now you ask the OS to give you that code. The whole point of all this is that a program can self replicate without relying on any other external mechanisms, just by itself, only having the ability to write something. You can read a wiki article about quines which explores this topic.
1:14:50 i have been thinking about this question for days which is related to pset2 #4 [projection of decidable iff T-recognizable].How can we be sure that proofs itself doesn't cause looping.In the sense of projection problem How can i be sure that recognizable T is trying new inputs and not wasting its time with a pointless circles in specific pair of (x,y)
Are there true statements that cannot be proven, but we can reason that they are true anyway, without using the Recursion Theorem?
i think all of those unprovable, but true statements are non-constructive, meaning they will never be of any relevance for what we humans use maths for.
Isn't that like the Godels Incompleteness Theorem
I'm confused by the proof of the fixed-point theorem.
What happens if f is the identity transformation? Then, R will go into an infinite loop.
Or, what if f adds the line "print 'hello'" or adds 1 to whatever R computes? The proof doesn't seem to cover that possibility either.
If f is an identity transformation, that only means every points are fixed points.
You can pick any f, but you can not specify R. R has to be specific as shown in the proof. Simulate and simulate (S, w) in the proof did give the same result.
But I agree, if you want to implement the same thing on a standard computer, it will be very confusing. So it probably is fair to ask what does such theorem really mean?
Binging this shit like its Netflix
Aint got enough braincells to nail it
Gotta keep going to stay off the streets
31:25
Companion of this lecture, could be this video: th-cam.com/video/6avJHaC3C2U/w-d-xo.html