Turing completness is being typically proved via reduction to already proved Turing-complete machine.
Can the same be obtained by showing, that the machine in question is capable of generating arbitrary output – if proper input is given?
Tell me more
×
Computer Science Stack Exchange is a question and answer site for
students, researchers and practitioners of computer science. It's 100% free, no registration required.
|
|
|||||||
|
|
Turing-completeness means that the machine model in question can compute everything that is computable. That means that for every computable function $f$, there is a corresponding program for your model which behaves "like" $f$, where I put the quotes since the input and output may look differently. Showing that the machine can generate arbitrary output is hardly enough - consider the machine model which executes only one program, copying its input to its output. |
|||
|
|
