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  7775 reads

Browse archives
Active forum topics 
Recent comments
10 hours 54 min ago
14 hours 41 min ago
14 hours 48 min ago
22 weeks 1 day ago
26 weeks 3 days ago
28 weeks 22 hours ago
28 weeks 22 hours ago
30 weeks 5 days ago
35 weeks 3 days ago
35 weeks 3 days ago