|
|
|
|
|
|
by nyrikki
511 days ago
|
|
|
Turing machines are typically described as having an infinite tape. It may not be able to access that tape in finite time, but the tape is not bound to a finite tape But it doesn't matter, it is an abstract model of computation. But it doesn't matter Church–Turing thesis states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine. It doesn't matter if you put the algorithm on paper, on 1 or k tapes etc... Rice's theorem I mentioned above is like Scott–Curry theorem in Lambda calculus. Lambda calculus is Turing complete, that is, it is a universal model of computation that can be used to simulate any Turing machine. The similar problems with 'trivial properties' in TMs end up being recursively inseparable sets in Lambda calculus. |
|
|