last day (15 days later) » 

01:11
45
A: Is a Turing Machine "by definition" the most powerful machine?

David Richerby I agree that a Turing Machine can do "all the possible mathematical problems". Well, you shouldn't, because it's not true. For example, Turing machines cannot determine if polynomials with integer coefficients have integer solutions (Hilbert's tenth problem). Is Turing Machine “by defini...

If we could "use" without building a machine more powerfull than the one of Turing we could not anyway use it or communicate its results. The limit in Turing Machines is a formal limit caused by the fact you want Yes/No answers, It is not about the machine but how we interact with the machine. If we assume we could communicate certain stuff we have paradox which are not in the machine itself, but in the result they give.
@DarioOO I don't understand what you mean by using a machine without building it. How can you use it if it doesn't physically exist?
Another thing TMs can't do: talk to oracles (i.e. do I/O). In that sense, we can build more powerful models of computation.
We don't know how to build any oracle that would be more powerful than a Turing machine.
@Rhymoid It's not clear what you mean by "more powerful" in that scenario. If you made the user specify their inputs in advance, you could write them on a tape and give the TM read-only access to that tape, only allowing its head to move right. The resulting machine would compute exactly the same functions of its input as a Turing machine.
01:11
I just simply mean that even if we had an oracle, we would not be able to use it @DavidRicherby
"the Turing machine is the most powerful machine that we know, at least in principle, how to build" That's not true, we can also build humans.
@DavidRicherby That wouldn't be an oracle, unless you presume that the oracle already knows what the TM will provide as input.
@Rhymoid Nor is a user providing input and oracle. An oracle always provides the same response to any given prompt.
@DavidRicherby Says who?
@Rhymoid Says Alan Turing. On page 18 of his PhD thesis, he defines "$o$-machines" (which we would call "oracle Turing machines") as having a state $\cal{O}$ which, when enters either jumps to state $t$ or state $f$ according to whether a particular property of the work tape is true or false. Later authors use the same notion.
 
21 hours later…
22:15
@DarioOO This doesn't make sense to me. It sounds like you're saying that oracle machines are fundamentally impossible, even given the existence of an actual oracle. Care to defend that position?

  last day (15 days later) »