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

Browse archives
Active forum topics 
Recent comments
17 weeks 4 days ago
17 weeks 4 days ago
17 weeks 4 days ago
39 weeks 5 days ago
44 weeks 16 hours ago
45 weeks 4 days ago
45 weeks 4 days ago
48 weeks 2 days ago
1 year 6 days ago
1 year 6 days ago