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 3 of 10 — ← Prev page 1 2 [3] 4 5 … 10 Next page →
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-10 01:13 +0100 |
| Message-ID | <87wneumegw.fsf@bsb.me.uk> |
| In reply to | #50141 |
olcott <NoOne@NoWhere.com> writes: > 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. None of these authors say what is "conventional". What is certain is that if there were a convention, an author not using that convention should say as much. You'll find, however, that that is not the case. -- 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:28 -0500 |
| Message-ID | <ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> |
| In reply to | #50167 |
On 5/9/2022 7:13 PM, Ben wrote: > olcott <NoOne@NoWhere.com> writes: > >> 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. > > None of these authors say what is "conventional". What is certain is > that if there were a convention, an author not using that convention > should say as much. You'll find, however, that that is not the case. > How would you define conventional? The most typical use is one way unlimited, right? -- 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 23:34 -0400 |
| Message-ID | <63leK.5428$Xh%d.2134@fx98.iad> |
| In reply to | #50175 |
On 5/9/22 9:28 PM, olcott wrote: > On 5/9/2022 7:13 PM, Ben wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> 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. >> >> None of these authors say what is "conventional". What is certain is >> that if there were a convention, an author not using that convention >> should say as much. You'll find, however, that that is not the case. >> > > How would you define conventional? > The most typical use is one way unlimited, right? > Actually, I see unlimited in both directions as more normal, otherwise you get the odd case of what happens if the system tries to move past the end of the tape. It basically says you need a special character for that end of the tape, which just adds an asymmetry to the system. As I mentioned, it is just a small bit of code to implement an expand the tape one cell in that direction that just needs to be added to every case to handle running into the beginning of tape symbol, so there is no difference in what can be computed, just how much work you need to do that computation. The one-directional tape may be easier on the simulator, but that is just a small advantage, and the impact on the Turing Machine is an uglification and asymmetry so it seems common to just make the tape double ended. Maybe very simple examples for teaching might seem simpler with a single ended, since you don't need to think as much about where you need to leave space on your page that you are keeping track of your tape on, and many of the simple problems only need to extend in one direction, but that is only a small benifit, and again, you need to add a dedicated 'Beginning of tape' symbol to let the machine know that is the edge (you might be able to make it double as an end of tape that is allowed to be overwritten in the other direction.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2022-05-10 00:24 -0700 |
| Message-ID | <b30f22cb-7bbd-4336-9741-7fd74980be8en@googlegroups.com> |
| In reply to | #50179 |
On Tuesday, 10 May 2022 at 04:34:31 UTC+1, richar...@gmail.com wrote: > On 5/9/22 9:28 PM, olcott wrote: > > On 5/9/2022 7:13 PM, Ben wrote: > >> olcott <No...@NoWhere.com> writes: > >> > >>> On 5/9/2022 5:14 PM, Ben wrote: > >>>> olcott <No...@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. > >> > >> None of these authors say what is "conventional". What is certain is > >> that if there were a convention, an author not using that convention > >> should say as much. You'll find, however, that that is not the case. > >> > > > > How would you define conventional? > > The most typical use is one way unlimited, right? > > > Actually, I see unlimited in both directions as more normal, otherwise > you get the odd case of what happens if the system tries to move past > the end of the tape. It basically says you need a special character for > that end of the tape, which just adds an asymmetry to the system. > > As I mentioned, it is just a small bit of code to implement an expand > the tape one cell in that direction that just needs to be added to every > case to handle running into the beginning of tape symbol, so there is no > difference in what can be computed, just how much work you need to do > that computation. > > The one-directional tape may be easier on the simulator, but that is > just a small advantage, and the impact on the Turing Machine is an > uglification and asymmetry so it seems common to just make the tape > double ended. > > Maybe very simple examples for teaching might seem simpler with a single > ended, since you don't need to think as much about where you need to > leave space on your page that you are keeping track of your tape on, and > many of the simple problems only need to extend in one direction, but > that is only a small benifit, and again, you need to add a dedicated > 'Beginning of tape' symbol to let the machine know that is the edge (you > might be able to make it double as an end of tape that is allowed to be > overwritten in the other direction. > As a mathematical model, a tape which is open at both ends is simpler. If you are engineering a physical machine, a tape which extends arbitrarily in only one direction may well be easier to implement. As you say, it's easier to draw the tape, for example.
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-10 11:31 +0100 |
| Message-ID | <87fslhn0fj.fsf@bsb.me.uk> |
| In reply to | #50175 |
olcott <NoOne@NoWhere.com> writes: > On 5/9/2022 7:13 PM, Ben wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> 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. >> >> None of these authors say what is "conventional". What is certain is >> that if there were a convention, an author not using that convention >> should say as much. You'll find, however, that that is not the case. > > How would you define conventional? "the accepted or traditional method of doing something" > The most typical use is one way unlimited, right? I don't know. I know it's not a widely agreed convention, but what it "typical" is hard to assess. I think double-open is more commonly used in modern presentations, but the only real way to know would be to do a survey and I don't think the topic merits that. From a technical point of view, double-open is clearly preferable as it removes a special case with no technical down-side. -- 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 | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2022-05-10 03:46 -0700 |
| Message-ID | <adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com> |
| In reply to | #50184 |
On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: > olcott <No...@NoWhere.com> writes: > > > On 5/9/2022 7:13 PM, Ben wrote: > >> olcott <No...@NoWhere.com> writes: > >> > >>> On 5/9/2022 5:14 PM, Ben wrote: > >>>> olcott <No...@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. > >> > >> None of these authors say what is "conventional". What is certain is > >> that if there were a convention, an author not using that convention > >> should say as much. You'll find, however, that that is not the case. > > > > How would you define conventional? > "the accepted or traditional method of doing something" > > The most typical use is one way unlimited, right? > I don't know. I know it's not a widely agreed convention, but what it > "typical" is hard to assess. I think double-open is more commonly used in > modern presentations, but the only real way to know would be to do a > survey and I don't think the topic merits that. > > From a technical point of view, double-open is clearly preferable as it > removes a special case with no technical down-side. > There's a technical downside if you implement the tape in the obvious way, as a dynamic buffer. Most languages make it quite fast to append characters to the buffer's end. There's usually spare memory there in the system, so the push_back() operation is just a case of incrementing a size field. push_front(), however, generally requires a push_back, followed by a move for the entire buffer. There are ways round this, of course, but you have to know what you are doing, and it's not as easy to write. ,
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-10 12:23 +0100 |
| Message-ID | <874k1xmy1v.fsf@bsb.me.uk> |
| In reply to | #50186 |
Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: >> olcott <No...@NoWhere.com> writes: >> >> > On 5/9/2022 7:13 PM, Ben wrote: >> >> olcott <No...@NoWhere.com> writes: >> >> >> >>> On 5/9/2022 5:14 PM, Ben wrote: >> >>>> olcott <No...@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. >> >> >> >> None of these authors say what is "conventional". What is certain is >> >> that if there were a convention, an author not using that convention >> >> should say as much. You'll find, however, that that is not the case. >> > >> > How would you define conventional? >> >> "the accepted or traditional method of doing something" >> >> > The most typical use is one way unlimited, right? >> >> I don't know. I know it's not a widely agreed convention, but what it >> "typical" is hard to assess. I think double-open is more commonly used in >> modern presentations, but the only real way to know would be to do a >> survey and I don't think the topic merits that. >> >> From a technical point of view, double-open is clearly preferable as it >> removes a special case with no technical down-side. >> > There's a technical downside if you implement the tape in the obvious way, > as a dynamic buffer. Most languages make it quite fast to append characters > to the buffer's end. I meant for the theory of such machines. It's the theory and the theorems that will dictate which style an authors chooses and there's no down-side in that context. > There's usually spare memory there in the system, so > the push_back() operation is just a case of incrementing a size field. If you do the resizing right, the same is true of push_front(). > push_front(), however, generally requires a push_back, followed by a move > for the entire buffer. Every now and then, your realloc will need an extra move, but that's a cost that will be amortised if you do the usual exponential resizing. > There are ways round this, of course, but you have to know what you > are doing, and it's not as easy to write. Gosh, you have a low opinion of what's generally understood! Maybe I have too high an opinion, but growing a buffer at one or other or even both ends seems to me to be utterly trivial. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-10 06:53 -0500 |
| Message-ID | <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50187 |
On 5/10/2022 6:23 AM, Ben wrote: > Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > >> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: >>> olcott <No...@NoWhere.com> writes: >>> >>>> On 5/9/2022 7:13 PM, Ben wrote: >>>>> olcott <No...@NoWhere.com> writes: >>>>> >>>>>> On 5/9/2022 5:14 PM, Ben wrote: >>>>>>> olcott <No...@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. >>>>> >>>>> None of these authors say what is "conventional". What is certain is >>>>> that if there were a convention, an author not using that convention >>>>> should say as much. You'll find, however, that that is not the case. >>>> >>>> How would you define conventional? >>> >>> "the accepted or traditional method of doing something" >>> >>>> The most typical use is one way unlimited, right? >>> >>> I don't know. I know it's not a widely agreed convention, but what it >>> "typical" is hard to assess. I think double-open is more commonly used in >>> modern presentations, but the only real way to know would be to do a >>> survey and I don't think the topic merits that. >>> >>> From a technical point of view, double-open is clearly preferable as it >>> removes a special case with no technical down-side. >>> >> There's a technical downside if you implement the tape in the obvious way, >> as a dynamic buffer. Most languages make it quite fast to append characters >> to the buffer's end. > > I meant for the theory of such machines. It's the theory and the > theorems that will dictate which style an authors chooses and there's no > down-side in that context. > >> There's usually spare memory there in the system, so >> the push_back() operation is just a case of incrementing a size field. > > If you do the resizing right, the same is true of push_front(). > >> push_front(), however, generally requires a push_back, followed by a move >> for the entire buffer. > > Every now and then, your realloc will need an extra move, but that's a > cost that will be amortised if you do the usual exponential resizing. > >> There are ways round this, of course, but you have to know what you >> are doing, and it's not as easy to write. > > Gosh, you have a low opinion of what's generally understood! Maybe I > have too high an opinion, but growing a buffer at one or other or even > both ends seems to me to be utterly trivial. > https://en.cppreference.com/w/cpp/container/deque push_back adds an element to the end push_front inserts an element to the beginning -- 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-10 08:01 -0400 |
| Message-ID | <SuseK.34$w1W1.2@fx47.iad> |
| In reply to | #50188 |
On 5/10/22 7:53 AM, olcott wrote: > On 5/10/2022 6:23 AM, Ben wrote: >> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >> >>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: >>>> olcott <No...@NoWhere.com> writes: >>>> >>>>> On 5/9/2022 7:13 PM, Ben wrote: >>>>>> olcott <No...@NoWhere.com> writes: >>>>>> >>>>>>> On 5/9/2022 5:14 PM, Ben wrote: >>>>>>>> olcott <No...@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. >>>>>> >>>>>> None of these authors say what is "conventional". What is certain is >>>>>> that if there were a convention, an author not using that convention >>>>>> should say as much. You'll find, however, that that is not the case. >>>>> >>>>> How would you define conventional? >>>> >>>> "the accepted or traditional method of doing something" >>>> >>>>> The most typical use is one way unlimited, right? >>>> >>>> I don't know. I know it's not a widely agreed convention, but what it >>>> "typical" is hard to assess. I think double-open is more commonly >>>> used in >>>> modern presentations, but the only real way to know would be to do a >>>> survey and I don't think the topic merits that. >>>> >>>> From a technical point of view, double-open is clearly preferable >>>> as it >>>> removes a special case with no technical down-side. >>>> >>> There's a technical downside if you implement the tape in the obvious >>> way, >>> as a dynamic buffer. Most languages make it quite fast to append >>> characters >>> to the buffer's end. >> >> I meant for the theory of such machines. It's the theory and the >> theorems that will dictate which style an authors chooses and there's no >> down-side in that context. >> >>> There's usually spare memory there in the system, so >>> the push_back() operation is just a case of incrementing a size field. >> >> If you do the resizing right, the same is true of push_front(). >> >>> push_front(), however, generally requires a push_back, followed by a >>> move >>> for the entire buffer. >> >> Every now and then, your realloc will need an extra move, but that's a >> cost that will be amortised if you do the usual exponential resizing. >> >>> There are ways round this, of course, but you have to know what you >>> are doing, and it's not as easy to write. >> >> Gosh, you have a low opinion of what's generally understood! Maybe I >> have too high an opinion, but growing a buffer at one or other or even >> both ends seems to me to be utterly trivial. >> > > https://en.cppreference.com/w/cpp/container/deque > push_back adds an element to the end > push_front inserts an element to the beginning > Yes, but they are arguing about what works efficiently. deque is designed for this, so both are likely reasonably efficient, though all extentions that need a realloc to the front will need a move, while some realloction to the end won't. Note, I think some people are still thinking about string, which generally doesn't preallocate extra space to the front of the string (because push_front isn't a common operation) which deque almost certainly does (would need to see if required by complexity specifications).
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-10 16:41 +0100 |
| Message-ID | <87sfphl7iv.fsf@bsb.me.uk> |
| In reply to | #50188 |
olcott <NoOne@NoWhere.com> writes: > On 5/10/2022 6:23 AM, Ben wrote: >> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >> >>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: >>>> olcott <No...@NoWhere.com> writes: >>>> >>>>> On 5/9/2022 7:13 PM, Ben wrote: >>>>>> olcott <No...@NoWhere.com> writes: >>>>>> >>>>>>> On 5/9/2022 5:14 PM, Ben wrote: >>>>>>>> olcott <No...@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. >>>>>> >>>>>> None of these authors say what is "conventional". What is certain is >>>>>> that if there were a convention, an author not using that convention >>>>>> should say as much. You'll find, however, that that is not the case. >>>>> >>>>> How would you define conventional? >>>> >>>> "the accepted or traditional method of doing something" >>>> >>>>> The most typical use is one way unlimited, right? >>>> >>>> I don't know. I know it's not a widely agreed convention, but what it >>>> "typical" is hard to assess. I think double-open is more commonly used in >>>> modern presentations, but the only real way to know would be to do a >>>> survey and I don't think the topic merits that. >>>> >>>> From a technical point of view, double-open is clearly preferable as it >>>> removes a special case with no technical down-side. >>>> >>> There's a technical downside if you implement the tape in the obvious way, >>> as a dynamic buffer. Most languages make it quite fast to append characters >>> to the buffer's end. >> I meant for the theory of such machines. It's the theory and the >> theorems that will dictate which style an authors chooses and there's no >> down-side in that context. >> >>> There's usually spare memory there in the system, so >>> the push_back() operation is just a case of incrementing a size field. >> If you do the resizing right, the same is true of push_front(). >> >>> push_front(), however, generally requires a push_back, followed by a move >>> for the entire buffer. >> Every now and then, your realloc will need an extra move, but that's a >> cost that will be amortised if you do the usual exponential resizing. >> >>> There are ways round this, of course, but you have to know what you >>> are doing, and it's not as easy to write. >> >> Gosh, you have a low opinion of what's generally understood! Maybe I >> have too high an opinion, but growing a buffer at one or other or even >> both ends seems to me to be utterly trivial. > > https://en.cppreference.com/w/cpp/container/deque > push_back adds an element to the end > push_front inserts an element to the beginning I think everyone here knows that. Using std::deque was suggested before (by Jeff I think), but at nearly 200 million steps a second, I didn't think there was much room for a speed-up. I've just tried it, and using std::deque rather than std::string slows my implementation down to 106 million steps a second, and it doesn't simplify the logic at all. In fact, the few places where you really want a string get a bit more fiddly. Mind you, the speed is almost irrelevant unless you are hunting for BB champions. -- 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 | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2022-05-10 11:56 -0600 |
| Message-ID | <t5e902$61j$1@dont-email.me> |
| In reply to | #50197 |
On 5/10/2022 9:41 AM, Ben wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 5/10/2022 6:23 AM, Ben wrote: >>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >>> >>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: >>>>> olcott <No...@NoWhere.com> writes: >>>>> >>>>>> On 5/9/2022 7:13 PM, Ben wrote: >>>>>>> olcott <No...@NoWhere.com> writes: >>>>>>> >>>>>>>> On 5/9/2022 5:14 PM, Ben wrote: >>>>>>>>> olcott <No...@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. >>>>>>> >>>>>>> None of these authors say what is "conventional". What is certain is >>>>>>> that if there were a convention, an author not using that convention >>>>>>> should say as much. You'll find, however, that that is not the case. >>>>>> >>>>>> How would you define conventional? >>>>> >>>>> "the accepted or traditional method of doing something" >>>>> >>>>>> The most typical use is one way unlimited, right? >>>>> >>>>> I don't know. I know it's not a widely agreed convention, but what it >>>>> "typical" is hard to assess. I think double-open is more commonly used in >>>>> modern presentations, but the only real way to know would be to do a >>>>> survey and I don't think the topic merits that. >>>>> >>>>> From a technical point of view, double-open is clearly preferable as it >>>>> removes a special case with no technical down-side. >>>>> >>>> There's a technical downside if you implement the tape in the obvious way, >>>> as a dynamic buffer. Most languages make it quite fast to append characters >>>> to the buffer's end. >>> I meant for the theory of such machines. It's the theory and the >>> theorems that will dictate which style an authors chooses and there's no >>> down-side in that context. >>> >>>> There's usually spare memory there in the system, so >>>> the push_back() operation is just a case of incrementing a size field. >>> If you do the resizing right, the same is true of push_front(). >>> >>>> push_front(), however, generally requires a push_back, followed by a move >>>> for the entire buffer. >>> Every now and then, your realloc will need an extra move, but that's a >>> cost that will be amortised if you do the usual exponential resizing. >>> >>>> There are ways round this, of course, but you have to know what you >>>> are doing, and it's not as easy to write. >>> >>> Gosh, you have a low opinion of what's generally understood! Maybe I >>> have too high an opinion, but growing a buffer at one or other or even >>> both ends seems to me to be utterly trivial. >> >> https://en.cppreference.com/w/cpp/container/deque >> push_back adds an element to the end >> push_front inserts an element to the beginning > > I think everyone here knows that. > > Using std::deque was suggested before (by Jeff I think), but at nearly > 200 million steps a second, I didn't think there was much room for a > speed-up. > > I've just tried it, and using std::deque rather than std::string slows > my implementation down to 106 million steps a second, and it doesn't > simplify the logic at all. In fact, the few places where you really > want a string get a bit more fiddly. > > Mind you, the speed is almost irrelevant unless you are hunting for BB > champions. One possibility is to use a linked list where each node contains a character, a pointer to the following node, and a pointer to the previous node. Since the TM can only move one tape square per state transition, the cache will do a good job of speeding things up. Of course storage per character is more and that will slow things down. Another way to make tape storage almost all characters is to allocate a block (page sized) at a time with one block initially. A block is allocated each time you are about to go off either the front or back end and is linked. The cache hit ratio is extremely good and only a tiny fraction less then using a big array. It wins, however, when growing an array would cause you to move it. -- Jeff Barnett
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-10 19:43 -0500 |
| Message-ID | <8vydnYsTy7kxm-b_nZ2dnUU7_8xh4p2d@giganews.com> |
| In reply to | #50202 |
On 5/10/2022 12:56 PM, Jeff Barnett wrote: > On 5/10/2022 9:41 AM, Ben wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> On 5/10/2022 6:23 AM, Ben wrote: >>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >>>> >>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: >>>>>> olcott <No...@NoWhere.com> writes: >>>>>> >>>>>>> On 5/9/2022 7:13 PM, Ben wrote: >>>>>>>> olcott <No...@NoWhere.com> writes: >>>>>>>> >>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote: >>>>>>>>>> olcott <No...@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. >>>>>>>> >>>>>>>> None of these authors say what is "conventional". What is >>>>>>>> certain is >>>>>>>> that if there were a convention, an author not using that >>>>>>>> convention >>>>>>>> should say as much. You'll find, however, that that is not the >>>>>>>> case. >>>>>>> >>>>>>> How would you define conventional? >>>>>> >>>>>> "the accepted or traditional method of doing something" >>>>>> >>>>>>> The most typical use is one way unlimited, right? >>>>>> >>>>>> I don't know. I know it's not a widely agreed convention, but what it >>>>>> "typical" is hard to assess. I think double-open is more commonly >>>>>> used in >>>>>> modern presentations, but the only real way to know would be to do a >>>>>> survey and I don't think the topic merits that. >>>>>> >>>>>> From a technical point of view, double-open is clearly >>>>>> preferable as it >>>>>> removes a special case with no technical down-side. >>>>>> >>>>> There's a technical downside if you implement the tape in the >>>>> obvious way, >>>>> as a dynamic buffer. Most languages make it quite fast to append >>>>> characters >>>>> to the buffer's end. >>>> I meant for the theory of such machines. It's the theory and the >>>> theorems that will dictate which style an authors chooses and >>>> there's no >>>> down-side in that context. >>>> >>>>> There's usually spare memory there in the system, so >>>>> the push_back() operation is just a case of incrementing a size field. >>>> If you do the resizing right, the same is true of push_front(). >>>> >>>>> push_front(), however, generally requires a push_back, followed by >>>>> a move >>>>> for the entire buffer. >>>> Every now and then, your realloc will need an extra move, but that's a >>>> cost that will be amortised if you do the usual exponential resizing. >>>> >>>>> There are ways round this, of course, but you have to know what you >>>>> are doing, and it's not as easy to write. >>>> >>>> Gosh, you have a low opinion of what's generally understood! Maybe I >>>> have too high an opinion, but growing a buffer at one or other or even >>>> both ends seems to me to be utterly trivial. >>> >>> https://en.cppreference.com/w/cpp/container/deque >>> push_back adds an element to the end >>> push_front inserts an element to the beginning >> >> I think everyone here knows that. >> >> Using std::deque was suggested before (by Jeff I think), but at nearly >> 200 million steps a second, I didn't think there was much room for a >> speed-up. >> >> I've just tried it, and using std::deque rather than std::string slows >> my implementation down to 106 million steps a second, and it doesn't >> simplify the logic at all. In fact, the few places where you really >> want a string get a bit more fiddly. >> >> Mind you, the speed is almost irrelevant unless you are hunting for BB >> champions. > > One possibility is to use a linked list where each node contains a > character, a pointer to the following node, and a pointer to the > previous node. Since the TM can only move one tape square per state > transition, the > cache will do a good job of speeding things up. Of > course storage per character is more and that will slow things down. > > Another way to make tape storage almost all characters is to allocate a > block (page sized) at a time with one block initially. A block is > allocated each time you are about to go off either the front or back end > and is linked. The cache hit ratio is extremely good and only a tiny > fraction less then using a big array. It wins, however, when growing an > array would cause you to move it. David kleinecke's solution 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. I consider it an optimal solution and the one that I am implementing. -- 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-10 20:49 -0600 |
| Message-ID | <t5f87p$n3e$1@dont-email.me> |
| In reply to | #50214 |
On 5/10/2022 6:43 PM, olcott wrote: > On 5/10/2022 12:56 PM, Jeff Barnett wrote: >> On 5/10/2022 9:41 AM, Ben wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> On 5/10/2022 6:23 AM, Ben wrote: >>>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >>>>> >>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: >>>>>>> olcott <No...@NoWhere.com> writes: >>>>>>> >>>>>>>> On 5/9/2022 7:13 PM, Ben wrote: >>>>>>>>> olcott <No...@NoWhere.com> writes: >>>>>>>>> >>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote: >>>>>>>>>>> olcott <No...@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. >>>>>>>>> >>>>>>>>> None of these authors say what is "conventional". What is >>>>>>>>> certain is >>>>>>>>> that if there were a convention, an author not using that >>>>>>>>> convention >>>>>>>>> should say as much. You'll find, however, that that is not the >>>>>>>>> case. >>>>>>>> >>>>>>>> How would you define conventional? >>>>>>> >>>>>>> "the accepted or traditional method of doing something" >>>>>>> >>>>>>>> The most typical use is one way unlimited, right? >>>>>>> >>>>>>> I don't know. I know it's not a widely agreed convention, but >>>>>>> what it >>>>>>> "typical" is hard to assess. I think double-open is more commonly >>>>>>> used in >>>>>>> modern presentations, but the only real way to know would be to do a >>>>>>> survey and I don't think the topic merits that. >>>>>>> >>>>>>> From a technical point of view, double-open is clearly >>>>>>> preferable as it >>>>>>> removes a special case with no technical down-side. >>>>>>> >>>>>> There's a technical downside if you implement the tape in the >>>>>> obvious way, >>>>>> as a dynamic buffer. Most languages make it quite fast to append >>>>>> characters >>>>>> to the buffer's end. >>>>> I meant for the theory of such machines. It's the theory and the >>>>> theorems that will dictate which style an authors chooses and >>>>> there's no >>>>> down-side in that context. >>>>> >>>>>> There's usually spare memory there in the system, so >>>>>> the push_back() operation is just a case of incrementing a size >>>>>> field. >>>>> If you do the resizing right, the same is true of push_front(). >>>>> >>>>>> push_front(), however, generally requires a push_back, followed by >>>>>> a move >>>>>> for the entire buffer. >>>>> Every now and then, your realloc will need an extra move, but that's a >>>>> cost that will be amortised if you do the usual exponential resizing. >>>>> >>>>>> There are ways round this, of course, but you have to know what you >>>>>> are doing, and it's not as easy to write. >>>>> >>>>> Gosh, you have a low opinion of what's generally understood! Maybe I >>>>> have too high an opinion, but growing a buffer at one or other or even >>>>> both ends seems to me to be utterly trivial. >>>> >>>> https://en.cppreference.com/w/cpp/container/deque >>>> push_back adds an element to the end >>>> push_front inserts an element to the beginning >>> >>> I think everyone here knows that. >>> >>> Using std::deque was suggested before (by Jeff I think), but at nearly >>> 200 million steps a second, I didn't think there was much room for a >>> speed-up. >>> >>> I've just tried it, and using std::deque rather than std::string slows >>> my implementation down to 106 million steps a second, and it doesn't >>> simplify the logic at all. In fact, the few places where you really >>> want a string get a bit more fiddly. >>> >>> Mind you, the speed is almost irrelevant unless you are hunting for BB >>> champions. >> >> One possibility is to use a linked list where each node contains a >> character, a pointer to the following node, and a pointer to the >> previous node. Since the TM can only move one tape square per state >> transition, the > cache will do a good job of speeding things up. Of >> course storage per character is more and that will slow things down. >> >> Another way to make tape storage almost all characters is to allocate >> a block (page sized) at a time with one block initially. A block is >> allocated each time you are about to go off either the front or back >> end and is linked. The cache hit ratio is extremely good and only a >> tiny fraction less then using a big array. It wins, however, when >> growing an array would cause you to move it. > > > David kleinecke's solution 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. > > I consider it an optimal solution and the one that I am implementing. I'm not sure what any of what you said has to do with what I wrote. All I assume from the runtime is a way of occasionally allocating some multi page-sized blocks. That and a few lines (a dozen or so) of code will handle the allocation and usage: fairly trivial and quick stuff. -- Jeff Barnett
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2022-05-10 19:01 +0100 |
| Message-ID | <20220510190118.00006b59@reddwarf.jmc> |
| In reply to | #50197 |
On Tue, 10 May 2022 16:41:28 +0100 Ben <ben.usenet@bsb.me.uk> wrote: > olcott <NoOne@NoWhere.com> writes: > > > On 5/10/2022 6:23 AM, Ben wrote: > >> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > >> > >>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: > >>>> olcott <No...@NoWhere.com> writes: > >>>> > >>>>> On 5/9/2022 7:13 PM, Ben wrote: > >>>>>> olcott <No...@NoWhere.com> writes: > >>>>>> > >>>>>>> On 5/9/2022 5:14 PM, Ben wrote: > >>>>>>>> olcott <No...@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. > >>>>>> > >>>>>> None of these authors say what is "conventional". What is > >>>>>> certain is that if there were a convention, an author not > >>>>>> using that convention should say as much. You'll find, > >>>>>> however, that that is not the case. > >>>>> > >>>>> How would you define conventional? > >>>> > >>>> "the accepted or traditional method of doing something" > >>>> > >>>>> The most typical use is one way unlimited, right? > >>>> > >>>> I don't know. I know it's not a widely agreed convention, but > >>>> what it "typical" is hard to assess. I think double-open is more > >>>> commonly used in modern presentations, but the only real way to > >>>> know would be to do a survey and I don't think the topic merits > >>>> that. > >>>> > >>>> From a technical point of view, double-open is clearly > >>>> preferable as it removes a special case with no technical > >>>> down-side. > >>> There's a technical downside if you implement the tape in the > >>> obvious way, as a dynamic buffer. Most languages make it quite > >>> fast to append characters to the buffer's end. > >> I meant for the theory of such machines. It's the theory and the > >> theorems that will dictate which style an authors chooses and > >> there's no down-side in that context. > >> > >>> There's usually spare memory there in the system, so > >>> the push_back() operation is just a case of incrementing a size > >>> field. > >> If you do the resizing right, the same is true of push_front(). > >> > >>> push_front(), however, generally requires a push_back, followed > >>> by a move for the entire buffer. > >> Every now and then, your realloc will need an extra move, but > >> that's a cost that will be amortised if you do the usual > >> exponential resizing. > >>> There are ways round this, of course, but you have to know what > >>> you are doing, and it's not as easy to write. > >> > >> Gosh, you have a low opinion of what's generally understood! > >> Maybe I have too high an opinion, but growing a buffer at one or > >> other or even both ends seems to me to be utterly trivial. > > > > https://en.cppreference.com/w/cpp/container/deque > > push_back adds an element to the end > > push_front inserts an element to the beginning > > I think everyone here knows that. > > Using std::deque was suggested before (by Jeff I think), but at nearly > 200 million steps a second, I didn't think there was much room for a > speed-up. > > I've just tried it, and using std::deque rather than std::string slows > my implementation down to 106 million steps a second, and it doesn't > simplify the logic at all. In fact, the few places where you really > want a string get a bit more fiddly. > > Mind you, the speed is almost irrelevant unless you are hunting for BB > champions. std::string (or std::vector) will likely win for small N and std::deque for large N as far as push_front is concerned. /Flibble
[toc] | [prev] | [next] | [standalone]
| From | "dklei...@gmail.com" <dkleinecke@gmail.com> |
|---|---|
| Date | 2022-05-10 11:59 -0700 |
| Message-ID | <f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com> |
| In reply to | #50203 |
On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote: > On Tue, 10 May 2022 16:41:28 +0100 > Ben <ben.u...@bsb.me.uk> wrote: > > > olcott <No...@NoWhere.com> writes: > > > > > On 5/10/2022 6:23 AM, Ben wrote: > > >> Malcolm McLean <malcolm.ar...@gmail.com> writes: > > >> > > >>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: > > >>>> olcott <No...@NoWhere.com> writes: > > >>>> > > >>>>> On 5/9/2022 7:13 PM, Ben wrote: > > >>>>>> olcott <No...@NoWhere.com> writes: > > >>>>>> > > >>>>>>> On 5/9/2022 5:14 PM, Ben wrote: > > >>>>>>>> olcott <No...@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. > > >>>>>> > > >>>>>> None of these authors say what is "conventional". What is > > >>>>>> certain is that if there were a convention, an author not > > >>>>>> using that convention should say as much. You'll find, > > >>>>>> however, that that is not the case. > > >>>>> > > >>>>> How would you define conventional? > > >>>> > > >>>> "the accepted or traditional method of doing something" > > >>>> > > >>>>> The most typical use is one way unlimited, right? > > >>>> > > >>>> I don't know. I know it's not a widely agreed convention, but > > >>>> what it "typical" is hard to assess. I think double-open is more > > >>>> commonly used in modern presentations, but the only real way to > > >>>> know would be to do a survey and I don't think the topic merits > > >>>> that. > > >>>> > > >>>> From a technical point of view, double-open is clearly > > >>>> preferable as it removes a special case with no technical > > >>>> down-side. > > >>> There's a technical downside if you implement the tape in the > > >>> obvious way, as a dynamic buffer. Most languages make it quite > > >>> fast to append characters to the buffer's end. > > >> I meant for the theory of such machines. It's the theory and the > > >> theorems that will dictate which style an authors chooses and > > >> there's no down-side in that context. > > >> > > >>> There's usually spare memory there in the system, so > > >>> the push_back() operation is just a case of incrementing a size > > >>> field. > > >> If you do the resizing right, the same is true of push_front(). > > >> > > >>> push_front(), however, generally requires a push_back, followed > > >>> by a move for the entire buffer. > > >> Every now and then, your realloc will need an extra move, but > > >> that's a cost that will be amortised if you do the usual > > >> exponential resizing. > > >>> There are ways round this, of course, but you have to know what > > >>> you are doing, and it's not as easy to write. > > >> > > >> Gosh, you have a low opinion of what's generally understood! > > >> Maybe I have too high an opinion, but growing a buffer at one or > > >> other or even both ends seems to me to be utterly trivial. > > > > > > https://en.cppreference.com/w/cpp/container/deque > > > push_back adds an element to the end > > > push_front inserts an element to the beginning > > > > I think everyone here knows that. > > > > Using std::deque was suggested before (by Jeff I think), but at nearly > > 200 million steps a second, I didn't think there was much room for a > > speed-up. > > > > I've just tried it, and using std::deque rather than std::string slows > > my implementation down to 106 million steps a second, and it doesn't > > simplify the logic at all. In fact, the few places where you really > > want a string get a bit more fiddly. > > > > Mind you, the speed is almost irrelevant unless you are hunting for BB > > champions. > std::string (or std::vector) will likely win for small N and std::deque > for large N as far as push_front is concerned. > > /Flibble If you are not actually implementing a machine replacing the tape by a pair of stacks is attractive. Actually you replace the tape by three things - two stacks (called for example left and right) and a single focus cell. But none of this is really needed. We don't really need TM's for anything practical.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-10 19:04 -0500 |
| Message-ID | <ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50207 |
On 5/10/2022 1:59 PM, dklei...@gmail.com wrote: > On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote: >> On Tue, 10 May 2022 16:41:28 +0100 >> Ben <ben.u...@bsb.me.uk> wrote: >> >>> olcott <No...@NoWhere.com> writes: >>> >>>> On 5/10/2022 6:23 AM, Ben wrote: >>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes: >>>>> >>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: >>>>>>> olcott <No...@NoWhere.com> writes: >>>>>>> >>>>>>>> On 5/9/2022 7:13 PM, Ben wrote: >>>>>>>>> olcott <No...@NoWhere.com> writes: >>>>>>>>> >>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote: >>>>>>>>>>> olcott <No...@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. >>>>>>>>> >>>>>>>>> None of these authors say what is "conventional". What is >>>>>>>>> certain is that if there were a convention, an author not >>>>>>>>> using that convention should say as much. You'll find, >>>>>>>>> however, that that is not the case. >>>>>>>> >>>>>>>> How would you define conventional? >>>>>>> >>>>>>> "the accepted or traditional method of doing something" >>>>>>> >>>>>>>> The most typical use is one way unlimited, right? >>>>>>> >>>>>>> I don't know. I know it's not a widely agreed convention, but >>>>>>> what it "typical" is hard to assess. I think double-open is more >>>>>>> commonly used in modern presentations, but the only real way to >>>>>>> know would be to do a survey and I don't think the topic merits >>>>>>> that. >>>>>>> >>>>>>> From a technical point of view, double-open is clearly >>>>>>> preferable as it removes a special case with no technical >>>>>>> down-side. >>>>>> There's a technical downside if you implement the tape in the >>>>>> obvious way, as a dynamic buffer. Most languages make it quite >>>>>> fast to append characters to the buffer's end. >>>>> I meant for the theory of such machines. It's the theory and the >>>>> theorems that will dictate which style an authors chooses and >>>>> there's no down-side in that context. >>>>> >>>>>> There's usually spare memory there in the system, so >>>>>> the push_back() operation is just a case of incrementing a size >>>>>> field. >>>>> If you do the resizing right, the same is true of push_front(). >>>>> >>>>>> push_front(), however, generally requires a push_back, followed >>>>>> by a move for the entire buffer. >>>>> Every now and then, your realloc will need an extra move, but >>>>> that's a cost that will be amortised if you do the usual >>>>> exponential resizing. >>>>>> There are ways round this, of course, but you have to know what >>>>>> you are doing, and it's not as easy to write. >>>>> >>>>> Gosh, you have a low opinion of what's generally understood! >>>>> Maybe I have too high an opinion, but growing a buffer at one or >>>>> other or even both ends seems to me to be utterly trivial. >>>> >>>> https://en.cppreference.com/w/cpp/container/deque >>>> push_back adds an element to the end >>>> push_front inserts an element to the beginning >>> >>> I think everyone here knows that. >>> >>> Using std::deque was suggested before (by Jeff I think), but at nearly >>> 200 million steps a second, I didn't think there was much room for a >>> speed-up. >>> >>> I've just tried it, and using std::deque rather than std::string slows >>> my implementation down to 106 million steps a second, and it doesn't >>> simplify the logic at all. In fact, the few places where you really >>> want a string get a bit more fiddly. >>> >>> Mind you, the speed is almost irrelevant unless you are hunting for BB >>> champions. >> std::string (or std::vector) will likely win for small N and std::deque >> for large N as far as push_front is concerned. >> >> /Flibble > > If you are not actually implementing a machine replacing the tape by a pair of > stacks is attractive. Actually you replace the tape by three things - two stacks > (called for example left and right) and a single focus cell. > > But none of this is really needed. We don't really need TM's for anything > practical. This is the best idea yet. I spent all day researching this on my cell phone during chemotherapy infusion. I am implemented this idea in code and will post it as another reply to your message. -- 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-11 01:42 +0100 |
| Message-ID | <87bkw4lx13.fsf@bsb.me.uk> |
| In reply to | #50210 |
olcott <NoOne@NoWhere.com> writes: > On 5/10/2022 1:59 PM, dklei...@gmail.com wrote: >> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote: >>> On Tue, 10 May 2022 16:41:28 +0100 >>> Ben <ben.u...@bsb.me.uk> wrote: >>> >>>> olcott <No...@NoWhere.com> writes: >>>> >>>>> On 5/10/2022 6:23 AM, Ben wrote: >>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes: >>>>>> >>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: >>>>>>>> olcott <No...@NoWhere.com> writes: >>>>>>>> >>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote: >>>>>>>>>> olcott <No...@NoWhere.com> writes: >>>>>>>>>> >>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote: >>>>>>>>>>>> olcott <No...@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. >>>>>>>>>> >>>>>>>>>> None of these authors say what is "conventional". What is >>>>>>>>>> certain is that if there were a convention, an author not >>>>>>>>>> using that convention should say as much. You'll find, >>>>>>>>>> however, that that is not the case. >>>>>>>>> >>>>>>>>> How would you define conventional? >>>>>>>> >>>>>>>> "the accepted or traditional method of doing something" >>>>>>>> >>>>>>>>> The most typical use is one way unlimited, right? >>>>>>>> >>>>>>>> I don't know. I know it's not a widely agreed convention, but >>>>>>>> what it "typical" is hard to assess. I think double-open is more >>>>>>>> commonly used in modern presentations, but the only real way to >>>>>>>> know would be to do a survey and I don't think the topic merits >>>>>>>> that. >>>>>>>> >>>>>>>> From a technical point of view, double-open is clearly >>>>>>>> preferable as it removes a special case with no technical >>>>>>>> down-side. >>>>>>> There's a technical downside if you implement the tape in the >>>>>>> obvious way, as a dynamic buffer. Most languages make it quite >>>>>>> fast to append characters to the buffer's end. >>>>>> I meant for the theory of such machines. It's the theory and the >>>>>> theorems that will dictate which style an authors chooses and >>>>>> there's no down-side in that context. >>>>>> >>>>>>> There's usually spare memory there in the system, so >>>>>>> the push_back() operation is just a case of incrementing a size >>>>>>> field. >>>>>> If you do the resizing right, the same is true of push_front(). >>>>>> >>>>>>> push_front(), however, generally requires a push_back, followed >>>>>>> by a move for the entire buffer. >>>>>> Every now and then, your realloc will need an extra move, but >>>>>> that's a cost that will be amortised if you do the usual >>>>>> exponential resizing. >>>>>>> There are ways round this, of course, but you have to know what >>>>>>> you are doing, and it's not as easy to write. >>>>>> >>>>>> Gosh, you have a low opinion of what's generally understood! >>>>>> Maybe I have too high an opinion, but growing a buffer at one or >>>>>> other or even both ends seems to me to be utterly trivial. >>>>> >>>>> https://en.cppreference.com/w/cpp/container/deque >>>>> push_back adds an element to the end >>>>> push_front inserts an element to the beginning >>>> >>>> I think everyone here knows that. >>>> >>>> Using std::deque was suggested before (by Jeff I think), but at nearly >>>> 200 million steps a second, I didn't think there was much room for a >>>> speed-up. >>>> >>>> I've just tried it, and using std::deque rather than std::string slows >>>> my implementation down to 106 million steps a second, and it doesn't >>>> simplify the logic at all. In fact, the few places where you really >>>> want a string get a bit more fiddly. >>>> >>>> Mind you, the speed is almost irrelevant unless you are hunting for BB >>>> champions. >>> std::string (or std::vector) will likely win for small N and std::deque >>> for large N as far as push_front is concerned. >>> >>> /Flibble >> If you are not actually implementing a machine replacing the tape by >> a pair of stacks is attractive. Actually you replace the tape by >> three things - two stacks (called for example left and right) and a >> single focus cell. I've tried both (two stacks and two stacks and a cell) and I think the extra cell just makes it a bit fussy. If you have an array of two stacks: stack<symbol> tape[2]; and 'dir' is the move direction as 0 or 1, then tape[dir].push(tape[!dir].pop()) is the move operation. Reading the tape cell is done just once per step, so tape[0].top() is not going to be expensive. >> But none of this is really needed. We don't really need TM's for anything >> practical. > > This is the best idea yet. I spent all day researching this > on my cell phone during chemotherapy infusion. > > I am implemented this idea in code and will post it as another > reply to your message. My Haskell TM interpreter did it this way with a pair of strings (Haskell strings are essentially stacks). But I've lost the code. I might have time to re-create it. -- 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 20:12 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50213 |
On 5/10/2022 7:42 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
>>> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>>>> On Tue, 10 May 2022 16:41:28 +0100
>>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>>
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>
>>>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>>>> olcott <No...@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.
>>>>>>>>>>>
>>>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>>>> however, that that is not the case.
>>>>>>>>>>
>>>>>>>>>> How would you define conventional?
>>>>>>>>>
>>>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>>>
>>>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>>>
>>>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>>>> that.
>>>>>>>>>
>>>>>>>>> From a technical point of view, double-open is clearly
>>>>>>>>> preferable as it removes a special case with no technical
>>>>>>>>> down-side.
>>>>>>>> There's a technical downside if you implement the tape in the
>>>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>>>> fast to append characters to the buffer's end.
>>>>>>> I meant for the theory of such machines. It's the theory and the
>>>>>>> theorems that will dictate which style an authors chooses and
>>>>>>> there's no down-side in that context.
>>>>>>>
>>>>>>>> There's usually spare memory there in the system, so
>>>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>>>> field.
>>>>>>> If you do the resizing right, the same is true of push_front().
>>>>>>>
>>>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>>>> by a move for the entire buffer.
>>>>>>> Every now and then, your realloc will need an extra move, but
>>>>>>> that's a cost that will be amortised if you do the usual
>>>>>>> exponential resizing.
>>>>>>>> There are ways round this, of course, but you have to know what
>>>>>>>> you are doing, and it's not as easy to write.
>>>>>>>
>>>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>>>> other or even both ends seems to me to be utterly trivial.
>>>>>>
>>>>>> https://en.cppreference.com/w/cpp/container/deque
>>>>>> push_back adds an element to the end
>>>>>> push_front inserts an element to the beginning
>>>>>
>>>>> I think everyone here knows that.
>>>>>
>>>>> Using std::deque was suggested before (by Jeff I think), but at nearly
>>>>> 200 million steps a second, I didn't think there was much room for a
>>>>> speed-up.
>>>>>
>>>>> I've just tried it, and using std::deque rather than std::string slows
>>>>> my implementation down to 106 million steps a second, and it doesn't
>>>>> simplify the logic at all. In fact, the few places where you really
>>>>> want a string get a bit more fiddly.
>>>>>
>>>>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>>>>> champions.
>>>> std::string (or std::vector) will likely win for small N and std::deque
>>>> for large N as far as push_front is concerned.
>>>>
>>>> /Flibble
>>> If you are not actually implementing a machine replacing the tape by
>>> a pair of stacks is attractive. Actually you replace the tape by
>>> three things - two stacks (called for example left and right) and a
>>> single focus cell.
>
> I've tried both (two stacks and two stacks and a cell) and I think the
> extra cell just makes it a bit fussy.
>
std::vector <is> essentially a stack.
struct Tape
{
unsigned int Tape_Head;
std::vector<unsigned char> Left;
std::vector<unsigned char> Right;
unsigned int move_left();
unsigned int move_right();
};
Tape_Head is mapped to its location in Left or Right.
I am still working out the details of this part.
--
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 | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2022-05-11 03:05 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk> |
| In reply to | #50215 |
On 11/05/2022 02:12, olcott wrote:
> On 5/10/2022 7:42 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
>>>> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>>>>> On Tue, 10 May 2022 16:41:28 +0100
>>>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>>>
>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>
>>>>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>>
>>>>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>
>>>>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>>>>> olcott <No...@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.
>>>>>>>>>>>>
>>>>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>>>>> however, that that is not the case.
>>>>>>>>>>>
>>>>>>>>>>> How would you define conventional?
>>>>>>>>>>
>>>>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>>>>
>>>>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>>>>
>>>>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>>>>> that.
>>>>>>>>>>
>>>>>>>>>> From a technical point of view, double-open is clearly
>>>>>>>>>> preferable as it removes a special case with no technical
>>>>>>>>>> down-side.
>>>>>>>>> There's a technical downside if you implement the tape in the
>>>>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>>>>> fast to append characters to the buffer's end.
>>>>>>>> I meant for the theory of such machines. It's the theory and the
>>>>>>>> theorems that will dictate which style an authors chooses and
>>>>>>>> there's no down-side in that context.
>>>>>>>>
>>>>>>>>> There's usually spare memory there in the system, so
>>>>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>>>>> field.
>>>>>>>> If you do the resizing right, the same is true of push_front().
>>>>>>>>
>>>>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>>>>> by a move for the entire buffer.
>>>>>>>> Every now and then, your realloc will need an extra move, but
>>>>>>>> that's a cost that will be amortised if you do the usual
>>>>>>>> exponential resizing.
>>>>>>>>> There are ways round this, of course, but you have to know what
>>>>>>>>> you are doing, and it's not as easy to write.
>>>>>>>>
>>>>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>>>>> other or even both ends seems to me to be utterly trivial.
>>>>>>>
>>>>>>> https://en.cppreference.com/w/cpp/container/deque
>>>>>>> push_back adds an element to the end
>>>>>>> push_front inserts an element to the beginning
>>>>>>
>>>>>> I think everyone here knows that.
>>>>>>
>>>>>> Using std::deque was suggested before (by Jeff I think), but at nearly
>>>>>> 200 million steps a second, I didn't think there was much room for a
>>>>>> speed-up.
>>>>>>
>>>>>> I've just tried it, and using std::deque rather than std::string slows
>>>>>> my implementation down to 106 million steps a second, and it doesn't
>>>>>> simplify the logic at all. In fact, the few places where you really
>>>>>> want a string get a bit more fiddly.
>>>>>>
>>>>>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>>>>>> champions.
>>>>> std::string (or std::vector) will likely win for small N and std::deque
>>>>> for large N as far as push_front is concerned.
>>>>>
>>>>> /Flibble
>>>> If you are not actually implementing a machine replacing the tape by
>>>> a pair of stacks is attractive. Actually you replace the tape by
>>>> three things - two stacks (called for example left and right) and a
>>>> single focus cell.
>>
>> I've tried both (two stacks and two stacks and a cell) and I think the
>> extra cell just makes it a bit fussy.
>>
>
> std::vector <is> essentially a stack.
>
> struct Tape
> {
> unsigned int Tape_Head;
> std::vector<unsigned char> Left;
> std::vector<unsigned char> Right;
> unsigned int move_left();
> unsigned int move_right();
> };
>
> Tape_Head is mapped to its location in Left or Right.
> I am still working out the details of this part.
>
I think you've misunderstood DK's and Ben's approaches. I think what you're suggesting is that Left
handles all the "negative" tape head positions, and Right all the "positive" ones, while Tape_Head
contains the tape head index (positive or negative) which changes by 1 each time the head moves?
DK and Ben propose two stacks, and with this approach the tape head is effectively always in a fixed
place "in between the two stacks", or (with Ben's) at the top of [say] the left stack. So there is
no Tape_Head index to track.
But what you suggest is quite workable...
I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a
comfortably large chosen page size. (But efficiency really isn't an issue for this task!)
Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-10 21:14 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <Tb2dnQFwPLxohub_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50216 |
On 5/10/2022 9:05 PM, Mike Terry wrote:
> On 11/05/2022 02:12, olcott wrote:
>> On 5/10/2022 7:42 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
>>>>> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>>>>>> On Tue, 10 May 2022 16:41:28 +0100
>>>>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>>>>
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>>>
>>>>>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>>>>>> olcott <No...@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.
>>>>>>>>>>>>>
>>>>>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>>>>>> however, that that is not the case.
>>>>>>>>>>>>
>>>>>>>>>>>> How would you define conventional?
>>>>>>>>>>>
>>>>>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>>>>>
>>>>>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>>>>>
>>>>>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>>>>>> that.
>>>>>>>>>>>
>>>>>>>>>>> From a technical point of view, double-open is clearly
>>>>>>>>>>> preferable as it removes a special case with no technical
>>>>>>>>>>> down-side.
>>>>>>>>>> There's a technical downside if you implement the tape in the
>>>>>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>>>>>> fast to append characters to the buffer's end.
>>>>>>>>> I meant for the theory of such machines. It's the theory and the
>>>>>>>>> theorems that will dictate which style an authors chooses and
>>>>>>>>> there's no down-side in that context.
>>>>>>>>>
>>>>>>>>>> There's usually spare memory there in the system, so
>>>>>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>>>>>> field.
>>>>>>>>> If you do the resizing right, the same is true of push_front().
>>>>>>>>>
>>>>>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>>>>>> by a move for the entire buffer.
>>>>>>>>> Every now and then, your realloc will need an extra move, but
>>>>>>>>> that's a cost that will be amortised if you do the usual
>>>>>>>>> exponential resizing.
>>>>>>>>>> There are ways round this, of course, but you have to know what
>>>>>>>>>> you are doing, and it's not as easy to write.
>>>>>>>>>
>>>>>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>>>>>> other or even both ends seems to me to be utterly trivial.
>>>>>>>>
>>>>>>>> https://en.cppreference.com/w/cpp/container/deque
>>>>>>>> push_back adds an element to the end
>>>>>>>> push_front inserts an element to the beginning
>>>>>>>
>>>>>>> I think everyone here knows that.
>>>>>>>
>>>>>>> Using std::deque was suggested before (by Jeff I think), but at
>>>>>>> nearly
>>>>>>> 200 million steps a second, I didn't think there was much room for a
>>>>>>> speed-up.
>>>>>>>
>>>>>>> I've just tried it, and using std::deque rather than std::string
>>>>>>> slows
>>>>>>> my implementation down to 106 million steps a second, and it doesn't
>>>>>>> simplify the logic at all. In fact, the few places where you really
>>>>>>> want a string get a bit more fiddly.
>>>>>>>
>>>>>>> Mind you, the speed is almost irrelevant unless you are hunting
>>>>>>> for BB
>>>>>>> champions.
>>>>>> std::string (or std::vector) will likely win for small N and
>>>>>> std::deque
>>>>>> for large N as far as push_front is concerned.
>>>>>>
>>>>>> /Flibble
>>>>> If you are not actually implementing a machine replacing the tape by
>>>>> a pair of stacks is attractive. Actually you replace the tape by
>>>>> three things - two stacks (called for example left and right) and a
>>>>> single focus cell.
>>>
>>> I've tried both (two stacks and two stacks and a cell) and I think the
>>> extra cell just makes it a bit fussy.
>>>
>>
>> std::vector <is> essentially a stack.
>>
>> struct Tape
>> {
>> unsigned int Tape_Head;
>> std::vector<unsigned char> Left;
>> std::vector<unsigned char> Right;
>> unsigned int move_left();
>> unsigned int move_right();
>> };
>>
>> Tape_Head is mapped to its location in Left or Right.
>> I am still working out the details of this part.
>>
>
> I think you've misunderstood DK's and Ben's approaches. I think what
> you're suggesting is that Left handles all the "negative" tape head
> positions, and Right all the "positive" ones, while Tape_Head contains
> the tape head index (positive or negative) which changes by 1 each time
> the head moves?
>
Not in the least little bit. Please wait until you see my full
implementation before passing judgement. David's solution is optimal.
> DK and Ben propose two stacks, and with this approach the tape head is
> effectively always in a fixed place "in between the two stacks", or
> (with Ben's) at the top of [say] the left stack. So there is no
> Tape_Head index to track.
>
> But what you suggest is quite workable...
>
> I think if I were interested in ultimate efficiency, I might go with
> Jeff's "chained blocks" with a comfortably large chosen page size. (But
> efficiency really isn't an issue for this task!)
>
>
> Mike.
>
My implementation of David's solution essentially redefines the whole
notion of std::deque with std:vector's (memory and speed) efficiency and
none of std::deque's limitations: (such as invalidating iterators).
--
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 3 of 10 — ← Prev page 1 2 [3] 4 5 … 10 Next page →
Back to top | Article view | comp.theory
csiph-web