User loginNavigation 
Computational equivalent of incompleteness theorems?Godel's Incompleteness Theorems are wellknown, but I haven't come across any interpretation of incompleteness in terms of computation that aren't typed. neelk's comment is a great example of how it applies to programming language type systems via CurryHoward, but I'm looking for an untyped correspondence, like at the level of the raw lambda calculus or Turing machines. For instance, if I squint, the Halting Problem looks very much like an instance of the first incompleteness theorem. No program H can be constructed which can compute the termination value of every other program, ie. there are programs which halt but for which H cannot compute that fact. Wikipedia isn't much help here, implying there is some established connection, but not describing it in any accessible way or providing useful pointers. Has such a correspondence been established? Hopefully I'm not spewing nonsense and someone can point me in the right direction! By naasking at 20100825 02:34  LtU Forum  previous forum topic  next forum topic  other blogs  5467 reads

Browse archivesActive forum topics 
Recent comments
5 hours 39 min ago
6 hours 12 min ago
6 hours 39 min ago
7 hours 1 min ago
7 hours 9 min ago
10 hours 47 min ago
11 hours 19 min ago
14 hours 23 min ago
14 hours 48 min ago
16 hours 10 min ago