Hacker News new | ask | show | jobs
by pdkl95 3305 days ago
> You can not do so because Turing machines are universal.

Just because Turing machines are universal making it possible to write a program that asks a question about another type of Turning machine doesn't mean that question is decidable.

1 comments

Show a Turing machine programmed with ZFC axioms that can do something that a Turing machine programmed with PE can not do. If a Turing machine programmed with PE can simulate the Turing machine with ZFC and thus give the same answer, then I state that the program with ZFC is nothing of the sort.
The paper[1] I linked to in my other post shows that you cannot perform such a simulation because it is undecidable. (Specifically, BB(N >= 1919) is provably undecidable in ZFC).

[1] http://www.scottaaronson.com/blog/?p=2725

I read that when it came out, but I don't see how that is relevant to this question. The link provides a program for a Turing machine that probes ZFC. So can you create a Turing machine that probes ZFC, but can't be proven not to halt? The link emphatically says yes! And it also puts some bounds on the number of states necessary to program such a machine.

Please show how that paper describes a Turing machine 'programmed with PE' can't simulate a Turing machine 'programmed with ZFC'?

Perhaps we are arguing over what 'programmed with PE' or 'programmed with ZFC' means? The parent post seemed to claim that it was possible to construct a physical computer with the axioms of ZFC built-in so to speak. As opposed to one with PE built-in. Which obviously calls into question the parent post understanding of what exactly idealized Turing machines are.