Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #49891 > unrolled thread
| Started by | olcott <polcott2@gmail.com> |
|---|---|
| First post | 2022-05-06 15:53 -0500 |
| Last post | 2022-05-09 10:35 -0500 |
| Articles | 20 on this page of 194 — 10 participants |
Back to article view | Back to comp.theory
Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 15:53 -0500
Re: Validating that the implementation meets the spec for TM transition function Mr Flibble <flibble@reddwarf.jmc> - 2022-05-06 22:08 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 16:25 -0500
Re: Validating that the implementation meets the spec for TM transition function Mr Flibble <flibble@reddwarf.jmc> - 2022-05-06 22:29 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 17:08 -0500
Re: Validating that the implementation meets the spec for TM transition function Mr Flibble <flibble@reddwarf.jmc> - 2022-05-07 13:02 +0100
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-06 14:41 -0700
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 17:02 -0500
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-06 15:36 -0700
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 17:54 -0500
Re: Validating that the implementation meets the spec for TM transition function Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-07 00:39 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 18:54 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 01:54 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 20:05 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 23:21 +0100
Re: Validating that the implementation meets the spec for TM transition function Jeff Barnett <jbb@notatt.com> - 2022-05-07 19:57 -0600
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-08 07:34 -0400
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-08 05:11 -0700
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-08 14:20 -0400
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-08 19:59 +0100
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-09 03:14 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-08 22:39 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-09 12:36 +0100
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-08 14:44 +0100
Re: Validating that the implementation meets the spec for TM transition function Jeff Barnett <jbb@notatt.com> - 2022-05-08 11:08 -0600
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-08 19:27 +0100
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-08 15:22 -0400
Re: Validating that the implementation meets the spec for TM transition function Mr Flibble <flibble@reddwarf.jmc> - 2022-05-08 20:30 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 10:53 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-09 23:08 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 17:32 -0500
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-09 20:31 -0400
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-10 01:37 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 20:29 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-10 11:35 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape] olcott <NoOne@NoWhere.com> - 2022-05-10 19:12 -0500
Re: Validating that the implementation meets the spec for TM transition function Jeff Barnett <jbb@notatt.com> - 2022-05-08 14:51 -0600
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 10:18 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-09 23:14 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 17:42 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-10 01:13 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 20:28 -0500
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-09 23:34 -0400
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-10 00:24 -0700
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-10 11:31 +0100
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-10 03:46 -0700
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-10 12:23 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-10 06:53 -0500
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-10 08:01 -0400
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-10 16:41 +0100
Re: Validating that the implementation meets the spec for TM transition function Jeff Barnett <jbb@notatt.com> - 2022-05-10 11:56 -0600
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-10 19:43 -0500
Re: Validating that the implementation meets the spec for TM transition function Jeff Barnett <jbb@notatt.com> - 2022-05-10 20:49 -0600
Re: Validating that the implementation meets the spec for TM transition function Mr Flibble <flibble@reddwarf.jmc> - 2022-05-10 19:01 +0100
Re: Validating that the implementation meets the spec for TM transition function "dklei...@gmail.com" <dkleinecke@gmail.com> - 2022-05-10 11:59 -0700
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-10 19:04 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-11 01:42 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-10 20:12 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-11 03:05 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-10 21:14 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-11 02:19 -0700
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 08:54 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-11 16:27 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 10:36 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-11 16:49 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-11 14:30 -0700
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 16:38 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-12 00:01 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 19:05 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-12 04:03 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 22:29 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 22:37 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 15:02 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-12 19:03 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 19:30 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 14:23 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-12 19:19 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-13 01:02 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Jeff Barnett <jbb@notatt.com> - 2022-05-11 23:13 -0600
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 00:43 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-11 04:02 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-10 22:07 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-11 13:40 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 09:02 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-11 16:09 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 10:29 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-11 20:35 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 15:12 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-11 22:54 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 17:02 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 02:00 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 20:37 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 02:49 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 21:49 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 14:45 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 10:31 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 21:20 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 15:33 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mr Flibble <flibble@reddwarf.jmc> - 2022-05-12 21:36 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 16:28 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mr Flibble <flibble@reddwarf.jmc> - 2022-05-12 22:33 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 22:02 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 16:14 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 00:18 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 18:22 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 01:10 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 19:58 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 02:54 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-12 22:09 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 21:41 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mikko <mikko.levanto@iki.fi> - 2022-05-13 10:01 +0300
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 10:57 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mikko <mikko.levanto@iki.fi> - 2022-05-13 19:06 +0300
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 11:54 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 13:38 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 11:07 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 17:14 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 12:03 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 18:09 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 12:15 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 17:26 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 12:07 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 19:45 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 13:57 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 15:04 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 14:15 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 15:40 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 14:58 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 16:24 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 15:33 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 17:25 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 16:48 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 18:05 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 20:12 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 14:28 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 21:58 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 16:12 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 23:57 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 17:59 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-14 01:00 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 19:09 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-14 01:21 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-17 13:17 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-14 01:54 -0700
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-14 04:13 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-14 03:30 -0700
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-14 08:51 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-14 11:38 -0700
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-14 13:54 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-14 13:15 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-14 11:37 -0700
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-14 19:47 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-14 20:15 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-14 12:52 -0700
Re: Validating that the implementation meets the spec for TM transition function [ unlimited scalability ] olcott <NoOne@NoWhere.com> - 2022-05-13 16:43 -0500
Re: Validating that the implementation meets the spec for TM transition function [ unlimited scalability ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 23:58 +0100
Re: Validating that the implementation meets the spec for TM transition function [ unlimited scalability ] olcott <NoOne@NoWhere.com> - 2022-05-13 18:03 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Jeff Barnett <jbb@notatt.com> - 2022-05-13 15:06 -0600
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 16:16 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Jeff Barnett <jbb@notatt.com> - 2022-05-13 17:48 -0600
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 19:06 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Jeff Barnett <jbb@notatt.com> - 2022-05-13 19:58 -0600
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 22:39 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Jeff Barnett <jbb@notatt.com> - 2022-05-13 19:48 -0600
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 11:00 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 12:08 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 17:27 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 12:10 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 13:20 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-11 22:07 -0400
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-10 21:06 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-11 00:11 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-10 19:41 -0500
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-10 06:53 -0500
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-07 21:04 -0500
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-08 07:30 -0400
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-08 14:46 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 10:19 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 01:22 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 19:38 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 02:01 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 20:22 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 23:30 +0100
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 02:04 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 20:26 -0500
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-07 05:00 -0700
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 23:31 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-07 18:36 -0500
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-08 02:39 -0700
Re: Validating that the implementation meets the spec for TM transition function [ priorities ] olcott <NoOne@NoWhere.com> - 2022-05-08 17:21 -0500
Re: Validating that the implementation meets the spec for TM transition function Mikko <mikko.levanto@iki.fi> - 2022-05-07 11:06 +0300
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-07 11:14 -0500
Re: Validating that the implementation meets the spec for TM transition function Mikko <mikko.levanto@iki.fi> - 2022-05-08 11:57 +0300
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 10:35 -0500
Page 2 of 10 — ← Prev page 1 [2] 3 4 … 10 Next page →
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-09 03:14 +0100 |
| Message-ID | <87ee13sb9g.fsf@bsb.me.uk> |
| In reply to | #50036 |
Ben <ben.usenet@bsb.me.uk> writes: > 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|_]_________________________________ There was a bug (now fixed) so that when the initial tape is empty there would be a couple of false transitions. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-08 22:39 -0500 |
| Message-ID | <ePKdnciMLI1qEeX_nZ2dnUU7_8zNnZ2d@giganews.com> |
| In reply to | #50059 |
On 5/8/2022 9:14 PM, Ben wrote: > Ben <ben.usenet@bsb.me.uk> writes: > >> 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|_]_________________________________ > > There was a bug (now fixed) so that when the initial tape is empty there > would be a couple of false transitions. > Mine is almost working. I got David S. Woodruff's TM.exe to show me the trace that I am supposed to get on his paren.tm program. My TM.cpp does the first four steps of this correctly. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-09 12:36 +0100 |
| Message-ID | <878rrbrl83.fsf@bsb.me.uk> |
| In reply to | #50063 |
olcott <NoOne@NoWhere.com> writes:
> On 5/8/2022 9:14 PM, Ben wrote:
>> Ben <ben.usenet@bsb.me.uk> writes:
>>
>>> 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|_]_________________________________
>> There was a bug (now fixed) so that when the initial tape is empty there
>> would be a couple of false transitions.
>
> Mine is almost working.
> I got David S. Woodruff's TM.exe to show me the trace
> that I am supposed to get on his paren.tm program.
If you want, I can provide traces for testing. My interpreter takes a
trace format argument so there's a reasonable chance I can make traces
similar to yours.
> My TM.cpp does the first four steps of this correctly.
A reasonable test would be if you get the same number of steps for BB(4)
and BB(5). BB(4) is (as above)
A B C D H
1 1LB _LC 1LD _RA
_ 1RB 1LA 1RH 1RD
and BB(5) is
A B C D E H
1 1LC 1RB _LE 1LD _LA
_ 1RB 1RC 1RD 1LA 1RH
BB(4) halts after 107 steps. B(5) halts after 47176870 steps.
Obviously the output could also be compared.
--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-08 14:44 +0100 |
| Message-ID | <878rrcuoj6.fsf@bsb.me.uk> |
| In reply to | #50007 |
Jeff Barnett <jbb@notatt.com> writes:
> 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?
Measured.
> How long would you estimate that a well-written TM interpreter on
> modern hardware needs to interpret the above? A few seconds or
> minutes?
$ time ./tm bb-5-2 ""
A B C D E H
1 1LC 1RB _LE 1LD _LA
_ 1RB 1RC 1RD 1LA 1RH
steps=47176874
real 0m0.237s
user 0m0.237s
sys 0m0.000s
This is a C++ interpreter I've just written so that I can compare
designs with anything PO produces. I've not worked on making it fast
though I compiler with -O3 for this test.
It uses a plain std::string for the tape, so I imagine the quality of
the C++ library is the key factor (I've not profiled it yet).
(That table at the start is just the sates transition table written in a
compact form.)
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2022-05-08 11:08 -0600 |
| Message-ID | <t58tdr$93p$1@dont-email.me> |
| In reply to | #50028 |
On 5/8/2022 7:44 AM, Ben wrote:
> Jeff Barnett <jbb@notatt.com> writes:
>
>> 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?
>
> Measured.
>
>> How long would you estimate that a well-written TM interpreter on
>> modern hardware needs to interpret the above? A few seconds or
>> minutes?
>
> $ time ./tm bb-5-2 ""
> A B C D E H
> 1 1LC 1RB _LE 1LD _LA
> _ 1RB 1RC 1RD 1LA 1RH
>
> steps=47176874
>
> real 0m0.237s
> user 0m0.237s
> sys 0m0.000s
>
> This is a C++ interpreter I've just written so that I can compare
> designs with anything PO produces. I've not worked on making it fast
> though I compiler with -O3 for this test.
>
> It uses a plain std::string for the tape, so I imagine the quality of
> the C++ library is the key factor (I've not profiled it yet).
>
> (That table at the start is just the sates transition table written in a
> compact form.)
Impressive. I'm going to conjecture from the rate of interpretation
47M/.237s ~ 200,000,000 states per second that TM definition, your code,
and used library code must have all snuggled into the machine cache. I'm
also assuming that the C++ code (because of the nature of the
computation) does not lend itself to using multiple cores which makes
the speed all that more impressive.
Other questions:
Did you directly set up a (state X character) -> (quintuple) lookup
rather than doing it in two steps? I don't think that wouldn't make a
big difference for this example but could for TM definitions with much
larger quintuple tables.
Do C++ character arrays (strings?) have provisions to grow if a char is
pushed passed the structure's end? I'm thinking of Lisp arrays with fill
pointers as an example. To ask the question a different way which of the
following did you do to set the initial size of the "tape": determine
empirically, start arbitrarily and let the C++ system run-time grow the
structure as needed, or start arbitrarily and use your own code to deal
with the issue?
--
Jeff Barnett
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-08 19:27 +0100 |
| Message-ID | <87tu9zubfs.fsf@bsb.me.uk> |
| In reply to | #50031 |
Jeff Barnett <jbb@notatt.com> writes:
> On 5/8/2022 7:44 AM, Ben wrote:
>> Jeff Barnett <jbb@notatt.com> writes:
>>
>>> 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?
>> Measured.
>>
>>> How long would you estimate that a well-written TM interpreter on
>>> modern hardware needs to interpret the above? A few seconds or
>>> minutes?
>> $ time ./tm bb-5-2 ""
>> A B C D E H
>> 1 1LC 1RB _LE 1LD _LA
>> _ 1RB 1RC 1RD 1LA 1RH
>> steps=47176874
>> real 0m0.237s
>> user 0m0.237s
>> sys 0m0.000s
>> This is a C++ interpreter I've just written so that I can compare
>> designs with anything PO produces. I've not worked on making it fast
>> though I compiler with -O3 for this test.
>> It uses a plain std::string for the tape, so I imagine the quality of
>> the C++ library is the key factor (I've not profiled it yet).
>> (That table at the start is just the sates transition table written in a
>> compact form.)
>
> Impressive.
Thanks, but there's no skill involved, other that not picking any part
of the design that looks like a certain loser.
> I'm going to conjecture from the rate of interpretation 47M/.237s ~
> 200,000,000 states per second that TM definition, your code, and used
> library code must have all snuggled into the machine cache.
Seems likely.
> I'm also
> assuming that the C++ code (because of the nature of the computation)
> does not lend itself to using multiple cores which makes the speed all
> that more impressive.
Yes, single core. My laptop is not an old banger (1.6Ghz i5-8256U), but
even so I was surprised.
> Other questions:
>
> Did you directly set up a (state X character) -> (quintuple) lookup
> rather than doing it in two steps?
There's only one lookup, but not that one. In my current design the
states are objects that hold a char to triple map, the triple being the
character to write, the tape movement, and a pointer to the next state).
The inner loop is therefore very tight. I could (probably) speed it up
a bit by using an array for that lookup, but I imagined I might like to
use fancy Unicode symbols at some stage and a map will work better for
that.
> I don't think that wouldn't make a big difference for this example but
> could for TM definitions with much larger quintuple tables.
>
> Do C++ character arrays (strings?) have provisions to grow if a char
> is pushed passed the structure's end?
push_back is amortised constant time whereas append and insert give no
guarantees. I think glibc goes to some effort to make appending and
growing at the front quote efficient.
> I'm thinking of Lisp arrays with
> fill pointers as an example. To ask the question a different way which
> of the following did you do to set the initial size of the "tape":
> determine empirically, start arbitrarily and let the C++ system
> run-time grow the structure as needed, or start arbitrarily and use
> your own code to deal with the issue?
My code is utterly trivial. The tape is a std::string to which I assign
the input. All that happens after that is that tape[head] is assigned
to, and the string is grown by one blank, either at the front or the
back, if the tape movement requires it.
I'll post the code when the time comes if case anyone cares to see it.
I plan to do a Haskell version too. I used to have one, but that got
lost in retirement.
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-05-08 15:22 -0400 |
| Message-ID | <zLUdK.4623$arR.255@fx48.iad> |
| In reply to | #50034 |
On 5/8/22 2:27 PM, Ben wrote:
> Jeff Barnett <jbb@notatt.com> writes:
>
>> On 5/8/2022 7:44 AM, Ben wrote:
>>> Jeff Barnett <jbb@notatt.com> writes:
>>>
>>>> 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?
>>> Measured.
>>>
>>>> How long would you estimate that a well-written TM interpreter on
>>>> modern hardware needs to interpret the above? A few seconds or
>>>> minutes?
>>> $ time ./tm bb-5-2 ""
>>> A B C D E H
>>> 1 1LC 1RB _LE 1LD _LA
>>> _ 1RB 1RC 1RD 1LA 1RH
>>> steps=47176874
>>> real 0m0.237s
>>> user 0m0.237s
>>> sys 0m0.000s
>>> This is a C++ interpreter I've just written so that I can compare
>>> designs with anything PO produces. I've not worked on making it fast
>>> though I compiler with -O3 for this test.
>>> It uses a plain std::string for the tape, so I imagine the quality of
>>> the C++ library is the key factor (I've not profiled it yet).
>>> (That table at the start is just the sates transition table written in a
>>> compact form.)
>>
>> Impressive.
>
> Thanks, but there's no skill involved, other that not picking any part
> of the design that looks like a certain loser.
>
>> I'm going to conjecture from the rate of interpretation 47M/.237s ~
>> 200,000,000 states per second that TM definition, your code, and used
>> library code must have all snuggled into the machine cache.
>
> Seems likely.
>
>> I'm also
>> assuming that the C++ code (because of the nature of the computation)
>> does not lend itself to using multiple cores which makes the speed all
>> that more impressive.
>
> Yes, single core. My laptop is not an old banger (1.6Ghz i5-8256U), but
> even so I was surprised.
>
>> Other questions:
>>
>> Did you directly set up a (state X character) -> (quintuple) lookup
>> rather than doing it in two steps?
>
> There's only one lookup, but not that one. In my current design the
> states are objects that hold a char to triple map, the triple being the
> character to write, the tape movement, and a pointer to the next state).
>
> The inner loop is therefore very tight. I could (probably) speed it up
> a bit by using an array for that lookup, but I imagined I might like to
> use fancy Unicode symbols at some stage and a map will work better for
> that.
My thinking is that there are only two things that have the ability to
"cost" time. One is tape management, but using an object that acts like
an array which is indexed in makes this fast except when we need to
expand it, but that will generally amortize to a small value. (Letting
the string class do that isn't a bad option).
The second "costly" operation is looking up the rule based on current
state / tape symbol. For speed this really needs to be O(1) (at least
amortized). If we reduce our state and input symbols to an internal
numbering of 0-n an array works great. If we limit our states to 'ascii
characters' then the 256 x 256 array isn't outlandish in space
requirements for modern machines.
If you want full Unicode characters, then either you need the conversion
to a simple 0-n enumeration, or going to a hash table to store the
rules. The question becomes which cost more the input/output conversion
to use 0-n values, or hashing (and handling the possible collisions).
My thought is that in the 0-n enumeration, the table is "dense" in the
sense that all non-terminal state will be fully filled out. (And
terminal states don't actually need an entry, just a value recognized as
terminal).
>
>> I don't think that wouldn't make a big difference for this example but
>> could for TM definitions with much larger quintuple tables.
>>
>> Do C++ character arrays (strings?) have provisions to grow if a char
>> is pushed passed the structure's end?
>
> push_back is amortised constant time whereas append and insert give no
> guarantees. I think glibc goes to some effort to make appending and
> growing at the front quote efficient.
>
>> I'm thinking of Lisp arrays with
>> fill pointers as an example. To ask the question a different way which
>> of the following did you do to set the initial size of the "tape":
>> determine empirically, start arbitrarily and let the C++ system
>> run-time grow the structure as needed, or start arbitrarily and use
>> your own code to deal with the issue?
>
> My code is utterly trivial. The tape is a std::string to which I assign
> the input. All that happens after that is that tape[head] is assigned
> to, and the string is grown by one blank, either at the front or the
> back, if the tape movement requires it.
>
> I'll post the code when the time comes if case anyone cares to see it.
>
> I plan to do a Haskell version too. I used to have one, but that got
> lost in retirement.
>
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2022-05-08 20:30 +0100 |
| Message-ID | <20220508203050.00001cd7@reddwarf.jmc> |
| In reply to | #50038 |
On Sun, 8 May 2022 15:22:07 -0400
Richard Damon <Richard@Damon-Family.org> wrote:
> On 5/8/22 2:27 PM, Ben wrote:
> > Jeff Barnett <jbb@notatt.com> writes:
> >
> >> On 5/8/2022 7:44 AM, Ben wrote:
> >>> Jeff Barnett <jbb@notatt.com> writes:
> >>>
> >>>> 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?
> >>> Measured.
> >>>
> >>>> How long would you estimate that a well-written TM interpreter on
> >>>> modern hardware needs to interpret the above? A few seconds or
> >>>> minutes?
> >>> $ time ./tm bb-5-2 ""
> >>> A B C D E H
> >>> 1 1LC 1RB _LE 1LD _LA
> >>> _ 1RB 1RC 1RD 1LA 1RH
> >>> steps=47176874
> >>> real 0m0.237s
> >>> user 0m0.237s
> >>> sys 0m0.000s
> >>> This is a C++ interpreter I've just written so that I can compare
> >>> designs with anything PO produces. I've not worked on making it
> >>> fast though I compiler with -O3 for this test.
> >>> It uses a plain std::string for the tape, so I imagine the
> >>> quality of the C++ library is the key factor (I've not profiled
> >>> it yet). (That table at the start is just the sates transition
> >>> table written in a compact form.)
> >>
> >> Impressive.
> >
> > Thanks, but there's no skill involved, other that not picking any
> > part of the design that looks like a certain loser.
> >
> >> I'm going to conjecture from the rate of interpretation 47M/.237s ~
> >> 200,000,000 states per second that TM definition, your code, and
> >> used library code must have all snuggled into the machine cache.
> >
> > Seems likely.
> >
> >> I'm also
> >> assuming that the C++ code (because of the nature of the
> >> computation) does not lend itself to using multiple cores which
> >> makes the speed all that more impressive.
> >
> > Yes, single core. My laptop is not an old banger (1.6Ghz
> > i5-8256U), but even so I was surprised.
> >
> >> Other questions:
> >>
> >> Did you directly set up a (state X character) -> (quintuple) lookup
> >> rather than doing it in two steps?
> >
> > There's only one lookup, but not that one. In my current design the
> > states are objects that hold a char to triple map, the triple being
> > the character to write, the tape movement, and a pointer to the
> > next state).
> >
> > The inner loop is therefore very tight. I could (probably) speed
> > it up a bit by using an array for that lookup, but I imagined I
> > might like to use fancy Unicode symbols at some stage and a map
> > will work better for that.
>
> My thinking is that there are only two things that have the ability
> to "cost" time. One is tape management, but using an object that acts
> like an array which is indexed in makes this fast except when we need
> to expand it, but that will generally amortize to a small value.
> (Letting the string class do that isn't a bad option).
>
> The second "costly" operation is looking up the rule based on current
> state / tape symbol. For speed this really needs to be O(1) (at least
> amortized). If we reduce our state and input symbols to an internal
> numbering of 0-n an array works great. If we limit our states to
> 'ascii characters' then the 256 x 256 array isn't outlandish in space
> requirements for modern machines.
>
> If you want full Unicode characters, then either you need the
> conversion to a simple 0-n enumeration, or going to a hash table to
> store the rules. The question becomes which cost more the
> input/output conversion to use 0-n values, or hashing (and handling
> the possible collisions).
>
> My thought is that in the 0-n enumeration, the table is "dense" in
> the sense that all non-terminal state will be fully filled out. (And
> terminal states don't actually need an entry, just a value recognized
> as terminal).
>
> >
> >> I don't think that wouldn't make a big difference for this example
> >> but could for TM definitions with much larger quintuple tables.
> >>
> >> Do C++ character arrays (strings?) have provisions to grow if a
> >> char is pushed passed the structure's end?
> >
> > push_back is amortised constant time whereas append and insert give
> > no guarantees. I think glibc goes to some effort to make appending
> > and growing at the front quote efficient.
Have you considered std::deque? Might be worth trying if the tape
sequence isn't small.
/Flibble
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-09 10:53 -0500 |
| Message-ID | <sdydnYLI-KSQpOT_nZ2dnUU7_81g4p2d@giganews.com> |
| In reply to | #50039 |
On 5/8/2022 2:30 PM, Mr Flibble wrote:
> On Sun, 8 May 2022 15:22:07 -0400
> Richard Damon <Richard@Damon-Family.org> wrote:
>
>> On 5/8/22 2:27 PM, Ben wrote:
>>> Jeff Barnett <jbb@notatt.com> writes:
>>>
>>>> On 5/8/2022 7:44 AM, Ben wrote:
>>>>> Jeff Barnett <jbb@notatt.com> writes:
>>>>>
>>>>>> 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?
>>>>> Measured.
>>>>>
>>>>>> How long would you estimate that a well-written TM interpreter on
>>>>>> modern hardware needs to interpret the above? A few seconds or
>>>>>> minutes?
>>>>> $ time ./tm bb-5-2 ""
>>>>> A B C D E H
>>>>> 1 1LC 1RB _LE 1LD _LA
>>>>> _ 1RB 1RC 1RD 1LA 1RH
>>>>> steps=47176874
>>>>> real 0m0.237s
>>>>> user 0m0.237s
>>>>> sys 0m0.000s
>>>>> This is a C++ interpreter I've just written so that I can compare
>>>>> designs with anything PO produces. I've not worked on making it
>>>>> fast though I compiler with -O3 for this test.
>>>>> It uses a plain std::string for the tape, so I imagine the
>>>>> quality of the C++ library is the key factor (I've not profiled
>>>>> it yet). (That table at the start is just the sates transition
>>>>> table written in a compact form.)
>>>>
>>>> Impressive.
>>>
>>> Thanks, but there's no skill involved, other that not picking any
>>> part of the design that looks like a certain loser.
>>>
>>>> I'm going to conjecture from the rate of interpretation 47M/.237s ~
>>>> 200,000,000 states per second that TM definition, your code, and
>>>> used library code must have all snuggled into the machine cache.
>>>
>>> Seems likely.
>>>
>>>> I'm also
>>>> assuming that the C++ code (because of the nature of the
>>>> computation) does not lend itself to using multiple cores which
>>>> makes the speed all that more impressive.
>>>
>>> Yes, single core. My laptop is not an old banger (1.6Ghz
>>> i5-8256U), but even so I was surprised.
>>>
>>>> Other questions:
>>>>
>>>> Did you directly set up a (state X character) -> (quintuple) lookup
>>>> rather than doing it in two steps?
>>>
>>> There's only one lookup, but not that one. In my current design the
>>> states are objects that hold a char to triple map, the triple being
>>> the character to write, the tape movement, and a pointer to the
>>> next state).
>>>
>>> The inner loop is therefore very tight. I could (probably) speed
>>> it up a bit by using an array for that lookup, but I imagined I
>>> might like to use fancy Unicode symbols at some stage and a map
>>> will work better for that.
>>
>> My thinking is that there are only two things that have the ability
>> to "cost" time. One is tape management, but using an object that acts
>> like an array which is indexed in makes this fast except when we need
>> to expand it, but that will generally amortize to a small value.
>> (Letting the string class do that isn't a bad option).
>>
>> The second "costly" operation is looking up the rule based on current
>> state / tape symbol. For speed this really needs to be O(1) (at least
>> amortized). If we reduce our state and input symbols to an internal
>> numbering of 0-n an array works great. If we limit our states to
>> 'ascii characters' then the 256 x 256 array isn't outlandish in space
>> requirements for modern machines.
>>
>> If you want full Unicode characters, then either you need the
>> conversion to a simple 0-n enumeration, or going to a hash table to
>> store the rules. The question becomes which cost more the
>> input/output conversion to use 0-n values, or hashing (and handling
>> the possible collisions).
>>
>> My thought is that in the 0-n enumeration, the table is "dense" in
>> the sense that all non-terminal state will be fully filled out. (And
>> terminal states don't actually need an entry, just a value recognized
>> as terminal).
>>
>>>
>>>> I don't think that wouldn't make a big difference for this example
>>>> but could for TM definitions with much larger quintuple tables.
>>>>
>>>> Do C++ character arrays (strings?) have provisions to grow if a
>>>> char is pushed passed the structure's end?
>>>
>>> push_back is amortised constant time whereas append and insert give
>>> no guarantees. I think glibc goes to some effort to make appending
>>> and growing at the front quote efficient.
>
> Have you considered std::deque? Might be worth trying if the tape
> sequence isn't small.
>
> /Flibble
>
The classic TM is not allowed to move before its beginning thus a
std::vector is best for the tape.
--
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-09 23:08 +0100 |
| Message-ID | <87wneuqryi.fsf@bsb.me.uk> |
| In reply to | #50082 |
olcott <NoOne@NoWhere.com> writes: > The classic TM is not allowed to move before its beginning thus a > std::vector is best for the tape. In the usual definition the tape has no beginning so I can't make out what you are saying here. Something about it is wrong but I tell exactly what. -- Ben. "le génie humain a des limites, quand la bêtise humaine n’en a pas" Alexandre Dumas (fils)
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-09 17:32 -0500 |
| Message-ID | <XcmdnbaZ-aTnC-T_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50133 |
On 5/9/2022 5:08 PM, Ben wrote: > olcott <NoOne@NoWhere.com> writes: > >> The classic TM is not allowed to move before its beginning thus a >> std::vector is best for the tape. > > In the usual definition the tape has no beginning so I can't make out > what you are saying here. Something about it is wrong but I tell > exactly what. > Linz agrees with you, Kozen agrees with me and I can't find where Sipser specifies this. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-05-09 20:31 -0400 |
| Message-ID | <JnieK.57309$t72a.38684@fx10.iad> |
| In reply to | #50138 |
On 5/9/22 6:32 PM, olcott wrote: > On 5/9/2022 5:08 PM, Ben wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> The classic TM is not allowed to move before its beginning thus a >>> std::vector is best for the tape. >> >> In the usual definition the tape has no beginning so I can't make out >> what you are saying here. Something about it is wrong but I tell >> exactly what. >> > Linz agrees with you, Kozen agrees with me and I can't find where Sipser > specifies this. > The truth is that this is one area where different models of Turing Machines define the tape differently. Just like some allow for multiple tapes (and thus multiple "tape op" fields in the instruction, and multiple tape symbols in the rule lookup.) It can be shown that all the variations are computationally equivalent, it just changes how complicated some operations are. For a tape with a fixed beginning spot, if you wanted to extend it in that dirrection, you just need a short program to go to the other end and move ever cell out one cell to make room. Since the tape is finite, this is by definition doable in a finite number of steps.
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-10 01:37 +0100 |
| Message-ID | <87r152mdd2.fsf@bsb.me.uk> |
| In reply to | #50138 |
olcott <NoOne@NoWhere.com> writes: > On 5/9/2022 5:08 PM, Ben wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> The classic TM is not allowed to move before its beginning thus a >>> std::vector is best for the tape. >> In the usual definition the tape has no beginning so I can't make out >> what you are saying here. Something about it is wrong but I tell >> exactly what. >> > Linz agrees with you, Kozen agrees with me and I can't find where > Sipser specifies this. The definition is simpler if the tape in unbounded at both ends. If you are going to use any of the BB candidates as tests, you need a tape open at both ends. Given that you've gone for a one-ended tape, what rule do you apply when the transition function specifies going left from the left-most cell? I've modified my implementation to do either, just in case we end up comparing traces. -- Ben. "le génie humain a des limites, quand la bêtise humaine n’en a pas" Alexandre Dumas (fils)
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-09 20:29 -0500 |
| Message-ID | <ZK-dnZfTk9JjIuT_nZ2dnUU7_8xh4p2d@giganews.com> |
| In reply to | #50174 |
On 5/9/2022 7:37 PM, Ben wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 5/9/2022 5:08 PM, Ben wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> The classic TM is not allowed to move before its beginning thus a >>>> std::vector is best for the tape. >>> In the usual definition the tape has no beginning so I can't make out >>> what you are saying here. Something about it is wrong but I tell >>> exactly what. >>> >> Linz agrees with you, Kozen agrees with me and I can't find where >> Sipser specifies this. > > The definition is simpler if the tape in unbounded at both ends. If you > are going to use any of the BB candidates as tests, you need a tape open > at both ends. > > Given that you've gone for a one-ended tape, what rule do you apply when > the transition function specifies going left from the left-most cell? > (a) Abnormal termination error index out-of-bounds. (b) Extend the std::vector. > I've modified my implementation to do either, just in case we end up > comparing traces. > -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-10 11:35 +0100 |
| Message-ID | <87a6bpn08n.fsf@bsb.me.uk> |
| In reply to | #50176 |
olcott <NoOne@NoWhere.com> writes: > On 5/9/2022 7:37 PM, Ben wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> On 5/9/2022 5:08 PM, Ben wrote: >>>> olcott <NoOne@NoWhere.com> writes: >>>> >>>>> The classic TM is not allowed to move before its beginning thus a >>>>> std::vector is best for the tape. >>>> In the usual definition the tape has no beginning so I can't make out >>>> what you are saying here. Something about it is wrong but I tell >>>> exactly what. >>>> >>> Linz agrees with you, Kozen agrees with me and I can't find where >>> Sipser specifies this. >> >> The definition is simpler if the tape in unbounded at both ends. If you >> are going to use any of the BB candidates as tests, you need a tape open >> at both ends. >> >> Given that you've gone for a one-ended tape, what rule do you apply when >> the transition function specifies going left from the left-most cell? >> > (a) Abnormal termination error index out-of-bounds. There is no such concept for a Turing machine. The TM can be defined to halt in this situation (though I don't know any authors who specify it like that) but halting is halting no matter the reason. > (b) Extend the std::vector. Why extend the vector if you've terminated? >> I've modified my implementation to do either, just in case we end up >> comparing traces. Anywhere closer to writing E and specifying P? -- Ben. "le génie humain a des limites, quand la bêtise humaine n’en a pas" Alexandre Dumas (fils)
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-10 19:12 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape] |
| Message-ID | <cr-dnW5GGv7kYuf_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50174 |
On 5/9/2022 7:37 PM, Ben wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 5/9/2022 5:08 PM, Ben wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> The classic TM is not allowed to move before its beginning thus a >>>> std::vector is best for the tape. >>> In the usual definition the tape has no beginning so I can't make out >>> what you are saying here. Something about it is wrong but I tell >>> exactly what. >>> >> Linz agrees with you, Kozen agrees with me and I can't find where >> Sipser specifies this. > > The definition is simpler if the tape in unbounded at both ends. If you > are going to use any of the BB candidates as tests, you need a tape open > at both ends. > You have convinced me that this is the best way I am going to implement this using David kleinecke's solution. It is a much more efficient and simpler way to implement push_back() and push_front() than std::deque that also has none of the pitfalls such as: https://www.cplusplus.com/reference/deque/deque/push_front/ All iterators related to this container are invalidated. > Given that you've gone for a one-ended tape, what rule do you apply when > the transition function specifies going left from the left-most cell? > > I've modified my implementation to do either, just in case we end up > comparing traces. > -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2022-05-08 14:51 -0600 |
| Message-ID | <t59ag5$ima$1@dont-email.me> |
| In reply to | #50038 |
On 5/8/2022 1:22 PM, Richard Damon wrote:
> On 5/8/22 2:27 PM, Ben wrote:
>> Jeff Barnett <jbb@notatt.com> writes:
>>
>>> On 5/8/2022 7:44 AM, Ben wrote:
>>>> Jeff Barnett <jbb@notatt.com> writes:
>>>>
>>>>> 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?
>>>> Measured.
>>>>
>>>>> How long would you estimate that a well-written TM interpreter on
>>>>> modern hardware needs to interpret the above? A few seconds or
>>>>> minutes?
>>>> $ time ./tm bb-5-2 ""
>>>> A B C D E H
>>>> 1 1LC 1RB _LE 1LD _LA
>>>> _ 1RB 1RC 1RD 1LA 1RH
>>>> steps=47176874
>>>> real 0m0.237s
>>>> user 0m0.237s
>>>> sys 0m0.000s
>>>> This is a C++ interpreter I've just written so that I can compare
>>>> designs with anything PO produces. I've not worked on making it fast
>>>> though I compiler with -O3 for this test.
>>>> It uses a plain std::string for the tape, so I imagine the quality of
>>>> the C++ library is the key factor (I've not profiled it yet).
>>>> (That table at the start is just the sates transition table written
>>>> in a
>>>> compact form.)
>>>
>>> Impressive.
>>
>> Thanks, but there's no skill involved, other that not picking any part
>> of the design that looks like a certain loser.
>>
>>> I'm going to conjecture from the rate of interpretation 47M/.237s ~
>>> 200,000,000 states per second that TM definition, your code, and used
>>> library code must have all snuggled into the machine cache.
>>
>> Seems likely.
>>
>>> I'm also
>>> assuming that the C++ code (because of the nature of the computation)
>>> does not lend itself to using multiple cores which makes the speed all
>>> that more impressive.
>>
>> Yes, single core. My laptop is not an old banger (1.6Ghz i5-8256U), but
>> even so I was surprised.
>>
>>> Other questions:
>>>
>>> Did you directly set up a (state X character) -> (quintuple) lookup
>>> rather than doing it in two steps?
>>
>> There's only one lookup, but not that one. In my current design the
>> states are objects that hold a char to triple map, the triple being the
>> character to write, the tape movement, and a pointer to the next state).
>>
>> The inner loop is therefore very tight. I could (probably) speed it up
>> a bit by using an array for that lookup, but I imagined I might like to
>> use fancy Unicode symbols at some stage and a map will work better for
>> that.
>
> My thinking is that there are only two things that have the ability to
> "cost" time. One is tape management, but using an object that acts like
> an array which is indexed in makes this fast except when we need to
> expand it, but that will generally amortize to a small value. (Letting
> the string class do that isn't a bad option).
>
> The second "costly" operation is looking up the rule based on current
> state / tape symbol. For speed this really needs to be O(1) (at least
> amortized). If we reduce our state and input symbols to an internal
> numbering of 0-n an array works great. If we limit our states to 'ascii
> characters' then the 256 x 256 array isn't outlandish in space
> requirements for modern machines.
>
> If you want full Unicode characters, then either you need the conversion
> to a simple 0-n enumeration, or going to a hash table to store the
> rules. The question becomes which cost more the input/output conversion
> to use 0-n values, or hashing (and handling the possible collisions).
>
> My thought is that in the 0-n enumeration, the table is "dense" in the
> sense that all non-terminal state will be fully filled out. (And
> terminal states don't actually need an entry, just a value recognized as
> terminal).
Why not just "compile" the tuples into a graph? Take all the tuples
defined by one state and sort them on current character and look up by
binary search. If you have a truly large character set and many states
have lots of out-branches, then organize the nodes using hash tables as
you suggest.
It's interesting to note that many Common Lisp make such representation
decisions under the table especially for sorting and hashing. For
example sorting chooses from n^2 complexity sorting for short sequences
to n*log(n) varieties as the input is longer. Hashing starts with just a
linear list and linear time searching for small tables and switches
representations to arrays when the number of elements increase. Many of
these strategies use strategies depending on the comparison predicate.
All of these morphs are swept under the rug by using its object system
and dynamic ability to morph structures, dynamically, to different types.
>
>>
>>> I don't think that wouldn't make a big difference for this example but
>>> could for TM definitions with much larger quintuple tables.
>>>
>>> Do C++ character arrays (strings?) have provisions to grow if a char
>>> is pushed passed the structure's end?
>>
>> push_back is amortised constant time whereas append and insert give no
>> guarantees. I think glibc goes to some effort to make appending and
>> growing at the front quote efficient.
>>
>>> I'm thinking of Lisp arrays with
>>> fill pointers as an example. To ask the question a different way which
>>> of the following did you do to set the initial size of the "tape":
>>> determine empirically, start arbitrarily and let the C++ system
>>> run-time grow the structure as needed, or start arbitrarily and use
>>> your own code to deal with the issue?
>>
>> My code is utterly trivial. The tape is a std::string to which I assign
>> the input. All that happens after that is that tape[head] is assigned
>> to, and the string is grown by one blank, either at the front or the
>> back, if the tape movement requires it.
>>
>> I'll post the code when the time comes if case anyone cares to see it.
>>
>> I plan to do a Haskell version too. I used to have one, but that got
>> lost in retirement.--
Jeff Barnett
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-09 10:18 -0500 |
| Message-ID | <0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> |
| In reply to | #50034 |
On 5/8/2022 1:27 PM, Ben wrote:
> Jeff Barnett <jbb@notatt.com> writes:
>
>> On 5/8/2022 7:44 AM, Ben wrote:
>>> Jeff Barnett <jbb@notatt.com> writes:
>>>
>>>> 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?
>>> Measured.
>>>
>>>> How long would you estimate that a well-written TM interpreter on
>>>> modern hardware needs to interpret the above? A few seconds or
>>>> minutes?
>>> $ time ./tm bb-5-2 ""
>>> A B C D E H
>>> 1 1LC 1RB _LE 1LD _LA
>>> _ 1RB 1RC 1RD 1LA 1RH
>>> steps=47176874
>>> real 0m0.237s
>>> user 0m0.237s
>>> sys 0m0.000s
>>> This is a C++ interpreter I've just written so that I can compare
>>> designs with anything PO produces. I've not worked on making it fast
>>> though I compiler with -O3 for this test.
>>> It uses a plain std::string for the tape, so I imagine the quality of
>>> the C++ library is the key factor (I've not profiled it yet).
>>> (That table at the start is just the sates transition table written in a
>>> compact form.)
>>
>> Impressive.
>
> Thanks, but there's no skill involved, other that not picking any part
> of the design that looks like a certain loser.
>
>> I'm going to conjecture from the rate of interpretation 47M/.237s ~
>> 200,000,000 states per second that TM definition, your code, and used
>> library code must have all snuggled into the machine cache.
>
> Seems likely.
>
>> I'm also
>> assuming that the C++ code (because of the nature of the computation)
>> does not lend itself to using multiple cores which makes the speed all
>> that more impressive.
>
> Yes, single core. My laptop is not an old banger (1.6Ghz i5-8256U), but
> even so I was surprised.
>
>> Other questions:
>>
>> Did you directly set up a (state X character) -> (quintuple) lookup
>> rather than doing it in two steps?
>
> There's only one lookup, but not that one. In my current design the
> states are objects that hold a char to triple map, the triple being the
> character to write, the tape movement, and a pointer to the next state).
>
> The inner loop is therefore very tight. I could (probably) speed it up
> a bit by using an array for that lookup, but I imagined I might like to
> use fancy Unicode symbols at some stage and a map will work better for
> that.
>
>> I don't think that wouldn't make a big difference for this example but
>> could for TM definitions with much larger quintuple tables.
>>
>> Do C++ character arrays (strings?) have provisions to grow if a char
>> is pushed passed the structure's end?
>
> push_back is amortised constant time whereas append and insert give no
> guarantees. I think glibc goes to some effort to make appending and
> growing at the front quote efficient.
>
>> I'm thinking of Lisp arrays with
>> fill pointers as an example. To ask the question a different way which
>> of the following did you do to set the initial size of the "tape":
>> determine empirically, start arbitrarily and let the C++ system
>> run-time grow the structure as needed, or start arbitrarily and use
>> your own code to deal with the issue?
>
> My code is utterly trivial. The tape is a std::string to which I assign
> the input. All that happens after that is that tape[head] is assigned
> to, and the string is grown by one blank, either at the front or the
> back, if the tape movement requires it.
>
Conventionally tapes have an actual beginning, yet no fixed end.
> I'll post the code when the time comes if case anyone cares to see it.
>
> I plan to do a Haskell version too. I used to have one, but that got
> lost in retirement.
>
--
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-09 23:14 +0100 |
| Message-ID | <87r152qrp2.fsf@bsb.me.uk> |
| In reply to | #50069 |
olcott <NoOne@NoWhere.com> writes: > On 5/8/2022 1:27 PM, Ben wrote: >> My code is utterly trivial. The tape is a std::string to which I assign >> the input. All that happens after that is that tape[head] is assigned >> to, and the string is grown by one blank, either at the front or the >> back, if the tape movement requires it. > > Conventionally tapes have an actual beginning, yet no fixed end. No. -- Ben. "le génie humain a des limites, quand la bêtise humaine n’en a pas" Alexandre Dumas (fils)
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-09 17:42 -0500 |
| Message-ID | <rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50135 |
On 5/9/2022 5:14 PM, Ben wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 5/8/2022 1:27 PM, Ben wrote: > >>> My code is utterly trivial. The tape is a std::string to which I assign >>> the input. All that happens after that is that tape[head] is assigned >>> to, and the string is grown by one blank, either at the front or the >>> back, if the tape movement requires it. >> >> Conventionally tapes have an actual beginning, yet no fixed end. > > No. > Sipser and Kozen agree with me, Linz agrees with you. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
Page 2 of 10 — ← Prev page 1 [2] 3 4 … 10 Next page →
Back to top | Article view | comp.theory
csiph-web