hello, world
A. First Edition
This is first edition of my "hello, world" program and it is actually not exactly a program, but a problem.
This is from our text book of comp335. The problem is designed to prove there is something that
computer cannot do.
Suppose we have a program called "turing" which takes another program, say "input", as input and
output something according to the output of that "input" program. Then the author of book tried to
prove such kind of "turing" program cannot exist.
Suppose the "turing" program will output "yes" if the "input" program output "hello, world" and for
all other kinds of output (even no output is considered to be a kind of output.) of "input", "turing"
will output "hello, world". Then if we use "turing" itself as its input program, what happens?
In the text book, they said, assume "turing" output a "yes", then according to above rule, the input
program should have output a "hello, world". And this input program is "turing" itself which by
assumption has output a "yes". This leads to contradiction of our assumption of output of "turing"
is a "yes". So in conclusion such a program can not exist. Then it proves that some kind of program
is impossible to write which means there is something cannot be done by computer.
Is it a kind of problem that computer cannot accomplish? I always feel suspect about it. Not for
the correctness of proof, but for the problem itself. The following is my idea:
1. The concept of "program" and "process": We all know that "program" is usually referred to the
source code which defines the run-time behavior of our program. Whereas "process" is the run-time
entity of program and it is described by a series of states value which are stored in operating
system. One program can have many different processes running at same time. And the behavior of each
process may vary depending on its particular running environment, even they are both originated from
same "program".
2. The "turing" program is the source code that defines the property of its all running processes---
output "yes" for input "hello, world" and output "hello, world" for non else. However, does it mean
it can only have one running "process"? Certainly not! We all know for a fixed time and space there
can only exist one object. Same thing happens for computer environment! One "turing" program (or
process, if you like.) is using another "turing" program (process) output as its input. This itself
implies that it should be considered as two processes, or at least one process but running
continually with two different input and output. Suppose for simplicity sake, we create two
independent "turing" processes, one accept another one's output as its input. Why should we confuse
ourselves by the particular assumption in the proof that "assume "turing" output a "yes", then
according to above rule, the input program should have output a "hello, world". And this input
program is "turing" itself which by assumption has output a "yes". This leads to contradiction of
our assumption of output of "turing" is a "yes"". Quite obviously the "turing" program has two
independent processes which cannot have the same input all the time. Then why bother to say there
exists a contradiction?
//The following is just original what is going on in my mind and you can ignore them now.
/*
Is it a kind of problem that computer cannot accomplish? I always feel suspect about it. Not for
the correctness of proof, but for the problem itself. We know that the problem defined by author is
like a function, or more commonly, a logic implication:
If input is "hello, world", then output is "yes".
Let's define as following propositions:
Input()={ The input of "turing" program is "hello, world".}
Output()={ The output of "turing" program is "yes".}
Then it is like this implication:
Input()==>Output() is equivalent to: Input()<==>Input()&&Output()
This says that Input() is true then both Input() and Output must be true. But we force our "turing"
program to be in such an awkward situation that the "input" of this "turing" program is same as the
"output" of it. Do we force the functional relation of "turing" becoming a "loop"? Can we do it?
*/
/*
//The below is non-sense and disregard them!!
For this above implication, can we have converse implication such as following???
If the output is "yes", then the input is "hello, world".
The above one is obviously not possible true given first implication.
Then why should we ask computer to do something we know impossible even for logic or for brain of
human?
*/
E.Further improvement
F.File listing
1. turing.cpp (main)
file name: turing.cpp
#include <iostream>
using namespace std;
char* turing(char* input);
int main()
{
char* hello="hello,world";
char* yes="yes";
cout<<turing(turing(hello))<<endl;
cout<<"now if it is yes?\n";
cout<<turing(turing(yes))<<endl;
return 0;
}
char* turing(char* input)
{
if (strcmp(input, "hello, world")==0)
{
return "yes";
}
else
{
return "hello, world";
}
}
Here is the result: The result shows for any input, "hello, world" or not "hello, world", in this case "yes",
the output of function "turing" is always "yes".
yes
now if it is yes?
yes
Press any key to continue
Here is the result: This is more output if we change the main function like following:
int main()
{
char* hello="hello,world";
char* yes="yes";
cout<<turing(turing(hello))<<endl;
cout<<"now if it is yes?\n";
cout<<turing(turing(yes))<<endl;
cout<<"what's more, if we use output of turing as input once more!\n";
cout<<turing(turing(turing(hello)))<<endl;
cout<<"now change it to yes\n";
cout<<turing(turing(turing(hello)))<<endl;
return 0;
}
This is more intiguing! As why is that? Is it a logic? I mean true or false really mean something to
the world or not? Suppose we change all "true" to "false" of our world, what will happen?
yes
now if it is yes?
yes
what's more, if we use output of turing as input once more!
hello, world
now change it to yes
hello, world
Press any key to continue