News for hackers. Stuff that matters.
Re:On Two Views of Computation in Computer Science by readams on Wednesday August 31, 2016 @07:27PM (#12402214)
I'm not really sure I completely understand where the conflict is here. Even in the "machine model" the church-turing thesis "fails spectacularly" once you start adding in unreasonable things like halting oracles. TM+Halting oracle > TM. It's just that the TM+halting oracle doesn't exist in our universe, even though you can define it mathematically.

When building a language, it's similarly easy to introduce "unreasonable" things that either require huge complexity to translate to the machine representation or might even be completely unrealizable in the real world! Even ignoring higher types, compiling a C++ program requires a potentially unbounded amount of work because templates are a turing-complete functional programming language. As stated in the article, just determining if a C++ program is valid is undecidable!

Nothing stops you from designing these languages, but you can't say that Church-Turing fails until you consider also the systems required to actually execute these languages in the real world. If you can't, then your programming language is perhaps an interesting mathematical abstraction, but just as useful ultimately as that TM+halting oracle model of computation.

Re:On Two Views of Computation in Computer Science by j2kun on Wednesday August 31, 2016 @08:27PM (#12402447)
> TM+Halting oracle > TM

Why is this a failure of the Church-Turing thesis? The Church-Turing thesis says, "Anything that can be computed in our reality (i.e. by a human, ignoring resource constraints) can be computed by a TM." TM+Halting oracle doesn't satisfy the hypothesis.

Re:On Two Views of Computation in Computer Science by readams on Thursday September 01, 2016 @01:15PM (#12407084)
It's not a failure of Church-Turing. The whole point of my comment is that you can easy construct more powerful models that are "unreasonable" because they don't exist in our universe. It's the same for programming language models.