> proposed). For example, it is possible to implement a turing machine in > j, by representing only the finitely many cells which have been visited so > far. As the number of steps simulated increases without bound, so too may
Right, that is how the version Universal Turing machine - Rosetta Code <https://rosettacode.org/wiki/Universal_Turing_machine#The_structured_derivation_of_the_universal_Turing_machine> is implemented. By the way, I am somewhat familiar with a related implementation of rule 110, (0 1 1 1 0 1 1 0 {~ #.)\~&3@(0 0 , ] , 0:)^:_ which expands its input/output as necessary. For example, (3 (0 1 1 1 0 1 1 0 {~ #.)\ 0 0 , ] , 0:)^:(<11) 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1 1 0 1 However, I could not figure out how to use your version to reproduce the usual example. Can you show us how to do it? Regarding the Turing completeness of a parentheses free J, the best I can do so far is to reduce it to a single pair of parentheses, Fractan=. ([ {~ 1 i.~ [ = <.)@:* ::]^:_ Perhaps, you or another member can somehow get rid of them (the above line also shows concisely that tacit J is, in principle, Turing complete). At any rate, unlike the Turing machine emulator, the Fractan implementation does not give me any practical insight on how one can produce, in principle, tacit verbs which can accomplish any (Turing) computable tasks. On Tue, Feb 8, 2022 at 4:41 PM Elijah Stone <elro...@elronnd.net> wrote: > > It is meaningful, because j supports arrays of unbounded length, and it > does not support arrays of infinite length (though that has been > proposed). For example, it is possible to implement a turing machine in > j, by representing only the finitely many cells which have been visited so > far. As the number of steps simulated increases without bound, so too may > the memory requirements; but so long as the former is finite, the latter > must be, too. And there is no expectation that you will be able to > simulate infinite steps of a turing machine in finite real time. > > (In this respect, extant implementations of j are not and can not be > turing-complete, but that is irrelevant.) > > -E > > On Tue, 8 Feb 2022, Raul Miller wrote: > > > If we are talking about equivalence to a turing machine -- > > https://en.wikipedia.org/wiki/Turing_machine -- I do not think this is > > a meaningful distinction. > > > > Thanks, > > > > -- > > Raul > > > > On Tue, Feb 8, 2022 at 3:51 PM Elijah Stone <elro...@elronnd.net> wrote: > >> > >> That is not quite right. We do not need to explicitly represent infinite > >> arrays; we only need array length to be unbounded, such that the length of > >> a given array can grow without bound (but finitely) over a finite amount > >> of time. See limit definition. > >> > >> -E > >> > >> On Tue, 8 Feb 2022, Raul Miller wrote: > >> > >> > On Tue, Feb 8, 2022 at 4:30 AM Elijah Stone <elro...@elronnd.net> wrote: > >> >> Can anyone come up with something which does not require infinite arrays? > >> > > >> > Technically, any system which does not support infinite time and > >> > infinite space is not turing complete. > >> > > >> > That said, in most contexts, we take "infinite" to mean "larger than I > >> > need for the example(s) I am concerned about". > >> > > >> > FYI, > >> > > >> > -- > >> > Raul > >> > ---------------------------------------------------------------------- > >> > For information about J forums see http://www.jsoftware.com/forums.htm > >> ---------------------------------------------------------------------- > >> For information about J forums see http://www.jsoftware.com/forums.htm > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
