Your example of PDA's would require to have them interacting at every step as was said in the FOM list from where everybody is jumping to wrong conclusions. Smith's proof does not suppose any communication.
From the FOM list where most of you jumped to conclusions without even waiting to an official answer from Wolfram Research:
1. Concerning the prize committee, we did not expect them to go
through the details of the proof but to support the reviewers on
technical issues related to their fields of expertise. We would have
been delighted to have had them spend more time on the proof but that
wasn't our expectation. We did talk to people about how to set the
prize up. Basically we needed judgement about their areas and we were
very careful to cover those that could come up in a universality
proof. We are grateful to the committee for covering those areas and
we are happy that they were more active than many such committees.
In the review process, committee members agreed with the Wolfram
Science internal reviewers, while others asked for additional
clarifications (such as fulfilling universality basic requirements for
non-halting machines). All committee members had Alex Smith's proof in
hand for a couple of months. But it was Wolfram staff who did the hard
work to achieve a satisfactory level of verification (between
revisions and revision requests), and we thought that by waiting any
longer we would not have learned more. It helped that a lot of the
proof was submitted in the form of programs that could be run and
analyzed in a systematic way.
Smith's proof is available to everybody, anyone can point out
anything, and it is nice to get the sense that there are people out
there who would be interested in verifying proofs. This is great news,
and if we do other prizes we would definitely like to take advantage
of that. We would be also delighted to hear opinions on how to set up
next prizes.
2. Concerning the definition of universality, a halting state or
halting instruction wasn't a requirement. This is a common usage
nowadays in the field of small universal Turing machines (see detailed
references below), which is a generalization of previous definitions.
If there is no clear definition is because there is no clear-cut,
established procedure to determine when an initial condition is
computationally simple enough to be acceptable. Some would wish
universal computation stick to a finite initial condition with an
unbounded tape filled with "blanks", because that's the only case
where the theory is entirely clear. However, others accept
generalizations such as periodic "blank" words as long as they remain
computationally simple enough (possibly generated in the same fashion
as an unbounded "blank" tape). So Alex Smith's use of a non-periodic
but still sufficiently computationally simple background is a natural
generalization of this sort. The key point is that the background can
be set up without doing universal computation, so the 2,3 machine
itself actually carries out the computation.
One could fairly argue that two non-universal coupled automata can
reach universality, but it would require the couple to interact at
every step, as in Margenstern's nice example [1], but that's very
different from a non-universal second automaton intervening only once
at the first step.
We are glad that this is making a contribution to the discussion on
universality. We expect that others will further clarify what Alex
Smith has done. We particularly hope that his methods can be extended
to other similar proofs.
Accepting that you are not experts in the field but pretending to judge something that of course experts reviewed is a good start. It is nice that people like you think on this problem and possible flaws, though. Of course nobody is changing the well stablished definition of a Turing machine. But it is accepted even by the experts that there is no clear definition on universality. You should follow all the FOM posts and not only those that you think are better to criticise others. The definition of universality has been modify several times (if one can say so, since there is no original or first accepted definition), the first to make a generalization exactly as the used by Alex Smith was Watanabe as early as in the 60's. Alex Sm
From the FOM list:
1. Concerning the prize committee, we did not expect them to go
through the details of the proof but to support the reviewers on
technical issues related to their fields of expertise. We would have
been delighted to have had them spend more time on the proof but that
wasn't our expectation. We did talk to people about how to set the
prize up. Basically we needed judgement about their areas and we were
very careful to cover those that could come up in a universality
proof. We are grateful to the committee for covering those areas and
we are happy that they were more active than many such committees.
In the review process, committee members agreed with the Wolfram
Science internal reviewers, while others asked for additional
clarifications (such as fulfilling universality basic requirements for
non-halting machines). All committee members had Alex Smith's proof in
hand for a couple of months. But it was Wolfram staff who did the hard
work to achieve a satisfactory level of verification (between
revisions and revision requests), and we thought that by waiting any
longer we would not have learned more. It helped that a lot of the
proof was submitted in the form of programs that could be run and
analyzed in a systematic way.
Smith's proof is available to everybody, anyone can point out
anything, and it is nice to get the sense that there are people out
there who would be interested in verifying proofs. This is great news,
and if we do other prizes we would definitely like to take advantage
of that. We would be also delighted to hear opinions on how to set up
next prizes.
2. Concerning the definition of universality, a halting state or
halting instruction wasn't a requirement. This is a common usage
nowadays in the field of small universal Turing machines (see detailed
references below), which is a generalization of previous definitions.
If there is no clear definition is because there is no clear-cut,
established procedure to determine when an initial condition is
computationally simple enough to be acceptable. Some would wish
universal computation stick to a finite initial condition with an
unbounded tape filled with "blanks", because that's the only case
where the theory is entirely clear. However, others accept
generalizations such as periodic "blank" words as long as they remain
computationally simple enough (possibly generated in the same fashion
as an unbounded "blank" tape). So Alex Smith's use of a non-periodic
but still sufficiently computationally simple background is a natural
generalization of this sort. The key point is that the background can
be set up without doing universal computation, so the 2,3 machine
itself actually carries out the computation.
One could fairly argue that two non-universal coupled automata can
reach universality, but it would require the couple to interact at
every step, as in Margenstern's nice example [1], but that's very
different from a non-universal second automaton intervening only once
at the first step.
People using universality generalizations of this sort:
[1] Manfred Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, November 1996.
[2] Manfred Kudlek and Yurii Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory (DLT) 2001, vol. 2295 of LNCS, pp. 311-318, Vienna, May 2002. Springer.
[3] Maurice Margenstern and Liudmila Pavlotskaya. On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation, 13(2):133-202, April 2003.
[4] Claudio Baiocchi. Three small universal Turing machines. In Maurice Margenstern and Yurii Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pp. 1-10, Chisinau Moldavia, May 2001. Springer.
[5] Turlough Neary and Damien Woods. Four small universal Turing machines. Machines, Computations, and Universality (MCU), volume 4664 of LNCS, pp. 242-254, Orleans, Fran
Well, that's a good start: you accepting you are not an expert in the field but pretending to judge something that of course experts reviewed. It is nice that people like you think on this problem and possible flaws, though. Of course nobody is changing the well stablished definition of a Turing machine. But it is accepted even by the experts that there is no clear definition on universality. You should follow all the FOM posts and not only those that you think are better to critic others. The definition of universality has been modify several times, the first to make a generalization exactly as the used by Alex Smith was Watanabe as early as in the 60's. Alex Smith contribution is a generalization of the same sort. If you want some references feel free to check these and then reply again:
[1] Manfred Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, November 1996.
[2] Manfred Kudlek and Yurii Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory (DLT) 2001, vol. 2295 of LNCS, pp. 311-318, Vienna, May 2002. Springer.
[3] Maurice Margenstern and Liudmila Pavlotskaya. On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation, 13(2):133-202, April 2003.
[4] Claudio Baiocchi. Three small universal Turing machines. In Maurice Margenstern and Yurii Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pp. 1-10, Chisinau Moldavia, May 2001. Springer.
[5] Turlough Neary and Damien Woods. Four small universal Turing machines. Machines, Computations, and Universality (MCU), volume 4664 of LNCS, pp. 242-254, Orleans, France, September 2007. Springer.
[6] Yurii Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215-240, November 1996.
[7] Shigeru Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the ACM, 8(4):476-483, October 1961.
[8] Shigeru Watanabe. 4-symbol 5-state universal Turing machines. Journal of Information Processing Society of Japan, 13(9):588-592, 1972.
That is why many serious authors as Vaughn Pratt can be confused. Because they are not updated on the subtles of the field. We are glad that this is making a contribution to the discussion on universality. We expect that others will further clarify what Alex Smith has done.
This post is as ridicoulous as many others following this thread. The definition used in the proof has been used in the Small Turing Machine community since many years ago, namely Watanabe, Rogozhin, and many others. It wasn't an invention of Wolfram, Alex Smith or the reviewers but a contribution of Alex Smith to the debate of universality since he is not using periodic backgrounds but non-periodic simple ones.
Furthermore, it is much more likely to find tape backgrounds with some pattern than "blank" tapes... And if you prove that the background is computationally simple so you don't need another universal machine then it fulfills the basic requirements of universality. Don't confuse yourselves with "infinite initial conditions" just because there is an infinite pattern on the tape. It is exactly the same than the "infinite tape filled with blanks". You don't need an infinite number of molecules to build this machine, you just need 6 elements (2 states x 3 colors) and you will find that your machine can behave universal because it is not going to find blank tapes around but many patterns interacting with it.
Don't be fool an inform yourself or think a little bit.
Wolfram exploited this student? This student was free to submit his proof and won 25 K! I would like to be exploited like that...
You are wrong, taking the word of a guy as a peer review of a proof, and then come here and talk as if everybody knew about the topic. You are sharks feeding yourselves. That is the obscenity.
You talk about "the standards of the academic world". Do you mean that world that produces thousands of papers that nobody reads except the referee? Do you think all papers and proofs are flawless?
Wolfram Research is a company that want things to get done, well and fast. It is not a university and you don't have to expect them to behave as if they were. They don't want to be either. It is their prize and their money.
Before taking the word of someone sending an email with his personal opinions in the FOM list, go an inform yourself. At least wait for the right to answer before spreading your ignorance worldwide.
Here is the explanation about the suposed "flaw", which of course it is not:
http://forum.wolframscience.com/showthread.php?s=&threadid=1472
And my comments on the guy that thinks that the universality definition was changed for the prize benefit (I am surprised about how many people write about this without knowing a bit of the subject and trying to sound technical talking about "AND gates" completely nonsense):
Concerning the definition of universality, a halting state or halting instruction wasn't a requirement. This is a common usage nowadays in the field of small universal Turing machines, which is a generalization of previous definitions.
If there is no clear definition is because there is no clear-cut, established procedure to determine when an initial condition is computationally simple enough to be acceptable. Some would wish universal computation stick to a finite initial condition with an unbounded tape filled with "blanks", because that's the only case where the theory is entirely clear. However, others accept generalizations such as periodic "blank" words as long as they remain computationally simple enough (possibly generated in the same fashion as an unbounded "blank" tape). So Alex Smith's use of a non-periodic but still sufficiently computationally simple background is a natural generalization of this sort. The key point is that the background can be set up without doing universal computation, so the 2,3 machine itself actually carries out the computation.
We are glad that this is making a contribution to the discussion on universality. We expect that others will further clarify what Alex Smith has done. We particularly hope that his methods can be extended to other similar proofs.
No, Vaughn Pratt is confused. There is a post from on the FOM mailing list that explains the confusion.
There are subtle issues concerning the nature of computational universality in the presence of infinite initial conditions.
Vaughn Pratt is probably remembering work from the 1950s on computational universality, which does not address these issues.
There are different definitions that could be given for computational universality with infinite initial conditions. Alex Smith's proof was
verified with a particular, natural, definition that was chosen for the prize.
So all is well. The 2,3 Turing machine's universality has not been toppled with one email and the personal opinion of Vaughn Pratt.
What has happened, though, is that questions that have not been discussed since the 1950s are (this week) back in vogue again.
Slashdot Mirror
Your example of PDA's would require to have them interacting at every step as was said in the FOM list from where everybody is jumping to wrong conclusions. Smith's proof does not suppose any communication.
From the FOM list where most of you jumped to conclusions without even waiting to an official answer from Wolfram Research: 1. Concerning the prize committee, we did not expect them to go through the details of the proof but to support the reviewers on technical issues related to their fields of expertise. We would have been delighted to have had them spend more time on the proof but that wasn't our expectation. We did talk to people about how to set the prize up. Basically we needed judgement about their areas and we were very careful to cover those that could come up in a universality proof. We are grateful to the committee for covering those areas and we are happy that they were more active than many such committees. In the review process, committee members agreed with the Wolfram Science internal reviewers, while others asked for additional clarifications (such as fulfilling universality basic requirements for non-halting machines). All committee members had Alex Smith's proof in hand for a couple of months. But it was Wolfram staff who did the hard work to achieve a satisfactory level of verification (between revisions and revision requests), and we thought that by waiting any longer we would not have learned more. It helped that a lot of the proof was submitted in the form of programs that could be run and analyzed in a systematic way. Smith's proof is available to everybody, anyone can point out anything, and it is nice to get the sense that there are people out there who would be interested in verifying proofs. This is great news, and if we do other prizes we would definitely like to take advantage of that. We would be also delighted to hear opinions on how to set up next prizes. 2. Concerning the definition of universality, a halting state or halting instruction wasn't a requirement. This is a common usage nowadays in the field of small universal Turing machines (see detailed references below), which is a generalization of previous definitions. If there is no clear definition is because there is no clear-cut, established procedure to determine when an initial condition is computationally simple enough to be acceptable. Some would wish universal computation stick to a finite initial condition with an unbounded tape filled with "blanks", because that's the only case where the theory is entirely clear. However, others accept generalizations such as periodic "blank" words as long as they remain computationally simple enough (possibly generated in the same fashion as an unbounded "blank" tape). So Alex Smith's use of a non-periodic but still sufficiently computationally simple background is a natural generalization of this sort. The key point is that the background can be set up without doing universal computation, so the 2,3 machine itself actually carries out the computation. One could fairly argue that two non-universal coupled automata can reach universality, but it would require the couple to interact at every step, as in Margenstern's nice example [1], but that's very different from a non-universal second automaton intervening only once at the first step. We are glad that this is making a contribution to the discussion on universality. We expect that others will further clarify what Alex Smith has done. We particularly hope that his methods can be extended to other similar proofs. Accepting that you are not experts in the field but pretending to judge something that of course experts reviewed is a good start. It is nice that people like you think on this problem and possible flaws, though. Of course nobody is changing the well stablished definition of a Turing machine. But it is accepted even by the experts that there is no clear definition on universality. You should follow all the FOM posts and not only those that you think are better to criticise others. The definition of universality has been modify several times (if one can say so, since there is no original or first accepted definition), the first to make a generalization exactly as the used by Alex Smith was Watanabe as early as in the 60's. Alex Sm
From the FOM list: 1. Concerning the prize committee, we did not expect them to go through the details of the proof but to support the reviewers on technical issues related to their fields of expertise. We would have been delighted to have had them spend more time on the proof but that wasn't our expectation. We did talk to people about how to set the prize up. Basically we needed judgement about their areas and we were very careful to cover those that could come up in a universality proof. We are grateful to the committee for covering those areas and we are happy that they were more active than many such committees. In the review process, committee members agreed with the Wolfram Science internal reviewers, while others asked for additional clarifications (such as fulfilling universality basic requirements for non-halting machines). All committee members had Alex Smith's proof in hand for a couple of months. But it was Wolfram staff who did the hard work to achieve a satisfactory level of verification (between revisions and revision requests), and we thought that by waiting any longer we would not have learned more. It helped that a lot of the proof was submitted in the form of programs that could be run and analyzed in a systematic way. Smith's proof is available to everybody, anyone can point out anything, and it is nice to get the sense that there are people out there who would be interested in verifying proofs. This is great news, and if we do other prizes we would definitely like to take advantage of that. We would be also delighted to hear opinions on how to set up next prizes. 2. Concerning the definition of universality, a halting state or halting instruction wasn't a requirement. This is a common usage nowadays in the field of small universal Turing machines (see detailed references below), which is a generalization of previous definitions. If there is no clear definition is because there is no clear-cut, established procedure to determine when an initial condition is computationally simple enough to be acceptable. Some would wish universal computation stick to a finite initial condition with an unbounded tape filled with "blanks", because that's the only case where the theory is entirely clear. However, others accept generalizations such as periodic "blank" words as long as they remain computationally simple enough (possibly generated in the same fashion as an unbounded "blank" tape). So Alex Smith's use of a non-periodic but still sufficiently computationally simple background is a natural generalization of this sort. The key point is that the background can be set up without doing universal computation, so the 2,3 machine itself actually carries out the computation. One could fairly argue that two non-universal coupled automata can reach universality, but it would require the couple to interact at every step, as in Margenstern's nice example [1], but that's very different from a non-universal second automaton intervening only once at the first step. People using universality generalizations of this sort: [1] Manfred Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, November 1996. [2] Manfred Kudlek and Yurii Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory (DLT) 2001, vol. 2295 of LNCS, pp. 311-318, Vienna, May 2002. Springer. [3] Maurice Margenstern and Liudmila Pavlotskaya. On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation, 13(2):133-202, April 2003. [4] Claudio Baiocchi. Three small universal Turing machines. In Maurice Margenstern and Yurii Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pp. 1-10, Chisinau Moldavia, May 2001. Springer. [5] Turlough Neary and Damien Woods. Four small universal Turing machines. Machines, Computations, and Universality (MCU), volume 4664 of LNCS, pp. 242-254, Orleans, Fran
Well, that's a good start: you accepting you are not an expert in the field but pretending to judge something that of course experts reviewed. It is nice that people like you think on this problem and possible flaws, though. Of course nobody is changing the well stablished definition of a Turing machine. But it is accepted even by the experts that there is no clear definition on universality. You should follow all the FOM posts and not only those that you think are better to critic others. The definition of universality has been modify several times, the first to make a generalization exactly as the used by Alex Smith was Watanabe as early as in the 60's. Alex Smith contribution is a generalization of the same sort. If you want some references feel free to check these and then reply again: [1] Manfred Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, November 1996. [2] Manfred Kudlek and Yurii Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory (DLT) 2001, vol. 2295 of LNCS, pp. 311-318, Vienna, May 2002. Springer. [3] Maurice Margenstern and Liudmila Pavlotskaya. On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation, 13(2):133-202, April 2003. [4] Claudio Baiocchi. Three small universal Turing machines. In Maurice Margenstern and Yurii Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pp. 1-10, Chisinau Moldavia, May 2001. Springer. [5] Turlough Neary and Damien Woods. Four small universal Turing machines. Machines, Computations, and Universality (MCU), volume 4664 of LNCS, pp. 242-254, Orleans, France, September 2007. Springer. [6] Yurii Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215-240, November 1996. [7] Shigeru Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the ACM, 8(4):476-483, October 1961. [8] Shigeru Watanabe. 4-symbol 5-state universal Turing machines. Journal of Information Processing Society of Japan, 13(9):588-592, 1972. That is why many serious authors as Vaughn Pratt can be confused. Because they are not updated on the subtles of the field. We are glad that this is making a contribution to the discussion on universality. We expect that others will further clarify what Alex Smith has done.
This post is as ridicoulous as many others following this thread. The definition used in the proof has been used in the Small Turing Machine community since many years ago, namely Watanabe, Rogozhin, and many others. It wasn't an invention of Wolfram, Alex Smith or the reviewers but a contribution of Alex Smith to the debate of universality since he is not using periodic backgrounds but non-periodic simple ones. Furthermore, it is much more likely to find tape backgrounds with some pattern than "blank" tapes... And if you prove that the background is computationally simple so you don't need another universal machine then it fulfills the basic requirements of universality. Don't confuse yourselves with "infinite initial conditions" just because there is an infinite pattern on the tape. It is exactly the same than the "infinite tape filled with blanks". You don't need an infinite number of molecules to build this machine, you just need 6 elements (2 states x 3 colors) and you will find that your machine can behave universal because it is not going to find blank tapes around but many patterns interacting with it. Don't be fool an inform yourself or think a little bit.
Wolfram exploited this student? This student was free to submit his proof and won 25 K! I would like to be exploited like that... You are wrong, taking the word of a guy as a peer review of a proof, and then come here and talk as if everybody knew about the topic. You are sharks feeding yourselves. That is the obscenity. You talk about "the standards of the academic world". Do you mean that world that produces thousands of papers that nobody reads except the referee? Do you think all papers and proofs are flawless? Wolfram Research is a company that want things to get done, well and fast. It is not a university and you don't have to expect them to behave as if they were. They don't want to be either. It is their prize and their money. Before taking the word of someone sending an email with his personal opinions in the FOM list, go an inform yourself. At least wait for the right to answer before spreading your ignorance worldwide.
Here is the explanation about the suposed "flaw", which of course it is not: http://forum.wolframscience.com/showthread.php?s=&threadid=1472 And my comments on the guy that thinks that the universality definition was changed for the prize benefit (I am surprised about how many people write about this without knowing a bit of the subject and trying to sound technical talking about "AND gates" completely nonsense): Concerning the definition of universality, a halting state or halting instruction wasn't a requirement. This is a common usage nowadays in the field of small universal Turing machines, which is a generalization of previous definitions. If there is no clear definition is because there is no clear-cut, established procedure to determine when an initial condition is computationally simple enough to be acceptable. Some would wish universal computation stick to a finite initial condition with an unbounded tape filled with "blanks", because that's the only case where the theory is entirely clear. However, others accept generalizations such as periodic "blank" words as long as they remain computationally simple enough (possibly generated in the same fashion as an unbounded "blank" tape). So Alex Smith's use of a non-periodic but still sufficiently computationally simple background is a natural generalization of this sort. The key point is that the background can be set up without doing universal computation, so the 2,3 machine itself actually carries out the computation. We are glad that this is making a contribution to the discussion on universality. We expect that others will further clarify what Alex Smith has done. We particularly hope that his methods can be extended to other similar proofs.
No, Vaughn Pratt is confused. There is a post from on the FOM mailing list that explains the confusion. There are subtle issues concerning the nature of computational universality in the presence of infinite initial conditions. Vaughn Pratt is probably remembering work from the 1950s on computational universality, which does not address these issues. There are different definitions that could be given for computational universality with infinite initial conditions. Alex Smith's proof was verified with a particular, natural, definition that was chosen for the prize. So all is well. The 2,3 Turing machine's universality has not been toppled with one email and the personal opinion of Vaughn Pratt. What has happened, though, is that questions that have not been discussed since the 1950s are (this week) back in vogue again.