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 5 of 10 — ← Prev page 1 … 3 4 [5] 6 7 … 10 Next page →
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-11 04:02 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <871qx0lqkn.fsf@bsb.me.uk> |
| In reply to | #50215 |
olcott <NoOne@NoWhere.com> writes:
> 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.
You can certainly use a std::vector as a stack but I'd derive my own
stack from a vector so as to make it infinitely "popable" with the pop
operation returning the tape's blank symbol.
> 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.
This looks odd. If you use the two stacks approach, you don't need
Tape_Head. The current cell is never indexed but is always the top of
the Right stack.
--
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 22:07 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <BPKdnQMRR6v4teb_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50220 |
On 5/10/2022 10:02 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> 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.
>
> You can certainly use a std::vector as a stack but I'd derive my own
> stack from a vector so as to make it infinitely "popable" with the pop
> operation returning the tape's blank symbol.
>
>> 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.
>
> This looks odd. If you use the two stacks approach, you don't need
> Tape_Head. The current cell is never indexed but is always the top of
> the Right stack.
>
The current Tape_Head maps to elements of Left or Right
or to an element before Left or after 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 | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-11 13:40 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <87ee108co5.fsf@bsb.me.uk> |
| In reply to | #50221 |
olcott <NoOne@NoWhere.com> writes:
> On 5/10/2022 10:02 PM, Ben wrote:
>> You can certainly use a std::vector as a stack but I'd derive my own
>> stack from a vector so as to make it infinitely "popable" with the pop
>> operation returning the tape's blank symbol.
>>
>>> 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.
>>
>> This looks odd. If you use the two stacks approach, you don't need
>> Tape_Head. The current cell is never indexed but is always the top of
>> the Right stack.
>
> The current Tape_Head maps to elements of Left or Right
> or to an element before Left or after Right.
Even talking about code you won't address the points made -- you just
assert something equally wrong. I won't repeat what I said. Address it
if you like or not.
--
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-11 09:02 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com> |
| In reply to | #50220 |
On 5/10/2022 10:02 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> 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.
>
> You can certainly use a std::vector as a stack but I'd derive my own
> stack from a vector so as to make it infinitely "popable" with the pop
> operation returning the tape's blank symbol.
>
No need for the pop operation.
>> 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.
>
> This looks odd. If you use the two stacks approach, you don't need
> Tape_Head. The current cell is never indexed but is always the top of
> the Right stack.
>
That is simply factually incorrect with my implementation of David
Kleinecke's double stack based std::deque applied to a doubled ended TM
tape.
--
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2022-05-11 16:09 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <t5gjk2$1qj3$1@gioia.aioe.org> |
| In reply to | #50228 |
On 11/05/2022 15:02, olcott wrote:
> On 5/10/2022 10:02 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> 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.
>>
>> You can certainly use a std::vector as a stack but I'd derive my own
>> stack from a vector so as to make it infinitely "popable" with the pop
>> operation returning the tape's blank symbol.
>>
>
> No need for the pop operation.
>
>>> 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.
>>
>> This looks odd. If you use the two stacks approach, you don't need
>> Tape_Head. The current cell is never indexed but is always the top of
>> the Right stack.
>>
>
> That is simply factually incorrect with my implementation of David Kleinecke's double stack based
> std::deque applied to a doubled ended TM tape.
>
Then you've not understood DK and Ben's approach, like I said. Your replies are typical of you not
reading what people write, or simply not understanding what they've written. Do you know what a
stack is?
So, tell us what how Tape_Head changes as the TM runs? Is it not the case Tape_Head will go up by 1
for each R tape movement and down for a L tape movement? (I.e. exactly like I suggested in my
earlier post, when you replied "not in the least little bit"?) THAT IS NOT DK/BEN'S TWO STACK DESIGN.
Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-11 10:29 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <GPCdnW5yC47BS-b_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50231 |
On 5/11/2022 10:09 AM, Mike Terry wrote:
> On 11/05/2022 15:02, olcott wrote:
>> On 5/10/2022 10:02 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> 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.
>>>
>>> You can certainly use a std::vector as a stack but I'd derive my own
>>> stack from a vector so as to make it infinitely "popable" with the pop
>>> operation returning the tape's blank symbol.
>>>
>>
>> No need for the pop operation.
>>
>>>> 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.
>>>
>>> This looks odd. If you use the two stacks approach, you don't need
>>> Tape_Head. The current cell is never indexed but is always the top of
>>> the Right stack.
>>>
>>
>> That is simply factually incorrect with my implementation of David
>> Kleinecke's double stack based std::deque applied to a doubled ended
>> TM tape.
>>
>
> Then you've not understood DK and Ben's approach, like I said. Your
> replies are typical of you not reading what people write, or simply not
> understanding what they've written. Do you know what a stack is?
>
> So, tell us what how Tape_Head changes as the TM runs? Is it not the
> case Tape_Head will go up by 1 for each R tape movement and down for a L
> tape movement?
The specified Tape_Head increments/decrements for move_right/move_left.
The tricky part of this is mapping this to integer subscripts of
Left/Right when both Left/Right can dynamically grow in size.
> (I.e. exactly like I suggested in my earlier post, when
> you replied "not in the least little bit"?) THAT IS NOT DK/BEN'S TWO
> STACK DESIGN.
>
> Mike.
--
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 20:35 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <87sfpf7th7.fsf@bsb.me.uk> |
| In reply to | #50228 |
olcott <NoOne@NoWhere.com> writes:
> On 5/10/2022 10:02 PM, Ben wrote:
>> You can certainly use a std::vector as a stack but I'd derive my own
>> stack from a vector so as to make it infinitely "popable" with the pop
>> operation returning the tape's blank symbol.
>
> No need for the pop operation.
>
>>> 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.
>>
>> This looks odd. If you use the two stacks approach, you don't need
>> Tape_Head. The current cell is never indexed but is always the top of
>> the Right stack.
>
> That is simply factually incorrect with my implementation of David
> Kleinecke's double stack based std::deque applied to a doubled ended
> TM tape.
You still don't understand the two stack method. Here is a sketch of
how it's done. The reason it's efficient (in so far as it is) is that
the tape move is simply:
if (go_right) left.push(right.pop());
else right.push(left.pop());
---------- code -------
#include <iostream>
#include <vector>
#include <string>
struct infinite_stack : public std::vector<char> {
char top() const { return empty() ? '_' : back(); }
char pop() { char c = top(); if (!empty()) pop_back(); return c; }
void push(char c) { push_back(c); }
};
struct tape {
tape(std::string s);
infinite_stack left, right;
void move(bool go_right) {
if (go_right) left.push(right.pop());
else right.push(left.pop());
}
friend std::ostream &operator<<(std::ostream &os, const tape &t);
};
tape::tape(std::string s)
{
for (auto i = s.size(); i-- > 0;) right.push(s[i]);
}
std::ostream &operator<<(std::ostream &os, const tape &t)
{
for (char c : t.left) os.put(c);
os << '[' << t.right.top() << ']';
for (auto i = t.right.size() - 1; i-- > 0;) os.put(t.right[i]);
return os;
}
int main()
{
tape test("abcdef");
std::cout << test << "\n";
test.move(0); std::cout << test << "\n";
test.move(0); std::cout << test << "\n";
test.move(1); std::cout << test << "\n";
test.move(1); std::cout << test << "\n";
test.move(1); std::cout << test << "\n";
}
--
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-11 15:12 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50242 |
On 5/11/2022 2:35 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/10/2022 10:02 PM, Ben wrote:
>
>>> You can certainly use a std::vector as a stack but I'd derive my own
>>> stack from a vector so as to make it infinitely "popable" with the pop
>>> operation returning the tape's blank symbol.
>>
>> No need for the pop operation.
>>
>>>> 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.
>>>
>>> This looks odd. If you use the two stacks approach, you don't need
>>> Tape_Head. The current cell is never indexed but is always the top of
>>> the Right stack.
>>
>> That is simply factually incorrect with my implementation of David
>> Kleinecke's double stack based std::deque applied to a doubled ended
>> TM tape.
>
> You still don't understand the two stack method. Here is a sketch of
> how it's done. The reason it's efficient (in so far as it is) is that
> the tape move is simply:
>
> if (go_right) left.push(right.pop());
> else right.push(left.pop());
>
> ---------- code -------
> #include <iostream>
> #include <vector>
> #include <string>
>
> struct infinite_stack : public std::vector<char> {
> char top() const { return empty() ? '_' : back(); }
> char pop() { char c = top(); if (!empty()) pop_back(); return c; }
> void push(char c) { push_back(c); }
> };
>
> struct tape {
> tape(std::string s);
> infinite_stack left, right;
> void move(bool go_right) {
> if (go_right) left.push(right.pop());
> else right.push(left.pop());
> }
> friend std::ostream &operator<<(std::ostream &os, const tape &t);
> };
>
> tape::tape(std::string s)
> {
> for (auto i = s.size(); i-- > 0;) right.push(s[i]);
> }
>
> std::ostream &operator<<(std::ostream &os, const tape &t)
> {
> for (char c : t.left) os.put(c);
> os << '[' << t.right.top() << ']';
> for (auto i = t.right.size() - 1; i-- > 0;) os.put(t.right[i]);
> return os;
> }
>
> int main()
> {
> tape test("abcdef");
> std::cout << test << "\n";
> test.move(0); std::cout << test << "\n";
> test.move(0); std::cout << test << "\n";
> test.move(1); std::cout << test << "\n";
> test.move(1); std::cout << test << "\n";
> test.move(1); std::cout << test << "\n";
> }
>
>
I think that my way is more efficient.
I will post it as soon as it is done.
--
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 22:54 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <87bkw37n1f.fsf@bsb.me.uk> |
| In reply to | #50245 |
olcott <NoOne@NoWhere.com> writes:
> On 5/11/2022 2:35 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/10/2022 10:02 PM, Ben wrote:
>>
>>>> You can certainly use a std::vector as a stack but I'd derive my own
>>>> stack from a vector so as to make it infinitely "popable" with the pop
>>>> operation returning the tape's blank symbol.
>>>
>>> No need for the pop operation.
>> You still don't understand the two stack method. Here is a sketch of
>> how it's done. The reason it's efficient (in so far as it is) is that
>> the tape move is simply:
>> if (go_right) left.push(right.pop());
>> else right.push(left.pop());
>> ---------- code -------
>> #include <iostream>
>> #include <vector>
>> #include <string>
>> struct infinite_stack : public std::vector<char> {
>> char top() const { return empty() ? '_' : back(); }
>> char pop() { char c = top(); if (!empty()) pop_back(); return c; }
>> void push(char c) { push_back(c); }
>> };
>> struct tape {
>> tape(std::string s);
>> infinite_stack left, right;
>> void move(bool go_right) {
>> if (go_right) left.push(right.pop());
>> else right.push(left.pop());
>> }
>> friend std::ostream &operator<<(std::ostream &os, const tape &t);
>> };
>> tape::tape(std::string s)
>> {
>> for (auto i = s.size(); i-- > 0;) right.push(s[i]);
>> }
>> std::ostream &operator<<(std::ostream &os, const tape &t)
>> {
>> for (char c : t.left) os.put(c);
>> os << '[' << t.right.top() << ']';
>> for (auto i = t.right.size() - 1; i-- > 0;) os.put(t.right[i]);
>> return os;
>> }
>> int main()
>> {
>> tape test("abcdef");
>> std::cout << test << "\n";
>> test.move(0); std::cout << test << "\n";
>> test.move(0); std::cout << test << "\n";
>> test.move(1); std::cout << test << "\n";
>> test.move(1); std::cout << test << "\n";
>> test.move(1); std::cout << test << "\n";
>> }
>
> I think that my way is more efficient.
That may well be the case. But your way is not the "two stacks" way if
there is no need for pop.
--
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-11 17:02 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50250 |
On 5/11/2022 4:54 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/11/2022 2:35 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/10/2022 10:02 PM, Ben wrote:
>>>
>>>>> You can certainly use a std::vector as a stack but I'd derive my own
>>>>> stack from a vector so as to make it infinitely "popable" with the pop
>>>>> operation returning the tape's blank symbol.
>>>>
>>>> No need for the pop operation.
>
>>> You still don't understand the two stack method. Here is a sketch of
>>> how it's done. The reason it's efficient (in so far as it is) is that
>>> the tape move is simply:
>>> if (go_right) left.push(right.pop());
>>> else right.push(left.pop());
>>> ---------- code -------
>>> #include <iostream>
>>> #include <vector>
>>> #include <string>
>>> struct infinite_stack : public std::vector<char> {
>>> char top() const { return empty() ? '_' : back(); }
>>> char pop() { char c = top(); if (!empty()) pop_back(); return c; }
>>> void push(char c) { push_back(c); }
>>> };
>>> struct tape {
>>> tape(std::string s);
>>> infinite_stack left, right;
>>> void move(bool go_right) {
>>> if (go_right) left.push(right.pop());
>>> else right.push(left.pop());
>>> }
>>> friend std::ostream &operator<<(std::ostream &os, const tape &t);
>>> };
>>> tape::tape(std::string s)
>>> {
>>> for (auto i = s.size(); i-- > 0;) right.push(s[i]);
>>> }
>>> std::ostream &operator<<(std::ostream &os, const tape &t)
>>> {
>>> for (char c : t.left) os.put(c);
>>> os << '[' << t.right.top() << ']';
>>> for (auto i = t.right.size() - 1; i-- > 0;) os.put(t.right[i]);
>>> return os;
>>> }
>>> int main()
>>> {
>>> tape test("abcdef");
>>> std::cout << test << "\n";
>>> test.move(0); std::cout << test << "\n";
>>> test.move(0); std::cout << test << "\n";
>>> test.move(1); std::cout << test << "\n";
>>> test.move(1); std::cout << test << "\n";
>>> test.move(1); std::cout << test << "\n";
>>> }
>>
>> I think that my way is more efficient.
>
> That may well be the case. But your way is not the "two stacks" way if
> there is no need for pop.
>
It is only two stacks in the sense that Left accesses its elements from
back to front. Since Right accesses its elements from front to back only
Left is like a stack.
--
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-12 02:00 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <87lev75zv6.fsf@bsb.me.uk> |
| In reply to | #50251 |
olcott <NoOne@NoWhere.com> writes: > On 5/11/2022 4:54 PM, Ben wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> On 5/11/2022 2:35 PM, Ben wrote: >>>> olcott <NoOne@NoWhere.com> writes: >>>> >>>>> On 5/10/2022 10:02 PM, Ben wrote: >>>> >>>>>> You can certainly use a std::vector as a stack but I'd derive my own >>>>>> stack from a vector so as to make it infinitely "popable" with the pop >>>>>> operation returning the tape's blank symbol. >>>>> >>>>> No need for the pop operation. >>> I think that my way is more efficient. >> >> That may well be the case. But your way is not the "two stacks" way if >> there is no need for pop. > > It is only two stacks in the sense that Left accesses its elements > from back to front. Since Right accesses its elements from front to > back only Left is like a stack. That's not what a stack is. Mind you, your writing is poor in that Right and Left don't access themselves so I have had to guess what you mean: possibly "the elements of Left are accessed from back to front" (and analogous wording for Right). It's even possible that you /are/ using two stacks and simply writing words that hide that fact. Can't you even post the code for the function that moves and/or updates the tape? Surely that part is now written? That way we'd know what data structure you are using... -- 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-11 20:37 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com> |
| In reply to | #50263 |
On 5/11/2022 8:00 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/11/2022 4:54 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/11/2022 2:35 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/10/2022 10:02 PM, Ben wrote:
>>>>>
>>>>>>> You can certainly use a std::vector as a stack but I'd derive my own
>>>>>>> stack from a vector so as to make it infinitely "popable" with the pop
>>>>>>> operation returning the tape's blank symbol.
>>>>>>
>>>>>> No need for the pop operation.
>
>>>> I think that my way is more efficient.
>>>
>>> That may well be the case. But your way is not the "two stacks" way if
>>> there is no need for pop.
>>
>> It is only two stacks in the sense that Left accesses its elements
>> from back to front. Since Right accesses its elements from front to
>> back only Left is like a stack.
>
> That's not what a stack is.
>
> Mind you, your writing is poor in that Right and Left don't access
> themselves so I have had to guess what you mean: possibly "the elements
> of Left are accessed from back to front" (and analogous wording for
> Right).
>
> It's even possible that you /are/ using two stacks and simply writing
> words that hide that fact.
>
> Can't you even post the code for the function that moves and/or updates
> the tape? Surely that part is now written? That way we'd know what
> data structure you are using...
>
struct Tape
{
unsigned int Tape_Head;
std::vector<unsigned char> Left;
std::vector<unsigned char> Right;
unsigned int move_left();
unsigned int move_right();
};
The part of mapping Tape_Head to a location in Left or Right needs more
desk checking before I will implement it.
We can add space with the efficiently of std::vector.
Much more (time & space) efficient and far less clumsy of an
implementation than std::deque. Seems to simply be a better std::deque.
--
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-12 02:49 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <874k1v5xll.fsf@bsb.me.uk> |
| In reply to | #50267 |
olcott <NoOne@NoWhere.com> writes:
> On 5/11/2022 8:00 PM, Ben wrote:
>> Can't you even post the code for the function that moves and/or updates
>> the tape? Surely that part is now written? That way we'd know what
>> data structure you are using...
>
> struct Tape
> {
> unsigned int Tape_Head;
> std::vector<unsigned char> Left;
> std::vector<unsigned char> Right;
> unsigned int move_left();
> unsigned int move_right();
> };
>
> The part of mapping Tape_Head to a location in Left or Right needs
> more desk checking before I will implement it.
How long is that going to take?
--
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-11 21:49 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <2eOdnW7GpMwx6OH_nZ2dnUU7_81g4p2d@giganews.com> |
| In reply to | #50268 |
On 5/11/2022 8:49 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/11/2022 8:00 PM, Ben wrote:
>
>>> Can't you even post the code for the function that moves and/or updates
>>> the tape? Surely that part is now written? That way we'd know what
>>> data structure you are using...
>>
>> struct Tape
>> {
>> unsigned int Tape_Head;
>> std::vector<unsigned char> Left;
>> std::vector<unsigned char> Right;
>> unsigned int move_left();
>> unsigned int move_right();
>> };
>>
>> The part of mapping Tape_Head to a location in Left or Right needs
>> more desk checking before I will implement it.
>
> How long is that going to take?
>
Less than 8 labor hours, maybe 2 labor hours.
I only work on it for 5 minutes every 2 hours.
--
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-12 14:45 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <87y1z650gu.fsf@bsb.me.uk> |
| In reply to | #50272 |
olcott <NoOne@NoWhere.com> writes:
> On 5/11/2022 8:49 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/11/2022 8:00 PM, Ben wrote:
>>
>>>> Can't you even post the code for the function that moves and/or updates
>>>> the tape? Surely that part is now written? That way we'd know what
>>>> data structure you are using...
>>>
>>> struct Tape
>>> {
>>> unsigned int Tape_Head;
>>> std::vector<unsigned char> Left;
>>> std::vector<unsigned char> Right;
>>> unsigned int move_left();
>>> unsigned int move_right();
>>> };
>>>
>>> The part of mapping Tape_Head to a location in Left or Right needs
>>> more desk checking before I will implement it.
>> How long is that going to take?
>
> Less than 8 labor hours, maybe 2 labor hours.
For just the tape? Surely not. I wanted to resolve what data structure
you are actually gong to be using.
> I only work on it for 5 minutes every 2 hours.
So may be another 12 days. Oh well, I'll see if I can apply the "tying
the knot" trick to my Haskell code...
--
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-12 10:31 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <XdadnZj8avjLteD_nZ2dnUU7_8zNnZ2d@giganews.com> |
| In reply to | #50280 |
On 5/12/2022 8:45 AM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/11/2022 8:49 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/11/2022 8:00 PM, Ben wrote:
>>>
>>>>> Can't you even post the code for the function that moves and/or updates
>>>>> the tape? Surely that part is now written? That way we'd know what
>>>>> data structure you are using...
>>>>
>>>> struct Tape
>>>> {
>>>> unsigned int Tape_Head;
>>>> std::vector<unsigned char> Left;
>>>> std::vector<unsigned char> Right;
>>>> unsigned int move_left();
>>>> unsigned int move_right();
>>>> };
>>>>
>>>> The part of mapping Tape_Head to a location in Left or Right needs
>>>> more desk checking before I will implement it.
>>> How long is that going to take?
>>
>> Less than 8 labor hours, maybe 2 labor hours.
>
> For just the tape? Surely not. I wanted to resolve what data structure
> you are actually gong to be using.
>
>> I only work on it for 5 minutes every 2 hours.
>
> So may be another 12 days. Oh well, I'll see if I can apply the "tying
> the knot" trick to my Haskell code...
>
I have it almost done. I staid up late working on it.
I got very enthused. This is lots of fun. It is also essentially
basically a significant improvement to how std::deque could be implemented.
--
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-12 21:20 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <875yma4i6b.fsf@bsb.me.uk> |
| In reply to | #50282 |
olcott <NoOne@NoWhere.com> writes:
> On 5/12/2022 8:45 AM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/11/2022 8:49 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/11/2022 8:00 PM, Ben wrote:
>>>>
>>>>>> Can't you even post the code for the function that moves and/or updates
>>>>>> the tape? Surely that part is now written? That way we'd know what
>>>>>> data structure you are using...
>>>>>
>>>>> struct Tape
>>>>> {
>>>>> unsigned int Tape_Head;
>>>>> std::vector<unsigned char> Left;
>>>>> std::vector<unsigned char> Right;
>>>>> unsigned int move_left();
>>>>> unsigned int move_right();
>>>>> };
>>>>>
>>>>> The part of mapping Tape_Head to a location in Left or Right needs
>>>>> more desk checking before I will implement it.
>>>> How long is that going to take?
>>>
>>> Less than 8 labor hours, maybe 2 labor hours.
>> For just the tape? Surely not. I wanted to resolve what data structure
>> you are actually gong to be using.
>>
>>> I only work on it for 5 minutes every 2 hours.
>> So may be another 12 days. Oh well, I'll see if I can apply the "tying
>> the knot" trick to my Haskell code...
>
> I have it almost done.
Not even the two tape movement functions?
> I staid up late working on it.
> I got very enthused. This is lots of fun.
A bit of programming is always fun.
> It is also essentially basically a significant improvement to how
> std::deque could be implemented.
This is ambiguous. It is easy to find an improvement over how
std::deque /could/ be implemented (since it /could/ be implemented
badly), but, on the other hand, I am sure you don't know all the ways
std::deque /could/ be implemented so you can't know you have an
improvement of that sort.
--
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-12 15:33 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <oZadnf2QMLKV8uD_nZ2dnUU7_8zNnZ2d@giganews.com> |
| In reply to | #50297 |
On 5/12/2022 3:20 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/12/2022 8:45 AM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/11/2022 8:49 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/11/2022 8:00 PM, Ben wrote:
>>>>>
>>>>>>> Can't you even post the code for the function that moves and/or updates
>>>>>>> the tape? Surely that part is now written? That way we'd know what
>>>>>>> data structure you are using...
>>>>>>
>>>>>> struct Tape
>>>>>> {
>>>>>> unsigned int Tape_Head;
>>>>>> std::vector<unsigned char> Left;
>>>>>> std::vector<unsigned char> Right;
>>>>>> unsigned int move_left();
>>>>>> unsigned int move_right();
>>>>>> };
>>>>>>
>>>>>> The part of mapping Tape_Head to a location in Left or Right needs
>>>>>> more desk checking before I will implement it.
>>>>> How long is that going to take?
>>>>
>>>> Less than 8 labor hours, maybe 2 labor hours.
>>> For just the tape? Surely not. I wanted to resolve what data structure
>>> you are actually gong to be using.
>>>
>>>> I only work on it for 5 minutes every 2 hours.
>>> So may be another 12 days. Oh well, I'll see if I can apply the "tying
>>> the knot" trick to my Haskell code...
>>
>> I have it almost done.
>
> Not even the two tape movement functions?
>
>> I staid up late working on it.
>> I got very enthused. This is lots of fun.
>
> A bit of programming is always fun.
>
>> It is also essentially basically a significant improvement to how
>> std::deque could be implemented.
>
> This is ambiguous. It is easy to find an improvement over how
> std::deque /could/ be implemented (since it /could/ be implemented
> badly), but, on the other hand, I am sure you don't know all the ways
> std::deque /could/ be implemented so you can't know you have an
> improvement of that sort.
>
The Tape_Type is almost done. It is ideal for a two-way TM tape. It has
the key benefit of being able to grow on both ends.
Unlike the messy overhead of the conventional std::deque implementation
it has all of the efficiently of std:vector because it is implemented as
a pair of std::vectors.
Left for growing left and Right for growing right. int Tape_Head >= 0
points to elements of Right, in order.
int Tape_Head < 0 points to elements of Left, such that -1 points to
Left[0] et cetera.
--
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 | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2022-05-12 21:36 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <20220512213658.0000325b@reddwarf.jmc> |
| In reply to | #50299 |
On Thu, 12 May 2022 15:33:11 -0500
olcott <NoOne@NoWhere.com> wrote:
> On 5/12/2022 3:20 PM, Ben wrote:
> > olcott <NoOne@NoWhere.com> writes:
> >
> >> On 5/12/2022 8:45 AM, Ben wrote:
> >>> olcott <NoOne@NoWhere.com> writes:
> >>>
> >>>> On 5/11/2022 8:49 PM, Ben wrote:
> >>>>> olcott <NoOne@NoWhere.com> writes:
> >>>>>
> >>>>>> On 5/11/2022 8:00 PM, Ben wrote:
> >>>>>
> >>>>>>> Can't you even post the code for the function that moves
> >>>>>>> and/or updates the tape? Surely that part is now written?
> >>>>>>> That way we'd know what data structure you are using...
> >>>>>>
> >>>>>> struct Tape
> >>>>>> {
> >>>>>> unsigned int Tape_Head;
> >>>>>> std::vector<unsigned char> Left;
> >>>>>> std::vector<unsigned char> Right;
> >>>>>> unsigned int move_left();
> >>>>>> unsigned int move_right();
> >>>>>> };
> >>>>>>
> >>>>>> The part of mapping Tape_Head to a location in Left or Right
> >>>>>> needs more desk checking before I will implement it.
> >>>>> How long is that going to take?
> >>>>
> >>>> Less than 8 labor hours, maybe 2 labor hours.
> >>> For just the tape? Surely not. I wanted to resolve what data
> >>> structure you are actually gong to be using.
> >>>
> >>>> I only work on it for 5 minutes every 2 hours.
> >>> So may be another 12 days. Oh well, I'll see if I can apply the
> >>> "tying the knot" trick to my Haskell code...
> >>
> >> I have it almost done.
> >
> > Not even the two tape movement functions?
> >
> >> I staid up late working on it.
> >> I got very enthused. This is lots of fun.
> >
> > A bit of programming is always fun.
> >
> >> It is also essentially basically a significant improvement to how
> >> std::deque could be implemented.
> >
> > This is ambiguous. It is easy to find an improvement over how
> > std::deque /could/ be implemented (since it /could/ be implemented
> > badly), but, on the other hand, I am sure you don't know all the
> > ways std::deque /could/ be implemented so you can't know you have an
> > improvement of that sort.
> >
>
> The Tape_Type is almost done. It is ideal for a two-way TM tape. It
> has the key benefit of being able to grow on both ends.
>
> Unlike the messy overhead of the conventional std::deque
> implementation it has all of the efficiently of std:vector because it
> is implemented as a pair of std::vectors.
You cannot meet the complexity and element referential integrity
guarantees that std::deque offers with a pair of std::vectors. You are
obviously a C++ n00b.
/Flibble
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-12 16:28 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <ecqdnUEriPhi5uD_nZ2dnUU7_8zNnZ2d@giganews.com> |
| In reply to | #50300 |
On 5/12/2022 3:36 PM, Mr Flibble wrote:
> On Thu, 12 May 2022 15:33:11 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/12/2022 3:20 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/12/2022 8:45 AM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/11/2022 8:49 PM, Ben wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/11/2022 8:00 PM, Ben wrote:
>>>>>>>
>>>>>>>>> Can't you even post the code for the function that moves
>>>>>>>>> and/or updates the tape? Surely that part is now written?
>>>>>>>>> That way we'd know what data structure you are using...
>>>>>>>>
>>>>>>>> struct Tape
>>>>>>>> {
>>>>>>>> unsigned int Tape_Head;
>>>>>>>> std::vector<unsigned char> Left;
>>>>>>>> std::vector<unsigned char> Right;
>>>>>>>> unsigned int move_left();
>>>>>>>> unsigned int move_right();
>>>>>>>> };
>>>>>>>>
>>>>>>>> The part of mapping Tape_Head to a location in Left or Right
>>>>>>>> needs more desk checking before I will implement it.
>>>>>>> How long is that going to take?
>>>>>>
>>>>>> Less than 8 labor hours, maybe 2 labor hours.
>>>>> For just the tape? Surely not. I wanted to resolve what data
>>>>> structure you are actually gong to be using.
>>>>>
>>>>>> I only work on it for 5 minutes every 2 hours.
>>>>> So may be another 12 days. Oh well, I'll see if I can apply the
>>>>> "tying the knot" trick to my Haskell code...
>>>>
>>>> I have it almost done.
>>>
>>> Not even the two tape movement functions?
>>>
>>>> I staid up late working on it.
>>>> I got very enthused. This is lots of fun.
>>>
>>> A bit of programming is always fun.
>>>
>>>> It is also essentially basically a significant improvement to how
>>>> std::deque could be implemented.
>>>
>>> This is ambiguous. It is easy to find an improvement over how
>>> std::deque /could/ be implemented (since it /could/ be implemented
>>> badly), but, on the other hand, I am sure you don't know all the
>>> ways std::deque /could/ be implemented so you can't know you have an
>>> improvement of that sort.
>>>
>>
>> The Tape_Type is almost done. It is ideal for a two-way TM tape. It
>> has the key benefit of being able to grow on both ends.
>>
>> Unlike the messy overhead of the conventional std::deque
>> implementation it has all of the efficiently of std:vector because it
>> is implemented as a pair of std::vectors.
>
> You cannot meet the complexity and element referential integrity
> guarantees that std::deque offers with a pair of std::vectors. You are
> obviously a C++ n00b.
>
> /Flibble
>
It has the same Big-O complexity (with less overhead)
As far as referential integrity std::deque does not do very well.
https://www.geeksforgeeks.org/iterator-invalidation-cpp/
--
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 5 of 10 — ← Prev page 1 … 3 4 [5] 6 7 … 10 Next page →
Back to top | Article view | comp.theory
csiph-web