Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Sunday, 8 May 2022 at 12:35:00 UTC+1, richar...@gmail.com wrote:
>> On 5/7/22 9:57 PM, Jeff Barnett wrote:
>> > On 5/7/2022 4:21 PM, Ben wrote:

>> >> Here's an interesting test case that's useful for timing and so on:
>> >>
>> >> A_1RB
>> >> A11LC
>> >> B_1RC
>> >> B11RB
>> >> C_1RD
>> >> C1_LE
>> >> D_1LA
>> >> D11LD
>> >> E_1RH
>> >> E1_LA
>> >>
>> >> You will need to add a '(' for DSW compatibility. Also, note that my
>> >> interpreter uses _ as the tape's blank symbol. Change all _s to an
>> >> actual spaces if that's what you use.
>> >>
>> >> This is (as far as I know) the current BB(5) champion. It runs for more
>> >> that 47 million steps before halting.
>> >
>> > Questions:
>> >
>> > Was 47 million steps a measured or a theoretically computed measure?
>> >
>> > How long would you estimate that a well-written TM interpreter on modern
>> > hardware needs to interpret the above? A few seconds or minutes?
>> A well written TM interpreter on modern hardware should be able to do
>> many millions of steps a second (as I posted a main loop that can do
>> that), so we are in seconds.
>>
>> IF we need to generate a trace that can be inspected by a human, we
>> likely get I/O bound generating that trace, and it may go to order of
>> minutes to maybe hours
>>
> Whilst you might write a pure implementation of a Turing machine as a
> first step, you're unlikely to use it much. People want to see the machine
> buzz and whir away, as it performs its magic.
> So that means some sort of graphical interface. Which is orders of
> magnitude slower than a simple virtual machine.

You don't really need much. A simple print of the tape (centred on the
head) give the feel for what's happening. Throw in a \r and a delay and
will look like an animation even in a plain tty.

With tracing turned on, my simple implementation shows this for the
BB(4) champion:

$ ./simple-tm bb-4-2 ""
A B C D H
1 1LB _LC 1LD _RA
_ 1RB 1LA 1RH 1RD
________________________________[A|_]_________________________________
________________________________[B|_]_________________________________
________________________________[A|_]_________________________________
_______________________________1[B|_]_________________________________
________________________________[A|1]1________________________________
________________________________[B|_]11_______________________________
________________________________[A|_]111______________________________
_______________________________1[B|1]11_______________________________
________________________________[C|1]_11______________________________
________________________________[D|_]1_11_____________________________
_______________________________1[D|1]_11______________________________
______________________________1_[A|_]11_______________________________
_____________________________1_1[B|1]1________________________________
______________________________1_[C|1]_1_______________________________
_______________________________1[D|_]1_1______________________________
______________________________11[D|1]_1_______________________________
_____________________________11_[A|_]1________________________________
____________________________11_1[B|1]_________________________________
_____________________________11_[C|1]_________________________________
______________________________11[D|_]1________________________________
_____________________________111[D|1]_________________________________
____________________________111_[A|_]_________________________________
___________________________111_1[B|_]_________________________________
____________________________111_[A|1]1________________________________
_____________________________111[B|_]11_______________________________
______________________________11[A|1]111______________________________
_______________________________1[B|1]1111_____________________________
________________________________[C|1]_1111____________________________
________________________________[D|_]1_1111___________________________
_______________________________1[D|1]_1111____________________________
______________________________1_[A|_]1111_____________________________
_____________________________1_1[B|1]111______________________________
______________________________1_[C|1]_111_____________________________
_______________________________1[D|_]1_111____________________________
______________________________11[D|1]_111_____________________________
_____________________________11_[A|_]111______________________________
____________________________11_1[B|1]11_______________________________
_____________________________11_[C|1]_11______________________________
______________________________11[D|_]1_11_____________________________
_____________________________111[D|1]_11______________________________
____________________________111_[A|_]11_______________________________
___________________________111_1[B|1]1________________________________
____________________________111_[C|1]_1_______________________________
_____________________________111[D|_]1_1______________________________
____________________________1111[D|1]_1_______________________________
___________________________1111_[A|_]1________________________________
__________________________1111_1[B|1]_________________________________
___________________________1111_[C|1]_________________________________
____________________________1111[D|_]1________________________________
___________________________11111[D|1]_________________________________
__________________________11111_[A|_]_________________________________
_________________________11111_1[B|_]_________________________________
__________________________11111_[A|1]1________________________________
___________________________11111[B|_]11_______________________________
____________________________1111[A|1]111______________________________
_____________________________111[B|1]1111_____________________________
______________________________11[C|1]_1111____________________________
_______________________________1[D|1]1_1111___________________________
______________________________1_[A|1]_1111____________________________
_______________________________1[B|_]1_1111___________________________
________________________________[A|1]11_1111__________________________
________________________________[B|_]111_1111_________________________
________________________________[A|_]1111_1111________________________
_______________________________1[B|1]111_1111_________________________
________________________________[C|1]_111_1111________________________
________________________________[D|_]1_111_1111_______________________
_______________________________1[D|1]_111_1111________________________
______________________________1_[A|_]111_1111_________________________
_____________________________1_1[B|1]11_1111__________________________
______________________________1_[C|1]_11_1111_________________________
_______________________________1[D|_]1_11_1111________________________
______________________________11[D|1]_11_1111_________________________
_____________________________11_[A|_]11_1111__________________________
____________________________11_1[B|1]1_1111___________________________
_____________________________11_[C|1]_1_1111__________________________
______________________________11[D|_]1_1_1111_________________________
_____________________________111[D|1]_1_1111__________________________
____________________________111_[A|_]1_1111___________________________
___________________________111_1[B|1]_1111____________________________
____________________________111_[C|1]__1111___________________________
_____________________________111[D|_]1__1111__________________________
____________________________1111[D|1]__1111___________________________
___________________________1111_[A|_]_1111____________________________
__________________________1111_1[B|_]1111_____________________________
___________________________1111_[A|1]11111____________________________
____________________________1111[B|_]111111___________________________
_____________________________111[A|1]1111111__________________________
______________________________11[B|1]11111111_________________________
_______________________________1[C|1]_11111111________________________
________________________________[D|1]1_11111111_______________________
________________________________[A|1]_11111111________________________
________________________________[B|_]1_11111111_______________________
________________________________[A|_]11_11111111______________________
_______________________________1[B|1]1_11111111_______________________
________________________________[C|1]_1_11111111______________________
________________________________[D|_]1_1_11111111_____________________
_______________________________1[D|1]_1_11111111______________________
______________________________1_[A|_]1_11111111_______________________
_____________________________1_1[B|1]_11111111________________________
______________________________1_[C|1]__11111111_______________________
_______________________________1[D|_]1__11111111______________________
______________________________11[D|1]__11111111_______________________
_____________________________11_[A|_]_11111111________________________
____________________________11_1[B|_]11111111_________________________
_____________________________11_[A|1]111111111________________________
______________________________11[B|_]1111111111_______________________
_______________________________1[A|1]11111111111______________________
________________________________[B|1]111111111111_____________________
________________________________[C|_]_111111111111____________________
_______________________________1[H|_]111111111111_____________________
steps=109

--
Ben.