Stitie Machine can do everything that Turing Machine can, and more. It just seems more expensive to implement. But sometimes more complex operation is more efficient. Like using power function can be cheaper and quicker than adding recurrentially.

Turing Machine - created by Alan Turing abstract model of computer used to run algorithms, consisting of infinitely long 2D space divided into fields. This space can be one-sidedly infinite or two-sidedly infinite. Each field may be in one of N states. Machine always is posed over one of fields and is in one of M states. Depending on combination of machine's state and field's state machine saves new value in field, changes state, then it can move by one field to right or left. This operation is called command. Turing Machine is controlled by list consisting of any number of commands. Numbers N and M may be any, just finite. Sometimes state M+1 may be allowed, which allows end of machine's work. Command list for Turing Machine may be treated as her program.

Hint: Finite State Object can be designed to support Machine's position and state. Or one additional Finite State Objects can represent Machine, and know routes to all fields (which are Finite State Objects too). It may keep references to all fields (for example in map, with key being unambiguous route definition, value being reference to field). Or may not (in this case it just holds reference to one field, and all routes go through this field).

Stitie Turing Machine can be serialized to binary number. Then we can build finite state automaton and optimize it to reduce number of transitions. How to reverse this change? Stitie Machine post explains how to arrange FSOs into Stitie Machine.

ReplyDeleteIf we can generate finite state automaton from Stitie Turing Machine then it will work on any computer as far as i know.

How to map Stitie Machine into above defined 2D Turing Machine?

ReplyDeleteFor example:

Define 'left' and 'right' in 3D, and combine states of machines at each of sides into larger, but simpler machines.