Talk:MISC Turing-completeness proof

MISC is not Turing-complete

MISC memory capacity is fixed at one arbitrarily large finite size; consequently, MISC is not Turing-complete (TC). Thus, a MISC program cannot interpret a TC version of brainfuck — at best it could interpret a non-TC version, such as one with an appropriately fixed finite-size memory. (Note that in TC versions of brainfuck, memory capacity can be considered finite but unbounded, but it cannot be considered fixed at one arbitrarily large finite size.) --r.e.s. (Talk) 00:40, 20 Aug 2005 (GMT)

What if the program was extended to the MISC-infinity? It's behaviour would still be well-defined, as long as each memory cell was initialised to a finite value (that is, only a finite number of bits are non-zero). Then that would be Turing-complete, right?--Safalra 09:57, 20 Aug 2005 (GMT)

Thinking about the MISC-infinity a bit more, I think it would work, but there are some technical issues in defining it, as the 'top two bits' is a strange concept when the memory cells consist of an infinite number of bits. I guess we could consider every fourth memory cell to consist of a pair of bits followed by an infinite number of bits, but there are some conditions here - when a memory cell is read (treated as a number, not part of instruction), the pair of bits must either both equal 0 (if the number is positive) or both equal 1 (if the number is negative). It is obviously then impossible to tell in general whether a starting configuration of the MISC-infinity is valid, as it's uncomputable in general whether, in a given program, one of these cells would ever be treated as a number rather than part of an instruction.--Safalra 12:33, 20 Aug 2005 (GMT)

It seems likely that with some finite number of words, MISC-infinity (meaning MISC changed to have infinite word-size) could be made TC, say by changing to unary representation after two reserved bits:

addr A :  -- 1A 0...
num X  :  -s 1X 0...
W3 word:  ab 1J 0...

In other words, when a word is read as an address, the first two bits are skipped and the (relative) address-value is the number of ones before the next 0. When a word is read (or written) as a number, the first bit is skipped, the sign bit is the second bit, and the numerical-value is the number of 1's before the next 0. When a W3 word is read, the first two bits flag the operand modes, and the jump-value is the number of 1's before the next 0. I think this will ensure that every possible configuration is valid, with every possible binary string allowed in every word. --r.e.s. (Talk) 22:08, 20 Aug 2005 (GMT)

Simulating a Turing machine directly

Jump addresses in MISC are relative to the instruction location, so the limit on memory size is unnecessary - a 16-bit MISC machine can have an infinite amount of memory, but it will have to move around it slowly. This means MISC can directly simulate a Turing machine, by copying the state transition data around memory as it moves to the left or right on the tape. This avoids the need for complex definition of a 'MISC-infinity'. --Safalra 17:29, 8 Dec 2005 (GMT)