That depends what you mean by “computational problems”. In its usual definition, a Turing machine takes a single input string, and provides a single bit as output: “Accept” or “Reject”. (It may also of course run forever without providing an answer.)
For example, the question, “What is the shortest path through this list of cities?” isn’t possible to encode directly into a standard Turing machine. Instead, the Turing machine can answer, “Is there a path through this list of cities with length at most k?”, for some constant k.
If you don’t like this, there are ways to modify the definition of a Turing machine. But for the purposes of studying computational complexity, all reasonable definitions seem to be equivalent.
I think the machine halting can be interpreted as accepting and you mgiht be allowed to leave a number on the tape.
I was wondering whether cases like the halting problem might be intedresting edgecases but TMs are not especially inferior. Church-turing thesis is about there not being anything interesting missed by what is captured by machines.
That depends what you mean by “computational problems”. In its usual definition, a Turing machine takes a single input string, and provides a single bit as output: “Accept” or “Reject”. (It may also of course run forever without providing an answer.)
For example, the question, “What is the shortest path through this list of cities?” isn’t possible to encode directly into a standard Turing machine. Instead, the Turing machine can answer, “Is there a path through this list of cities with length at most k?”, for some constant k.
If you don’t like this, there are ways to modify the definition of a Turing machine. But for the purposes of studying computational complexity, all reasonable definitions seem to be equivalent.
I think the machine halting can be interpreted as accepting and you mgiht be allowed to leave a number on the tape.
I was wondering whether cases like the halting problem might be intedresting edgecases but TMs are not especially inferior. Church-turing thesis is about there not being anything interesting missed by what is captured by machines.