tag:blogger.com,1999:blog-3722233.post117277460020176082..comments2023-03-20T21:49:52.361-05:00Comments on Computational Complexity: Inductive Turing MachinesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-85124269601642038142008-05-15T21:49:00.000-05:002008-05-15T21:49:00.000-05:00Dear Lance,Ignorance has never been the best featu...Dear Lance,<BR/>Ignorance has never been the best feature of a person. That's why I decided to explain the situation with inductive Turing machines to you and to those who visit your weblog and might be interested to have correct knowledge. If you, or somebody else, read publications on machine learning, you will see that this community has never used the term "inductive Turing machine". What they use is "inductive inference machine". It is a different kind of automata. Thus, your attempt to define inductive Turing machines is based on a wrong assumption. Moreover, what you defined is neither inductive Turing machine nor inductive inference machine.<BR/>However, your intuition that inductive Turing machines and inductive inference machines are related in some way was correct. Indeed, inductive inference machines are equivalent to the simplest kind of inductive Turing machines, which are at lowest level of the hierarchy of all inductive Turing machines. This is demonstrated in the book "Super-recursive algorithms".<BR/>As I don't expect that you, or somebody else of those who are writing to this weblog, is ever going to read this book or any mathematical paper where inductive Turing machines are rigorously defined and studied, I give here a simplified description of an inductive Turing machine. <BR/>The simplest inductive Turing machine M has the same structure as a Turing machine with three tapes and three heads. In the machine M, one tape is the read-only input tape, the second tape is the write-only output tape, and the third tape is the working tape of M. The machine M performs operations as a Turing machine. The only difference is in how M gets its results. Naturally, when M stops in a final state, then the word written in the output tape is the final result of M. This is the same as what a Turing machine is doing. That is why inductive Turing machines can simulate any Turing machine. <BR/>However, M can also obtain a result in a different way. Namely, when at some step of computation, the word written in the output tape stops changing, then this word is also the final result of the simplest inductive Turing machine M.<BR/>In spite of some incompetent comments, inductive Turing machines have much higher computing power than inductive inference machine and limit partial recursive functions.<BR/>More powerful inductive Turing machines have a more efficient memory, more powerful control device or/and processor (head). In the similar way to computers, these components add power to inductive Turing machines.<BR/>For those who read article for a general audience and then complain that they don't find rigor there, I would like to note (although it is evident) that this is not an exact definition. To find an exact definition, it is necessary to read the book "Super-recursive algorithms" or mathematical papers where inductive Turing machines are rigorously defined and studied.<BR/>To understand why and how you invented your definition of inductive Turing machine, it is not necessary to be either Sherlock Holmes or even Sherlock Pratt. The first cause for giving that definition was your good mathematical education: you studied calculus and you know the concept of limit. Thus, it is possible to assume that a professional at your level of expertise can understand definitions of inductive Turing machines and inductive inference machines … he reads these definitions. Consequently, it possible to conclude that you did not read either of these definitions. Unfortunately, society looses the culture of reading. It was the second cause for giving that definition. The third cause was a confusing choice of the name for the term "limit recursive function" introduced by such a prominent and influential computer mathematician as Gold and persistently used in the area of inductive inference. Looking at the definition of a limit recursive function or limit partial recursive function, it is possible to have an impression that their result is obtained as a limit of an infinite process.<BR/>However, this is not so with respect to the limits used in the calculus. In addition to other advantages, the construction of the simplest inductive Turing machine made it evident that this machine, as well as any limit recursive function or inductive inference machine, always gives its result (if any) after a finite number of steps. Unfortunately, the name "limit recursive function" implies connections to the concept of limit in calculus and these connections are wrong.<BR/>To conclude, it is possible to remark that the definition you gave is meaningful although it is not rigorous. One of possible rigorous definitions of such a construction is the definition of a simple limit Turing machine. There are also other topological algorithms based on the concept of limit.<BR/><BR/>Mark Burgin<BR/><BR/>P.S. It is much easier to discuss a TV show than to read a mathematical paper (not speaking about a book) and at least, to understand the main constructions (not speaking about results).Mark Burginhttps://www.blogger.com/profile/03441578906730742120noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73174513122719302612008-03-12T19:42:00.000-05:002008-03-12T19:42:00.000-05:00Sorry, replace "wrong" by "right" in the above. (...Sorry, replace "wrong" by "right" in the above. (Burgin's inductive Turing machines, which apparently he came up with on his own and later realized were already known, are related to Gold's notion of identification in the limit (JSL 1965, I&C 1967) and to omega-automata. What Janos said.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47158174992623120492008-03-12T19:29:00.000-05:002008-03-12T19:29:00.000-05:00What would Sherlock Holmes do here? He'd reason t...What would Sherlock Holmes do here? He'd reason that the writers are in LA so they'd go to the UCLA math department, ask the resident expert on Turing machines, Mark Burgin, for some authentic background terminology, and he helps them out with<BR/><BR/>M. Burgin, Inductive Turing machines, Notices Acad. Sci. USSR 270 (1983) 1289–1293 (translated<BR/>from Russian, v.27, No. 3).<BR/><BR/>How Holmes ever got his man with his cockamamie guesses was always beyond me. I'm sure this guess is wrong.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1172854670059903052007-03-02T10:57:00.000-06:002007-03-02T10:57:00.000-06:00You might as well ask what the mathematical signif...You might as well ask what the mathematical significance of 4, 8, 15, 16, 23 and 42 are.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1172846902956974742007-03-02T08:48:00.000-06:002007-03-02T08:48:00.000-06:00So let's play Lance's game -- the (Numbers)^-1 gam...So let's play Lance's game -- the (Numbers)^-1 game of taking out science from (Numbers), while presumably Numbers tries to put science into entertainment.<BR/><BR/>The question they were posing in the episode is<BR/><BR/>given a sample of a maze, can you learn it?<BR/><BR/>Of course the next question is "what do you mean by "learn"?"<BR/><BR/>A possible formalization is<BR/><BR/>In an unknown maze [of size at most n rooms] [, planar] [, bounded degree d] a master criminal follows a trajectory T [with some possible restrictions--max velocity, constant velocity, constant acceleration]<BR/>[Moreover the maze is a submaze of a known maze of size N]<BR/><BR/>(Items enclosed in square brackets are possible additional assumptions)<BR/><BR/>The criminal is observed at times 1, 2, ... i. The task is to predict its location at time i+1.<BR/><BR/>[in a way that as i grows the predictions become more accurate]<BR/><BR/>Give bounds on the number of observations needed, the accuracy of the prediction, and the time needed for your algorithm, for each possible case.<BR/><BR/>You only need to solve the cases where the solution is interesting.Janos Simonhttps://www.blogger.com/profile/15677985672817404601noreply@blogger.com