Noback Machine

This article is not detailed enough and needs to be expanded. Please help us by adding some more information.

Noback Machine is a variation of Turing machine by User:ChuckEsoteric08.

Description

Noback Machine is different from Turing-machine that there is no way to move left, instead it can only move pointer right or move pointer to the start of a tape. Tape in Noback Machine is also right-infinite because of that. Each state is represented as a 4-tuple:

(State, Initial symbol, Next symbol, Command, Next State)

Command can be either "Move right" (R) or "Move to the first cell" (F)

Often the name "Reset Turing machine" is used for similar variations of Turing machines but "Noback machine" is used for the one with this exact syntax

Computational class

Noback machine is Turing complete as it can simulate the Tag system in a similar way as brainfuck minus -.

Universal Noback machines

So far there has been a single Umiversal Noback Machine (UNM)

8-state, 10-symbol

It uses 10 characters to simulate Cyclic tag system, which are here represented like that:

• _ is blank character used for cells that weren't initialized, blank symbol is also used to replace deleted elements from the queue
• 0 and 1 are used to represent data queue of CT
• Productions are formed like that:
  • 0 is represented as d and 1 as e, productions end with f
  • During execution they are occasionally replaced by a, b and c respectively to keep track of instruction pointer
• g represents end of data queue

Thus each Cyclic tag program is encoded like that (note that while productions are dencoded, initial data queue remains the same):

productiondatag

So example program from the page becomes:

deefedfedef1g

Exact state transitions can be seen in the spreadsheet created by the author, which marks unused state and symbol combinations as red cells but general idea is:

• 1 is used to mark current command and branch, if it is data then go back to the start and if blank transitions to atate 8
• 2 and 3 for checking if front of queue is 1, and then if so they transition to states 4 and 5 to append 0 and 1 respectively and then both go to state 6
• 6 finds a currently executed command, unmarks it and moves to the next cell and transitions to state 1
• 7 blanks first data character it comes across and then turns to state 6
• 8 checks blank cells which signify deleted data, if they find non deleted bits then it will turn into state 1, if it come across end of data halt is simulated

That is likely isn't most optimal way to do it and instead of expected 8x10 = 80 transitions there is only 46 (only 57,5%) due to large gaps which mean that some optimizations are possible, and if we dont count ones which lead to halt and instead classify them as illegal that make program halt if appear that number is lowered to just 40