Talk:ORK

Computational Class

I don't know kipple, so I don't know if the kipple interpreter proves TC, but the brainfuck interpreter certainly doesn't, as it has a hard-coded tape-length.

A read of the spec leaves enough unanswered questions that one has to look at the reference implementation. It appears that all numbers are doubles and that all arrays are limited to double length. Nonetheless, it seems that there are two means of unbounded storage:

• The subroutine call stack could be used as a LIFO stack (I think C++ will recurse until it runs out of memory)
• strings provide random-access data of unbounded size (I think C++ will create strings of any desired length until it runs out of memory)

Of course, any C++ implementation that actually provides an unbounded call stack and unbounded strings (e.g. a C++ compiler/executer on an ideal turing machine) could also implement double as unbounded rationals. Still, the double limit is a very immediate limit in practical terms, since one cannot reasonably store a moderately long data list in a double, but one can store it in an array of numbers.

One last note... It is not immediately obvious that strings provide random access data in ORK since ORK's string operators are limited to concatenate and compare. My argument that they do is as follows:

1. If one can split a string into its first and remaining characters one has random access to that string
2. An ORK subroutine can be constructed that compares the unknown string to all possible length 1 strings, all possible length 2 strings, and so on...
3. The ORK subroutine can keep track of the comparison string as a first character plus a string of remaining characters and thus have the split when it finds a match

--Nthern 16:31, 21 July 2011 (UTC)

DOH! I haven't looked at ORK in quite a while, but when I was just re-reading its docs I noticed self-referential objects. I can't see any reason that an unbounded linked list could not be created and processed. It looks like ORK is definitely TC without the need to fall back on dubious and/or difficult schemes. --Nthern (talk) 19:41, 17 September 2013 (UTC)