1 reactions
Uncomputable functions via undecidable table?
Around the 24:30 mark of this [UC Davis lecture from 2011][0], Dan Gusfield sets up a proof by contradiction with a table T whose rows are computer programs.
He set out to prove the existence of uncomputable functions in a set
Q = { f | f : ℤ+ → {0,1} }
He defines A ⊆ Q as the set of computable functions.
Back to table T. Its rows are computer programs that compute some function in A and columns their values at all ℤ+, but f' (“f-bar” in the lecture) defined as
f'(i) = 1 - fᵢ(i)
appears nowhere in T.
How is T’s definition meaningful if membership for its rows is undecidable?
[0]: https://podcasts.apple.com/us/podcast/theory-of-computation-fall-2011/id585297167?i=1000411462836
#technology
Around the 24:30 mark of this [UC Davis lecture from 2011][0], Dan Gusfield sets up a proof by contradiction with a table T whose rows are computer programs.
He set out to prove the existence of uncomputable functions in a set
Q = { f | f : ℤ+ → {0,1} }
He defines A ⊆ Q as the set of computable functions.
Back to table T. Its rows are computer programs that compute some function in A and columns their values at all ℤ+, but f' (“f-bar” in the lecture) defined as
f'(i) = 1 - fᵢ(i)
appears nowhere in T.
How is T’s definition meaningful if membership for its rows is undecidable?
[0]: https://podcasts.apple.com/us/podcast/theory-of-computation-fall-2011/id585297167?i=1000411462836
#technology
| 33,000 mlx | |
| 32 | |
| 1 |