Non Computable Functions And Godel's Theorem

Click For Summary
The discussion explores the relationship between non-computable functions and Gödel's theorem, initiated by a reflection on the mathematical contributions of Ramanujan and Bertrand Russell. It presents a proof demonstrating that not all functions from natural numbers to binary values are computable, leading to the conclusion that there exist non-computable functions. The proof utilizes a diagonalization argument similar to Cantor's, illustrating that if a function g is computable, it leads to a contradiction regarding its own value. The conversation also touches on the distinction between completeness and decidability, emphasizing that while some statements may be undecidable, they do not necessarily imply incompleteness in a formal system. Ultimately, the discussion highlights the significance of computing concepts in understanding Gödel's results.
  • #31
you lost me here.

bhobba said:
Well all computer programs are countable because they use a finite number of characters and are of finite length.

Who wrote the internet? What is a computer program if not the internet? Is it done? It's like you are drawing a line across some joint of a thing and then counting the bones on one side.
 
Technology news on Phys.org
  • #32
Jimster41 said:
What is a computer program if not the internet?

I suggest you look into Turing Machines.

Thanks
Bill
 
  • #33
Jimster41 said:
you lost me here.
Who wrote the internet? What is a computer program if not the internet? Is it done? It's like you are drawing a line across some joint of a thing and then counting the bones on one side.
As @bhobba points out, you do not seem to have the technical background yet to be throwing out a philosophical question in this technical thread. Please do some reading about the technical aspects of this discussion, and then if you have pertinent questions, go ahead and post them in context. Thank you.
 
  • Like
Likes bhobba

Similar threads

  • · Replies 1 ·
Replies
1
Views
2K
Replies
29
Views
5K
  • · Replies 63 ·
3
Replies
63
Views
4K
  • · Replies 0 ·
Replies
0
Views
1K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 0 ·
Replies
0
Views
512
  • · Replies 0 ·
Replies
0
Views
1K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 28 ·
Replies
28
Views
4K
  • · Replies 12 ·
Replies
12
Views
2K