3 ms·

> There is an article floating around (posted here multiple times) that says MOV is turing complete [0]. Don't believe this claim - any computer has only acces

> There is an article floating around (posted here multiple times) that says MOV is turing complete [0]. Don't believe this claim - any computer has only access to a finite amount of memory while a Turing machine needs an infinite tape to work. So the proof must be false. In other words: only a mathematically idealized version of MOV might be Turing complete - but this cannot be the MOV that x86 implements.

chrisseaton 7y ago
Cone on... anyone reading the claim knows it has a silent ‘(but obviously with a machine-bound tape)’ at the end of it.
- wolfgke 7y ago
  The class of machines with the ‘(but obviously with a machine-bound tape)’ are even weaker than finite-state machines (because the number of states is bound by a fixed constant instead of "just" assumed to be finite). So if you argue that the silent ‘(but obviously with a machine-bound tape)’ assumption is OK, you argue that it is OK to identify Turing machines with a class of machines that is even weaker than finite-state machines. Any professor for (theoretical) computer science will be horrified by such claims.
  - chrisseaton 7y ago
    If your program finishes without reaching the limit of tape then it doesn’t matter that the tape was limited. It’s not about classes of machines. A machine with a limited tape is a perfect approximation for the proper class of a machine with an unlimited tape if the limit is not reached for all programs you care about. Professors won’t be horrified - they also use the silent parenthetical constraint. Look for example at formal publications like Dolan’s and see how academics talk about it.
msla 7y ago
If you want to be pedantic, let's get pedantic. Turing-completeness isn't a property of computational models, it's a property of problems. A problem is Turing-complete when it cannot be solved by any computational model less powerful than a Turing Machine, or other Turing-equivalent computational system, such as the Lambda Calculus. Moreover, a Turing machine does not have an infinite tape. It has an unbounded tape. Its tape is not limitless, it is extensible, such that a computation cannot fail due to running out of tape. Hey, you wanted to get pedantic. Finally, in practical land, the distinction between Turing-equivalent and non-Turing-equivalent is very relevant to real programming languages: Epigram is pointedly not Turing-equivalent, and therefore it's possible to prove programs in that language will halt. Moving away from Turing-equivalence frees you from the tyranny of the Halting Problem. https://scienceblogs.com/goodmath/2007/01/05/turing-equivalent-vs-turing-co https://scienceblogs.com/goodmath/2007/01/05/turing-equivale... https://en.wikipedia.org/wiki/Epigram_(programming_language) https://en.wikipedia.org/wiki/Epigram_(programming_language)

chrisseaton 7y ago

Cone on... anyone reading the claim knows it has a silent ‘(but obviously with a machine-bound tape)’ at the end of it.

wolfgke 7y ago
The class of machines with the ‘(but obviously with a machine-bound tape)’ are even weaker than finite-state machines (because the number of states is bound by a fixed constant instead of "just" assumed to be finite). So if you argue that the silent ‘(but obviously with a machine-bound tape)’ assumption is OK, you argue that it is OK to identify Turing machines with a class of machines that is even weaker than finite-state machines. Any professor for (theoretical) computer science will be horrified by such claims.
- chrisseaton 7y ago
  If your program finishes without reaching the limit of tape then it doesn’t matter that the tape was limited. It’s not about classes of machines. A machine with a limited tape is a perfect approximation for the proper class of a machine with an unlimited tape if the limit is not reached for all programs you care about. Professors won’t be horrified - they also use the silent parenthetical constraint. Look for example at formal publications like Dolan’s and see how academics talk about it.

msla 7y ago

If you want to be pedantic, let's get pedantic. Turing-completeness isn't a property of computational models, it's a property of problems. A problem is Turing-complete when it cannot be solved by any computational model less powerful than a Turing Machine, or other Turing-equivalent computational system, such as the Lambda Calculus. Moreover, a Turing machine does not have an infinite tape. It has an unbounded tape. Its tape is not limitless, it is extensible, such that a computation cannot fail due to running out of tape. Hey, you wanted to get pedantic. Finally, in practical land, the distinction between Turing-equivalent and non-Turing-equivalent is very relevant to real programming languages: Epigram is pointedly not Turing-equivalent, and therefore it's possible to prove programs in that language will halt. Moving away from Turing-equivalence frees you from the tyranny of the Halting Problem. https://scienceblogs.com/goodmath/2007/01/05/turing-equivalent-vs-turing-co https://scienceblogs.com/goodmath/2007/01/05/turing-equivale... https://en.wikipedia.org/wiki/Epigram_(programming_language) https://en.wikipedia.org/wiki/Epigram_(programming_language)