Using the diagonalization argument requires endless input, which of course would not be computable. Try it with finite length sets (which in turn would only be relevant for very limited limits of 'finite').
The assumptions given throughout this lecture (listed below) seem non-sensical. Someone please help! #1. An infinite string is computable. (1:02) - The only definition provided for "computable" pertains to portions infinite strings. Most computing involves finite objects, and even when "computing" involves irrational numbers, we never need to compute all of the digits. Why does this definition of "computable" make sense? #2. There is an (countably) infinite number of procedures. (2:10) - In the world we program in, with restrictions on size, how can there be an infinite number of procedures? A big finite number, yes, but infinite? #3. There are uncountably many infinite binary strings that are non-computable. (2:56) - Yes, there are uncountably many irrational numbers. Most un-"computable" per previous definition. What does that have to do with real-world computers halting? #4. HALT is described by a program returning when it is given it's own source code as input. (Slide 7, 5:26) - ?? This is, again, a very strange definition for HALT. Why is this input the only case considered? #5. A type-checking program C exists based only on program text s. (10:18) - Is there any perfect type-checking procedure that can exist without knowing anything about the inputs to s? These explanations seem very imprecise and contrived. What am I missing?
#1. I think that he means there is a string that is infinite, but only commutable to the n and not that the whole of the string can be held in memory and parsed. Example: Fibonacci sequence can be described as an infinite string. Yet we can compute the nth Fibonacci of this infinite string. We can't know all its digits at one time, but we can compute any of the digits we chose. Hence a commutable infinite string.
#2. There are an infinite number of stories one can choose to write does not mean one will write all the infinite stories. The number of procedure we can choose from are endless and obviously we can't run endless procedures. Example: There is a set of infinite number of procedures that divide the number 3. I write a procedure that divides 3 by 1 or 2 or 3 ... This infinite set itself is only a subset of infinite procedures sets that exist. Again they not running all at once.
# 3 Non-computable means that the machine will never halt. The computer can halt (computable) if it reaches a result, asks for more input, or returns with an error.
#5 I agree that the word "perfect" is not the best choice of word; perhaps he could have used complete. A type checker that can catch all typing errors types one can produce while writing a program. Similar to write a program that adds any two integers you can type in is a complete adder(perfect). If I exclude negative integers or integer 1, it's no longer complete.
Using the diagonalization argument requires endless input, which of course would not be computable. Try it with finite length sets (which in turn would only be relevant for very limited limits of 'finite').
Albert R. Meyer Sir ! simply great!
The assumptions given throughout this lecture (listed below) seem non-sensical. Someone please help!
#1. An infinite string is computable. (1:02)
- The only definition provided for "computable" pertains to portions infinite strings. Most computing involves finite objects, and even when "computing" involves irrational numbers, we never need to compute all of the digits. Why does this definition of "computable" make sense?
#2. There is an (countably) infinite number of procedures. (2:10)
- In the world we program in, with restrictions on size, how can there be an infinite number of procedures? A big finite number, yes, but infinite?
#3. There are uncountably many infinite binary strings that are non-computable. (2:56)
- Yes, there are uncountably many irrational numbers. Most un-"computable" per previous definition. What does that have to do with real-world computers halting?
#4. HALT is described by a program returning when it is given it's own source code as input. (Slide 7, 5:26)
- ?? This is, again, a very strange definition for HALT. Why is this input the only case considered?
#5. A type-checking program C exists based only on program text s. (10:18)
- Is there any perfect type-checking procedure that can exist without knowing anything about the inputs to s?
These explanations seem very imprecise and contrived. What am I missing?
#1. I think that he means there is a string that is infinite, but only commutable to the n and not that the whole of the string can be held in memory and parsed. Example: Fibonacci sequence can be described as an infinite string. Yet we can compute the nth Fibonacci of this infinite string. We can't know all its digits at one time, but we can compute any of the digits we chose. Hence a commutable infinite string.
#2. There are an infinite number of stories one can choose to write does not mean one will write all the infinite stories. The number of procedure we can choose from are endless and obviously we can't run endless procedures. Example: There is a set of infinite number of procedures that divide the number 3. I write a procedure that divides 3 by 1 or 2 or 3 ... This infinite set itself is only a subset of infinite procedures sets that exist. Again they not running all at once.
# 3 Non-computable means that the machine will never halt. The computer can halt (computable) if it reaches a result, asks for more input, or returns with an error.
#4 The program (source code) itself returns. P(s) is the program that halts. He never said what you claimed.
#5 I agree that the word "perfect" is not the best choice of word; perhaps he could have used complete. A type checker that can catch all typing errors types one can produce while writing a program. Similar to write a program that adds any two integers you can type in is a complete adder(perfect). If I exclude negative integers or integer 1, it's no longer complete.
"The infinite sets, some people think they are romantic...." :D
nice explanation