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 9 of 10 — ← Prev page 1 … 7 8 [9] 10 Next page →
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-13 19:06 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <f8ednbx2fY4Cb-P_nZ2dnUU7_81g4p2d@giganews.com> |
| In reply to | #50508 |
On 5/13/2022 6:48 PM, Jeff Barnett wrote: > On 5/13/2022 3:16 PM, olcott wrote: >> On 5/13/2022 4:06 PM, Jeff Barnett wrote: >>> On 5/13/2022 1:12 PM, Ben wrote: >>>> olcott <NoOne@NoWhere.com> writes: >>>> >>>>> On 5/13/2022 1:45 PM, Ben wrote: >>>>>> olcott <NoOne@NoWhere.com> writes: >>>>>> >>>>>>> Flibble found a case where my member functions would need to be >>>>>>> extended and this extension may have a worse Big-O than >>>>>>> std::deque in >>>>>>> some cases. >>>>>> >>>>>> As did everyone who glanced at the code for more than a few >>>>>> seconds. Or >>>>>> at least I sincerely hope they did. It's not hard to see that >>>>>> your code >>>>>> was wrong. >>>>> >>>>> The details of std::deque is almost brand new to me. >>>> >>>> I guessed as much. Yet you claimed to have done better than the teams >>>> of experienced programmers who've worked on various C++ standard >>>> libraries after writing only a few lines of code? That level of >>>> delusion might lead someone to think they can solve the halting >>>> problem. >>>> >>>>> None-the-less my Tape_Type does seem optimal for a TM tape as long as >>>>> the speed with Tape_Type::reserve() beats some and matches the rest of >>>>> the speed of every operation of your std::string, otherwise I would go >>>>> for the simpler std::string version. >>>> >>>> Using reserve has no effect on the one test case I have for timing. >>> Everyone as noted and/or commented on the fact that PO does not read >>> all that he cites or all that he criticizes. My conjecture is that he >>> has a learning disability that is manifest in his inability to stay >>> focused on or retain what he reads. >>> >>> Take this TM implementation nonsense: a few years ago many of us >>> (including me) suggested TM testers and interpreters. He refused to >>> use them at that time and now is trying to implement one himself. I >>> don't think that it's for fun or curiosity. I think its because he >>> cannot keep several ideas in his head at the same time. And what is >>> this nonsense about rewriting part of the C library? I think that >>> retaining enough of the documentation to use the existing package is >>> beyond his reading and retaining abilities. So there is a desperate >>> hope that he might be able to learn it by doing. The problem is that >>> he must fog the landscape with obscurities to hide the display of his >>> inabilities behind. >>> >>> If you have a moment to reflect, see if this viewpoint explains some >>> or all of the exhibitions of the last few years to you. I'd be >>> interested in what you think. >> >> My original intent was to rewrite this to give it a three minute >> learning curve. http://www.lns.mit.edu/~dsw/turing/turing.html >> >> It is also useful for me to understand TM's better by writing one from >> scratch. > And what did you learn by badly miscoding part of the C library? <- > that's a sarcastic question mark. Tape_Type does seem to be an optimal way to define a TM tape in C++, thus providing the other aspect of my design that has unlimited scalability. Scalable state change is the other aspect. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2022-05-13 19:58 -0600 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <t5n2cd$r23$1@dont-email.me> |
| In reply to | #50513 |
On 5/13/2022 6:06 PM, olcott wrote: > On 5/13/2022 6:48 PM, Jeff Barnett wrote: >> On 5/13/2022 3:16 PM, olcott wrote: >>> On 5/13/2022 4:06 PM, Jeff Barnett wrote: >>>> On 5/13/2022 1:12 PM, Ben wrote: >>>>> olcott <NoOne@NoWhere.com> writes: >>>>> >>>>>> On 5/13/2022 1:45 PM, Ben wrote: >>>>>>> olcott <NoOne@NoWhere.com> writes: >>>>>>> >>>>>>>> Flibble found a case where my member functions would need to be >>>>>>>> extended and this extension may have a worse Big-O than >>>>>>>> std::deque in >>>>>>>> some cases. >>>>>>> >>>>>>> As did everyone who glanced at the code for more than a few >>>>>>> seconds. Or >>>>>>> at least I sincerely hope they did. It's not hard to see that >>>>>>> your code >>>>>>> was wrong. >>>>>> >>>>>> The details of std::deque is almost brand new to me. >>>>> >>>>> I guessed as much. Yet you claimed to have done better than the teams >>>>> of experienced programmers who've worked on various C++ standard >>>>> libraries after writing only a few lines of code? That level of >>>>> delusion might lead someone to think they can solve the halting >>>>> problem. >>>>> >>>>>> None-the-less my Tape_Type does seem optimal for a TM tape as long as >>>>>> the speed with Tape_Type::reserve() beats some and matches the >>>>>> rest of >>>>>> the speed of every operation of your std::string, otherwise I >>>>>> would go >>>>>> for the simpler std::string version. >>>>> >>>>> Using reserve has no effect on the one test case I have for timing. >>>> Everyone as noted and/or commented on the fact that PO does not read >>>> all that he cites or all that he criticizes. My conjecture is that >>>> he has a learning disability that is manifest in his inability to >>>> stay focused on or retain what he reads. >>>> >>>> Take this TM implementation nonsense: a few years ago many of us >>>> (including me) suggested TM testers and interpreters. He refused to >>>> use them at that time and now is trying to implement one himself. I >>>> don't think that it's for fun or curiosity. I think its because he >>>> cannot keep several ideas in his head at the same time. And what is >>>> this nonsense about rewriting part of the C library? I think that >>>> retaining enough of the documentation to use the existing package is >>>> beyond his reading and retaining abilities. So there is a desperate >>>> hope that he might be able to learn it by doing. The problem is that >>>> he must fog the landscape with obscurities to hide the display of >>>> his inabilities behind. >>>> >>>> If you have a moment to reflect, see if this viewpoint explains some >>>> or all of the exhibitions of the last few years to you. I'd be >>>> interested in what you think. >>> >>> My original intent was to rewrite this to give it a three minute >>> learning curve. http://www.lns.mit.edu/~dsw/turing/turing.html >>> >>> It is also useful for me to understand TM's better by writing one >>> from scratch. >> And what did you learn by badly miscoding part of the C library? <- >> that's a sarcastic question mark. > > Tape_Type does seem to be an optimal way to define a TM tape in C++, > thus providing the other aspect of my design that has unlimited > scalability. Scalable state change is the other aspect. Are you doing indefinite precision address pointers, etc? Or are you smoking dope again? This is absurd! You have memory sizes of dozens (or hundreds) of gigabytes and disk arrays of dozens or hundreds of terabytes. So how far are you going to scale up? Are you going to add offline disk arrays that swap with the ones online? So are you going to to set a world record? Or the real question: How much smoke are you going to blow to cover up the fact that you can't do lesson one? You know the one. Write a TM that accepts even numbers where numbers are encode base one, i.e., the length of the string is the number? -- Jeff Barnett
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-13 22:39 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <7bednRyhFMzqueL_nZ2dnUU7_8xh4p2d@giganews.com> |
| In reply to | #50532 |
On 5/13/2022 8:58 PM, Jeff Barnett wrote: > On 5/13/2022 6:06 PM, olcott wrote: >> On 5/13/2022 6:48 PM, Jeff Barnett wrote: >>> On 5/13/2022 3:16 PM, olcott wrote: >>>> On 5/13/2022 4:06 PM, Jeff Barnett wrote: >>>>> On 5/13/2022 1:12 PM, Ben wrote: >>>>>> olcott <NoOne@NoWhere.com> writes: >>>>>> >>>>>>> On 5/13/2022 1:45 PM, Ben wrote: >>>>>>>> olcott <NoOne@NoWhere.com> writes: >>>>>>>> >>>>>>>>> Flibble found a case where my member functions would need to be >>>>>>>>> extended and this extension may have a worse Big-O than >>>>>>>>> std::deque in >>>>>>>>> some cases. >>>>>>>> >>>>>>>> As did everyone who glanced at the code for more than a few >>>>>>>> seconds. Or >>>>>>>> at least I sincerely hope they did. It's not hard to see that >>>>>>>> your code >>>>>>>> was wrong. >>>>>>> >>>>>>> The details of std::deque is almost brand new to me. >>>>>> >>>>>> I guessed as much. Yet you claimed to have done better than the >>>>>> teams >>>>>> of experienced programmers who've worked on various C++ standard >>>>>> libraries after writing only a few lines of code? That level of >>>>>> delusion might lead someone to think they can solve the halting >>>>>> problem. >>>>>> >>>>>>> None-the-less my Tape_Type does seem optimal for a TM tape as >>>>>>> long as >>>>>>> the speed with Tape_Type::reserve() beats some and matches the >>>>>>> rest of >>>>>>> the speed of every operation of your std::string, otherwise I >>>>>>> would go >>>>>>> for the simpler std::string version. >>>>>> >>>>>> Using reserve has no effect on the one test case I have for timing. >>>>> Everyone as noted and/or commented on the fact that PO does not >>>>> read all that he cites or all that he criticizes. My conjecture is >>>>> that he has a learning disability that is manifest in his inability >>>>> to stay focused on or retain what he reads. >>>>> >>>>> Take this TM implementation nonsense: a few years ago many of us >>>>> (including me) suggested TM testers and interpreters. He refused to >>>>> use them at that time and now is trying to implement one himself. I >>>>> don't think that it's for fun or curiosity. I think its because he >>>>> cannot keep several ideas in his head at the same time. And what is >>>>> this nonsense about rewriting part of the C library? I think that >>>>> retaining enough of the documentation to use the existing package >>>>> is beyond his reading and retaining abilities. So there is a >>>>> desperate hope that he might be able to learn it by doing. The >>>>> problem is that he must fog the landscape with obscurities to hide >>>>> the display of his inabilities behind. >>>>> >>>>> If you have a moment to reflect, see if this viewpoint explains >>>>> some or all of the exhibitions of the last few years to you. I'd be >>>>> interested in what you think. >>>> >>>> My original intent was to rewrite this to give it a three minute >>>> learning curve. http://www.lns.mit.edu/~dsw/turing/turing.html >>>> >>>> It is also useful for me to understand TM's better by writing one >>>> from scratch. >>> And what did you learn by badly miscoding part of the C library? <- >>> that's a sarcastic question mark. >> >> Tape_Type does seem to be an optimal way to define a TM tape in C++, >> thus providing the other aspect of my design that has unlimited >> scalability. Scalable state change is the other aspect. > > Are you doing indefinite precision address pointers, etc? Or are you > smoking dope again? This is absurd! You have memory sizes of dozens (or > hundreds) of gigabytes and disk arrays of dozens or hundreds of > terabytes. So how far are you going to scale up? At least 4GB > Are you going to add > offline disk arrays that swap with the ones online? So are you going to > to set a world record? > > Or the real question: How much smoke are you going to blow to cover up > the fact that you can't do lesson one? You know the one. Write a TM that > accepts even numbers where numbers are encode base one, i.e., the length > of the string is the number? -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2022-05-13 19:48 -0600 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <t5n1pu$oga$1@dont-email.me> |
| In reply to | #50455 |
On 5/13/2022 3:16 PM, olcott wrote: > On 5/13/2022 4:06 PM, Jeff Barnett wrote: >> On 5/13/2022 1:12 PM, Ben wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> On 5/13/2022 1:45 PM, Ben wrote: >>>>> olcott <NoOne@NoWhere.com> writes: >>>>> >>>>>> Flibble found a case where my member functions would need to be >>>>>> extended and this extension may have a worse Big-O than std::deque in >>>>>> some cases. >>>>> >>>>> As did everyone who glanced at the code for more than a few >>>>> seconds. Or >>>>> at least I sincerely hope they did. It's not hard to see that your >>>>> code >>>>> was wrong. >>>> >>>> The details of std::deque is almost brand new to me. >>> >>> I guessed as much. Yet you claimed to have done better than the teams >>> of experienced programmers who've worked on various C++ standard >>> libraries after writing only a few lines of code? That level of >>> delusion might lead someone to think they can solve the halting problem. >>> >>>> None-the-less my Tape_Type does seem optimal for a TM tape as long as >>>> the speed with Tape_Type::reserve() beats some and matches the rest of >>>> the speed of every operation of your std::string, otherwise I would go >>>> for the simpler std::string version. >>> >>> Using reserve has no effect on the one test case I have for timing. >> Everyone as noted and/or commented on the fact that PO does not read >> all that he cites or all that he criticizes. My conjecture is that he >> has a learning disability that is manifest in his inability to stay >> focused on or retain what he reads. >> >> Take this TM implementation nonsense: a few years ago many of us >> (including me) suggested TM testers and interpreters. He refused to >> use them at that time and now is trying to implement one himself. I >> don't think that it's for fun or curiosity. I think its because he >> cannot keep several ideas in his head at the same time. And what is >> this nonsense about rewriting part of the C library? I think that >> retaining enough of the documentation to use the existing package is >> beyond his reading and retaining abilities. So there is a desperate >> hope that he might be able to learn it by doing. The problem is that >> he must fog the landscape with obscurities to hide the display of his >> inabilities behind. >> >> If you have a moment to reflect, see if this viewpoint explains some >> or all of the exhibitions of the last few years to you. I'd be >> interested in what you think. > > My original intent was to rewrite this to give it a three minute > learning curve. http://www.lns.mit.edu/~dsw/turing/turing.html > > It is also useful for me to understand TM's better by writing one from > scratch. So you think the best way to learn a language is to write an interpreter for it? That's just silly nonsense. You were unable to complete Ben's first lesson - write a TM to accept even numbers with the numbers represented base one. I honestly believe many kids in the last year or two of grade school* could do that assignment. Crawl before you try to walk. Tm interpreters are a dime a dozen. Use one of them and convince yourself that you can do lesson one. * I just sat in on a seminar discussing and describing efforts to add computer engineering - development of computer artifacts such as software - to the curriculum of all grades levels.Based on that and some pilot studies, I believe the most kids could write that TM (EVEN) with an interested teacher helping them learn about the basics. -- Jeff Barnett
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-13 11:00 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <zdmdnVjtirshHeP_nZ2dnUU7_8xh4p2d@giganews.com> |
| In reply to | #50359 |
On 5/13/2022 5:54 AM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/12/2022 8:54 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> Its done see my new post.
>>>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>>>> tape. It's not a deque though.
>>>>
>>>> I think that it is a better way to implement a std::deque.
>>> Better than what?
>>
>> The complex mess of the conventional way to implement std::deque
>>
>>> There are lots of ways to implement a deque and they
>>> all have advantages and disadvantages.
>>
>> If you get maximum
>> (a) simplicity (b) speed and (c) minimum space what more could you
>> want?
>
> Correctness.
>
>>> Of course, since you have not
>>> implemented any of the deque interface, I can't tell what method might
>>> be thinking of using. Other than it will probably use two vectors.
>>>
>>
>> public:
>> tape_element& front( ) { return Left.back(); }
>> tape_element& back() { return Right.back(); }
>> void pop_front() { Left.pop_back(); }
>> void pop_back() { Right.pop_back(); }
>> void push_front(tape_element& E) { Left.push_back(E); }
>> void push_back(tape_element& E) { Right.push_back(E); }
>> void reserve(unsigned int N)
>> { Left.reserve(N); Right.reserve(N); }
>
> This is not correct. Please read a book. Or at least write a test
> program and compare with std::deque.
>
It is correct within this design:
// Tape_Type implements a two-way Turing machine tape.
// Right contains Tape_Head >= 0 values (right expansion)
// Left contains Tape_Head < 0 values (left expansion)
//
// Grows with Right.push_back() as Tape_Head increases above 0.
// Grows with Left.push_back() as Tape_Head decreases below 0.
//
// Tape_Type has functionality very similar to std::deque
// yet implements this functionality much more simply.
// This saves time and space.
//
--
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-05-13 12:08 -0400 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <6ovfK.217$hAre.157@fx08.iad> |
| In reply to | #50371 |
On 5/13/22 12:00 PM, olcott wrote:
> On 5/13/2022 5:54 AM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/12/2022 8:54 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> Its done see my new post.
>>>>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>>>>> tape. It's not a deque though.
>>>>>
>>>>> I think that it is a better way to implement a std::deque.
>>>> Better than what?
>>>
>>> The complex mess of the conventional way to implement std::deque
>>>
>>>> There are lots of ways to implement a deque and they
>>>> all have advantages and disadvantages.
>>>
>>> If you get maximum
>>> (a) simplicity (b) speed and (c) minimum space what more could you
>>> want?
>>
>> Correctness.
>>
>>>> Of course, since you have not
>>>> implemented any of the deque interface, I can't tell what method might
>>>> be thinking of using. Other than it will probably use two vectors.
>>>>
>>>
>>> public:
>>> tape_element& front( ) { return Left.back(); }
>>> tape_element& back() { return Right.back(); }
>>> void pop_front() { Left.pop_back(); }
>>> void pop_back() { Right.pop_back(); }
>>> void push_front(tape_element& E) { Left.push_back(E); }
>>> void push_back(tape_element& E) { Right.push_back(E); }
>>> void reserve(unsigned int N)
>>> { Left.reserve(N); Right.reserve(N); }
>>
>> This is not correct. Please read a book. Or at least write a test
>> program and compare with std::deque.
>>
>
> It is correct within this design:
>
> // Tape_Type implements a two-way Turing machine tape.
> // Right contains Tape_Head >= 0 values (right expansion)
> // Left contains Tape_Head < 0 values (left expansion)
> //
> // Grows with Right.push_back() as Tape_Head increases above 0.
> // Grows with Left.push_back() as Tape_Head decreases below 0.
> //
> // Tape_Type has functionality very similar to std::deque
> // yet implements this functionality much more simply.
> // This saves time and space.
> //
>
But that isn't the requirements of std:deque, that you claimed you were
improving on.
You seem to not understand the meaning of *a requirement*
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-13 17:27 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <87zgjlxusg.fsf@bsb.me.uk> |
| In reply to | #50371 |
olcott <NoOne@NoWhere.com> writes:
> On 5/13/2022 5:54 AM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/12/2022 8:54 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> Its done see my new post.
>>>>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>>>>> tape. It's not a deque though.
>>>>>
>>>>> I think that it is a better way to implement a std::deque.
>>>> Better than what?
>>>
>>> The complex mess of the conventional way to implement std::deque
>>>
>>>> There are lots of ways to implement a deque and they
>>>> all have advantages and disadvantages.
>>>
>>> If you get maximum
>>> (a) simplicity (b) speed and (c) minimum space what more could you
>>> want?
>> Correctness.
>>
>>>> Of course, since you have not
>>>> implemented any of the deque interface, I can't tell what method might
>>>> be thinking of using. Other than it will probably use two vectors.
>>>>
>>>
>>> public:
>>> tape_element& front( ) { return Left.back(); }
>>> tape_element& back() { return Right.back(); }
>>> void pop_front() { Left.pop_back(); }
>>> void pop_back() { Right.pop_back(); }
>>> void push_front(tape_element& E) { Left.push_back(E); }
>>> void push_back(tape_element& E) { Right.push_back(E); }
>>> void reserve(unsigned int N)
>>> { Left.reserve(N); Right.reserve(N); }
>> This is not correct. Please read a book. Or at least write a test
>> program and compare with std::deque.
>>
>
> It is correct within this design:
>
> // Tape_Type implements a two-way Turing machine tape.
> // Right contains Tape_Head >= 0 values (right expansion)
> // Left contains Tape_Head < 0 values (left expansion)
> //
> // Grows with Right.push_back() as Tape_Head increases above 0.
> // Grows with Left.push_back() as Tape_Head decreases below 0.
> //
> // Tape_Type has functionality very similar to std::deque
> // yet implements this functionality much more simply.
> // This saves time and space.
For goodness sake, find out what a deque is and then test our code. Do
you post in the hope that someone will point out all the bugs and the
tell you how to fit it?
--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-13 12:10 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <44CdnU8P0pZjDeP_nZ2dnUU7_81g4p2d@giganews.com> |
| In reply to | #50381 |
On 5/13/2022 11:27 AM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/13/2022 5:54 AM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/12/2022 8:54 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> Its done see my new post.
>>>>>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>>>>>> tape. It's not a deque though.
>>>>>>
>>>>>> I think that it is a better way to implement a std::deque.
>>>>> Better than what?
>>>>
>>>> The complex mess of the conventional way to implement std::deque
>>>>
>>>>> There are lots of ways to implement a deque and they
>>>>> all have advantages and disadvantages.
>>>>
>>>> If you get maximum
>>>> (a) simplicity (b) speed and (c) minimum space what more could you
>>>> want?
>>> Correctness.
>>>
>>>>> Of course, since you have not
>>>>> implemented any of the deque interface, I can't tell what method might
>>>>> be thinking of using. Other than it will probably use two vectors.
>>>>>
>>>>
>>>> public:
>>>> tape_element& front( ) { return Left.back(); }
>>>> tape_element& back() { return Right.back(); }
>>>> void pop_front() { Left.pop_back(); }
>>>> void pop_back() { Right.pop_back(); }
>>>> void push_front(tape_element& E) { Left.push_back(E); }
>>>> void push_back(tape_element& E) { Right.push_back(E); }
>>>> void reserve(unsigned int N)
>>>> { Left.reserve(N); Right.reserve(N); }
>>> This is not correct. Please read a book. Or at least write a test
>>> program and compare with std::deque.
>>>
>>
>> It is correct within this design:
>>
>> // Tape_Type implements a two-way Turing machine tape.
>> // Right contains Tape_Head >= 0 values (right expansion)
>> // Left contains Tape_Head < 0 values (left expansion)
>> //
>> // Grows with Right.push_back() as Tape_Head increases above 0.
>> // Grows with Left.push_back() as Tape_Head decreases below 0.
>> //
>> // Tape_Type has functionality very similar to std::deque
>> // yet implements this functionality much more simply.
>> // This saves time and space.
>
> For goodness sake, find out what a deque is and then test our code. Do
> you post in the hope that someone will point out all the bugs and the
> tell you how to fit it?
>
The std::deque stuff was a side issue.
The key issue is how it performs as Tape_Type compared to your
std::string method.
Tape_Type::reserve() may make mine much faster for you test code.
--
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-05-13 13:20 -0400 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <PrwfK.4943$x1Wf.3197@fx10.iad> |
| In reply to | #50389 |
On 5/13/22 1:10 PM, olcott wrote:
> On 5/13/2022 11:27 AM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/13/2022 5:54 AM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/12/2022 8:54 PM, Ben wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> Its done see my new post.
>>>>>>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>>>>>>> tape. It's not a deque though.
>>>>>>>
>>>>>>> I think that it is a better way to implement a std::deque.
>>>>>> Better than what?
>>>>>
>>>>> The complex mess of the conventional way to implement std::deque
>>>>>
>>>>>> There are lots of ways to implement a deque and they
>>>>>> all have advantages and disadvantages.
>>>>>
>>>>> If you get maximum
>>>>> (a) simplicity (b) speed and (c) minimum space what more could you
>>>>> want?
>>>> Correctness.
>>>>
>>>>>> Of course, since you have not
>>>>>> implemented any of the deque interface, I can't tell what method
>>>>>> might
>>>>>> be thinking of using. Other than it will probably use two vectors.
>>>>>>
>>>>>
>>>>> public:
>>>>> tape_element& front( ) { return Left.back(); }
>>>>> tape_element& back() { return Right.back(); }
>>>>> void pop_front() { Left.pop_back(); }
>>>>> void pop_back() { Right.pop_back(); }
>>>>> void push_front(tape_element& E) { Left.push_back(E); }
>>>>> void push_back(tape_element& E) { Right.push_back(E); }
>>>>> void reserve(unsigned int N)
>>>>> { Left.reserve(N); Right.reserve(N); }
>>>> This is not correct. Please read a book. Or at least write a test
>>>> program and compare with std::deque.
>>>>
>>>
>>> It is correct within this design:
>>>
>>> // Tape_Type implements a two-way Turing machine tape.
>>> // Right contains Tape_Head >= 0 values (right expansion)
>>> // Left contains Tape_Head < 0 values (left expansion)
>>> //
>>> // Grows with Right.push_back() as Tape_Head increases above 0.
>>> // Grows with Left.push_back() as Tape_Head decreases below 0.
>>> //
>>> // Tape_Type has functionality very similar to std::deque
>>> // yet implements this functionality much more simply.
>>> // This saves time and space.
>>
>> For goodness sake, find out what a deque is and then test our code. Do
>> you post in the hope that someone will point out all the bugs and the
>> tell you how to fit it?
>>
>
> The std::deque stuff was a side issue.
Then why did YOU insist that you were correct that your implementation
was "a better deque then the standard deque implementation"?
This shows that you are prone to make assertions with actual "proof"
that they are true, and that you are not a reliable source.
Yes, maybe for the sub-case of a Turing machine (which only needs to add
to the tape, and never actually needs to remove things from the tape) it
is faster than the standard deque, but has more "user" code to
implement, so isn't unconditionally simpler.
>
> The key issue is how it performs as Tape_Type compared to your
> std::string method.
>
> Tape_Type::reserve() may make mine much faster for you test code.
>
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-05-11 22:07 -0400 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <_ZZeK.55$C7G6.31@fx46.iad> |
| In reply to | #50267 |
On 5/11/22 9:37 PM, olcott wrote:
> 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.
>
>
>
Clearly you don't understand what was being talked about in the "two
stack" method, as the Tape Head is always the last element of a specifed
vector (I beleive traditionally the right).
Moving to the left is just taking the last element off the left vector
and putting it at the end of the right vector, and moving to the right,
is taking the last element off the right vector and putting it at the
end of the left vector.
(In eather case, if the source vector is empty, just put a 'blank tape'
symbol on the destination tape.
As an example, a tape with the symbols 1 to 9 in order (assending left
to right), with the tape head on the 5 would be
Left: 1 2 3 4
Right: 9 8 7 6 5
Note, the Right vector is storing its tape "reversed" from normal
reading order, so its 'businesss' end is the free end that is cheap to
add to and remove from.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-10 21:06 -0500 |
| Message-ID | <ecadnXdd_YWih-b_nZ2dnUU7_8zNnZ2d@giganews.com> |
| In reply to | #50207 |
On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>> On Tue, 10 May 2022 16:41:28 +0100
>> Ben <ben.u...@bsb.me.uk> wrote:
>>
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>
>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>>
>>>>>>>>>>>>> My code is utterly trivial. The tape is a std::string to
>>>>>>>>>>>>> which I assign the input. All that happens after that is
>>>>>>>>>>>>> that tape[head] is assigned to, and the string is grown by
>>>>>>>>>>>>> one blank, either at the front or the back, if the tape
>>>>>>>>>>>>> movement requires it.
>>>>>>>>>>>>
>>>>>>>>>>>> Conventionally tapes have an actual beginning, yet no fixed
>>>>>>>>>>>> end.
>>>>>>>>>>>
>>>>>>>>>>> No.
>>>>>>>>>>
>>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>>
>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>> however, that that is not the case.
>>>>>>>>
>>>>>>>> How would you define conventional?
>>>>>>>
>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>
>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>
>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>> that.
>>>>>>>
>>>>>>> From a technical point of view, double-open is clearly
>>>>>>> preferable as it removes a special case with no technical
>>>>>>> down-side.
>>>>>> There's a technical downside if you implement the tape in the
>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>> fast to append characters to the buffer's end.
>>>>> I meant for the theory of such machines. It's the theory and the
>>>>> theorems that will dictate which style an authors chooses and
>>>>> there's no down-side in that context.
>>>>>
>>>>>> There's usually spare memory there in the system, so
>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>> field.
>>>>> If you do the resizing right, the same is true of push_front().
>>>>>
>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>> by a move for the entire buffer.
>>>>> Every now and then, your realloc will need an extra move, but
>>>>> that's a cost that will be amortised if you do the usual
>>>>> exponential resizing.
>>>>>> There are ways round this, of course, but you have to know what
>>>>>> you are doing, and it's not as easy to write.
>>>>>
>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>> other or even both ends seems to me to be utterly trivial.
>>>>
>>>> https://en.cppreference.com/w/cpp/container/deque
>>>> push_back adds an element to the end
>>>> push_front inserts an element to the beginning
>>>
>>> I think everyone here knows that.
>>>
>>> Using std::deque was suggested before (by Jeff I think), but at nearly
>>> 200 million steps a second, I didn't think there was much room for a
>>> speed-up.
>>>
>>> I've just tried it, and using std::deque rather than std::string slows
>>> my implementation down to 106 million steps a second, and it doesn't
>>> simplify the logic at all. In fact, the few places where you really
>>> want a string get a bit more fiddly.
>>>
>>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>>> champions.
>> std::string (or std::vector) will likely win for small N and std::deque
>> for large N as far as push_front is concerned.
>>
>> /Flibble
>
> If you are not actually implementing a machine replacing the tape by a pair of
> stacks is attractive. Actually you replace the tape by three things - two stacks
> (called for example left and right) and a single focus cell.
>
> But none of this is really needed. We don't really need TM's for anything
> practical.
std::vector essentially <is> a stack.
I consider your solution optimal. Here is the first part of its
implementation:
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.
--
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 00:11 +0100 |
| Message-ID | <87h75xkmor.fsf@bsb.me.uk> |
| In reply to | #50203 |
Mr Flibble <flibble@reddwarf.jmc> writes: > On Tue, 10 May 2022 16:41:28 +0100 > Ben <ben.usenet@bsb.me.uk> wrote: > >> olcott <NoOne@NoWhere.com> writes: >> >> > On 5/10/2022 6:23 AM, Ben wrote: >> >> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >> >> >> >>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: >> >>>> olcott <No...@NoWhere.com> writes: >> >>>> >> >>>>> On 5/9/2022 7:13 PM, Ben wrote: >> >>>>>> olcott <No...@NoWhere.com> writes: >> >>>>>> >> >>>>>>> On 5/9/2022 5:14 PM, Ben wrote: >> >>>>>>>> olcott <No...@NoWhere.com> writes: >> >>>>>>>> >> >>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote: >> >>>>>>>> >> >>>>>>>>>> My code is utterly trivial. The tape is a std::string to >> >>>>>>>>>> which I assign the input. All that happens after that is >> >>>>>>>>>> that tape[head] is assigned to, and the string is grown by >> >>>>>>>>>> one blank, either at the front or the back, if the tape >> >>>>>>>>>> movement requires it. >> >>>>>>>>> >> >>>>>>>>> Conventionally tapes have an actual beginning, yet no fixed >> >>>>>>>>> end. >> >>>>>>>> >> >>>>>>>> No. >> >>>>>>> >> >>>>>>> Sipser and Kozen agree with me, Linz agrees with you. >> >>>>>> >> >>>>>> None of these authors say what is "conventional". What is >> >>>>>> certain is that if there were a convention, an author not >> >>>>>> using that convention should say as much. You'll find, >> >>>>>> however, that that is not the case. >> >>>>> >> >>>>> How would you define conventional? >> >>>> >> >>>> "the accepted or traditional method of doing something" >> >>>> >> >>>>> The most typical use is one way unlimited, right? >> >>>> >> >>>> I don't know. I know it's not a widely agreed convention, but >> >>>> what it "typical" is hard to assess. I think double-open is more >> >>>> commonly used in modern presentations, but the only real way to >> >>>> know would be to do a survey and I don't think the topic merits >> >>>> that. >> >>>> >> >>>> From a technical point of view, double-open is clearly >> >>>> preferable as it removes a special case with no technical >> >>>> down-side. >> >>> There's a technical downside if you implement the tape in the >> >>> obvious way, as a dynamic buffer. Most languages make it quite >> >>> fast to append characters to the buffer's end. >> >> I meant for the theory of such machines. It's the theory and the >> >> theorems that will dictate which style an authors chooses and >> >> there's no down-side in that context. >> >> >> >>> There's usually spare memory there in the system, so >> >>> the push_back() operation is just a case of incrementing a size >> >>> field. >> >> If you do the resizing right, the same is true of push_front(). >> >> >> >>> push_front(), however, generally requires a push_back, followed >> >>> by a move for the entire buffer. >> >> Every now and then, your realloc will need an extra move, but >> >> that's a cost that will be amortised if you do the usual >> >> exponential resizing. >> >>> There are ways round this, of course, but you have to know what >> >>> you are doing, and it's not as easy to write. >> >> >> >> Gosh, you have a low opinion of what's generally understood! >> >> Maybe I have too high an opinion, but growing a buffer at one or >> >> other or even both ends seems to me to be utterly trivial. >> > >> > https://en.cppreference.com/w/cpp/container/deque >> > push_back adds an element to the end >> > push_front inserts an element to the beginning >> >> I think everyone here knows that. >> >> Using std::deque was suggested before (by Jeff I think), but at nearly >> 200 million steps a second, I didn't think there was much room for a >> speed-up. >> >> I've just tried it, and using std::deque rather than std::string slows >> my implementation down to 106 million steps a second, and it doesn't >> simplify the logic at all. In fact, the few places where you really >> want a string get a bit more fiddly. >> >> Mind you, the speed is almost irrelevant unless you are hunting for BB >> champions. > > std::string (or std::vector) will likely win for small N and std::deque > for large N as far as push_front is concerned. I'm sure that's true. std::string /could/ be made fast for inserts at position 0 (there is no push_front for a string) but I doubt that case has been optimised. But very long tapes will be rare though. And for them to occur there has to be quite of lots going back and forth as well so I'm not sure if the tape growth cost will ever dominate. My test case (BB(5)) ends up with a resulting tape of 12,289 characters, and all but 45 of those were added at the front. Of course, 12,289 is not really a long string, and the vast majority of moves happened away form the "ends". -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-10 19:41 -0500 |
| Message-ID | <8vydnYgTy7nRm-b_nZ2dnUU7_8xh4p2d@giganews.com> |
| In reply to | #50203 |
On 5/10/2022 1:01 PM, Mr Flibble wrote: > On Tue, 10 May 2022 16:41:28 +0100 > Ben <ben.usenet@bsb.me.uk> wrote: > >> olcott <NoOne@NoWhere.com> writes: >> >>> On 5/10/2022 6:23 AM, Ben wrote: >>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >>>> >>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: >>>>>> olcott <No...@NoWhere.com> writes: >>>>>> >>>>>>> On 5/9/2022 7:13 PM, Ben wrote: >>>>>>>> olcott <No...@NoWhere.com> writes: >>>>>>>> >>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote: >>>>>>>>>> olcott <No...@NoWhere.com> writes: >>>>>>>>>> >>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote: >>>>>>>>>> >>>>>>>>>>>> My code is utterly trivial. The tape is a std::string to >>>>>>>>>>>> which I assign the input. All that happens after that is >>>>>>>>>>>> that tape[head] is assigned to, and the string is grown by >>>>>>>>>>>> one blank, either at the front or the back, if the tape >>>>>>>>>>>> movement requires it. >>>>>>>>>>> >>>>>>>>>>> Conventionally tapes have an actual beginning, yet no fixed >>>>>>>>>>> end. >>>>>>>>>> >>>>>>>>>> No. >>>>>>>>> >>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you. >>>>>>>> >>>>>>>> None of these authors say what is "conventional". What is >>>>>>>> certain is that if there were a convention, an author not >>>>>>>> using that convention should say as much. You'll find, >>>>>>>> however, that that is not the case. >>>>>>> >>>>>>> How would you define conventional? >>>>>> >>>>>> "the accepted or traditional method of doing something" >>>>>> >>>>>>> The most typical use is one way unlimited, right? >>>>>> >>>>>> I don't know. I know it's not a widely agreed convention, but >>>>>> what it "typical" is hard to assess. I think double-open is more >>>>>> commonly used in modern presentations, but the only real way to >>>>>> know would be to do a survey and I don't think the topic merits >>>>>> that. >>>>>> >>>>>> From a technical point of view, double-open is clearly >>>>>> preferable as it removes a special case with no technical >>>>>> down-side. >>>>> There's a technical downside if you implement the tape in the >>>>> obvious way, as a dynamic buffer. Most languages make it quite >>>>> fast to append characters to the buffer's end. >>>> I meant for the theory of such machines. It's the theory and the >>>> theorems that will dictate which style an authors chooses and >>>> there's no down-side in that context. >>>> >>>>> There's usually spare memory there in the system, so >>>>> the push_back() operation is just a case of incrementing a size >>>>> field. >>>> If you do the resizing right, the same is true of push_front(). >>>> >>>>> push_front(), however, generally requires a push_back, followed >>>>> by a move for the entire buffer. >>>> Every now and then, your realloc will need an extra move, but >>>> that's a cost that will be amortised if you do the usual >>>> exponential resizing. >>>>> There are ways round this, of course, but you have to know what >>>>> you are doing, and it's not as easy to write. >>>> >>>> Gosh, you have a low opinion of what's generally understood! >>>> Maybe I have too high an opinion, but growing a buffer at one or >>>> other or even both ends seems to me to be utterly trivial. >>> >>> https://en.cppreference.com/w/cpp/container/deque >>> push_back adds an element to the end >>> push_front inserts an element to the beginning >> >> I think everyone here knows that. >> >> Using std::deque was suggested before (by Jeff I think), but at nearly >> 200 million steps a second, I didn't think there was much room for a >> speed-up. >> >> I've just tried it, and using std::deque rather than std::string slows >> my implementation down to 106 million steps a second, and it doesn't >> simplify the logic at all. In fact, the few places where you really >> want a string get a bit more fiddly. >> >> Mind you, the speed is almost irrelevant unless you are hunting for BB >> champions. > > std::string (or std::vector) will likely win for small N and std::deque > for large N as far as push_front is concerned. > > /Flibble > David kleinecke's solution is a much more efficient and simpler way to implement push_back() and push_front() than std::deque that also has none of the pitfalls such as: https://www.cplusplus.com/reference/deque/deque/push_front/ All iterators related to this container are invalidated. -- 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 | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-10 06:53 -0500 |
| Message-ID | <TKmdnVKs6o7Pz-f_nZ2dnUU7_81g4p2d@giganews.com> |
| In reply to | #50186 |
On 5/10/2022 5:46 AM, Malcolm McLean wrote: > On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote: >> olcott <No...@NoWhere.com> writes: >> >>> On 5/9/2022 7:13 PM, Ben wrote: >>>> olcott <No...@NoWhere.com> writes: >>>> >>>>> On 5/9/2022 5:14 PM, Ben wrote: >>>>>> olcott <No...@NoWhere.com> writes: >>>>>> >>>>>>> On 5/8/2022 1:27 PM, Ben wrote: >>>>>> >>>>>>>> My code is utterly trivial. The tape is a std::string to which I assign >>>>>>>> the input. All that happens after that is that tape[head] is assigned >>>>>>>> to, and the string is grown by one blank, either at the front or the >>>>>>>> back, if the tape movement requires it. >>>>>>> >>>>>>> Conventionally tapes have an actual beginning, yet no fixed end. >>>>>> >>>>>> No. >>>>> >>>>> Sipser and Kozen agree with me, Linz agrees with you. >>>> >>>> None of these authors say what is "conventional". What is certain is >>>> that if there were a convention, an author not using that convention >>>> should say as much. You'll find, however, that that is not the case. >>> >>> How would you define conventional? >> "the accepted or traditional method of doing something" >>> The most typical use is one way unlimited, right? >> I don't know. I know it's not a widely agreed convention, but what it >> "typical" is hard to assess. I think double-open is more commonly used in >> modern presentations, but the only real way to know would be to do a >> survey and I don't think the topic merits that. >> >> From a technical point of view, double-open is clearly preferable as it >> removes a special case with no technical down-side. >> > There's a technical downside if you implement the tape in the obvious way, > as a dynamic buffer. Most languages make it quite fast to append characters > to the buffer's end. There's usually spare memory there in the system, so > the push_back() operation is just a case of incrementing a size field. > push_front(), however, generally requires a push_back, followed by a move > for the entire buffer. > > There are ways round this, of course, but you have to know what you are doing, > and it's not as easy to write. , > > https://en.cppreference.com/w/cpp/container/deque push_back adds an element to the end push_front inserts an element to the beginning -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-07 21:04 -0500 |
| Message-ID | <B4Cdnb1LsNSkuOr_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #49975 |
On 5/7/2022 5:21 PM, Ben wrote:
> olcott <polcott2@gmail.com> writes:
>
>> On 5/6/2022 7:54 PM, Ben wrote:
>>> olcott <polcott2@gmail.com> writes:
>>>
>>>> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
>>>
>>>>>>> olcott <polc...@gmail.com> wrote:
>>>
>>>>>>>> struct Quintuple
>>>>>>>> {
>>>>>>>> u32 state;
>>>>>>>> u32 symbol;
>>>>>>>> u32 write_symbol;
>>>>>>>> u32 next_state;
>>>>>>>> u8 Tape_Head_Move;
>>>>>>>> };
>>>>>>>>
>>>>>>>> class Quintuple_List
>>>>>>>> {
>>>>>>>> std::set<Quintuple> list;
>>>>>>>> NextState(int next_state, int current_input)
>>>>>>>> {
>>>>>>>> Quintuple QT(next_state, current_input);
>>>>>>>> return list.find(QT);
>>>>>>>> };
>>>>>>>> }
>>>
>>>>> ThIs looks along the right lines.
>>>>> The quintuples need to be indexed by the current state and the current input,
>>>>> and a set, properly specified, will achieve this.
>>>>
>>>> Ben didn't seem to understand this.
>>> Your code sketch just won't work as you have it now.
>>
>> Not when you erase the most important part:
>>
>> bool Quintuple_List::transition_function(std::set<Quintuple>::iterator& current_quintuple)
>> {
>> unsigned int next_state = current_quintuple->next_state;
>> unsigned int current_input = Tape[Tape_Head];
>> std::set<Quintuple>::iterator next_quintuple;
>>
>> Tape[Tape_Head] = current_quintuple->write_symbol;
>> if (toupper(current_quintuple->tape_head_move) == 'L')
>> Tape_Head--; // Left
>> else
>> Tape_Head++; // Right
>>
>> next_quintuple = NextState(next_state, current_input);
>> if (next_quintuple == States.end())
>> return false;
>> current_quintuple = next_quintuple;
>> return true;
>> }
>>
>> If you also assume that I got All the missing pieces correctly then it
>> should work just fine.
>
> As written, it can't, for reasons I've pointed out before (summary:
> assigned to local, uses the wrong symbol to pick the next rule).
>
> But it still also uses bad names. It's a big help that you've fixed
> some of the names, but NextState returns (an iterator to) a quintuple,
> not a state, and the collection States is a collections of quintuples.
>
>>> Do you know how to
>>> get it to work? The result will not be a natural use of a set.
>>
>> The natural use of a std::set it to look things up very quickly with
>> no need for a linear search.
>
> That's not the point. You need to play a little trick or a set is the
> just the wrong collection.
>
The TM interpreter uses linear search, I hate that, it doesn't scale.
>> I decided to make my system exactly compatible with these code samples:
>> http://www.lns.mit.edu/~dsw/turing/examples/examples.html
>
> Here's an interesting test case that's useful for timing and so on:
>
> A_1RB
> A11LC
> B_1RC
> B11RB
> C_1RD
> C1_LE
> D_1LA
> D11LD
> E_1RH
> E1_LA
>
> You will need to add a '(' for DSW compatibility. Also, note that my
> interpreter uses _ as the tape's blank symbol. Change all _s to an
> actual spaces if that's what you use.
>
> This is (as far as I know) the current BB(5) champion. It runs for more
> that 47 million steps before halting.
>
--
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-05-08 07:30 -0400 |
| Message-ID | <KRNdK.6818$Jex1.1781@fx35.iad> |
| In reply to | #50008 |
On 5/7/22 10:04 PM, olcott wrote:
> On 5/7/2022 5:21 PM, Ben wrote:
>> olcott <polcott2@gmail.com> writes:
>>
>>> On 5/6/2022 7:54 PM, Ben wrote:
>>>> olcott <polcott2@gmail.com> writes:
>>>>
>>>>> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
>>>>
>>>>>>>> olcott <polc...@gmail.com> wrote:
>>>>
>>>>>>>>> struct Quintuple
>>>>>>>>> {
>>>>>>>>> u32 state;
>>>>>>>>> u32 symbol;
>>>>>>>>> u32 write_symbol;
>>>>>>>>> u32 next_state;
>>>>>>>>> u8 Tape_Head_Move;
>>>>>>>>> };
>>>>>>>>>
>>>>>>>>> class Quintuple_List
>>>>>>>>> {
>>>>>>>>> std::set<Quintuple> list;
>>>>>>>>> NextState(int next_state, int current_input)
>>>>>>>>> {
>>>>>>>>> Quintuple QT(next_state, current_input);
>>>>>>>>> return list.find(QT);
>>>>>>>>> };
>>>>>>>>> }
>>>>
>>>>>> ThIs looks along the right lines.
>>>>>> The quintuples need to be indexed by the current state and the
>>>>>> current input,
>>>>>> and a set, properly specified, will achieve this.
>>>>>
>>>>> Ben didn't seem to understand this.
>>>> Your code sketch just won't work as you have it now.
>>>
>>> Not when you erase the most important part:
>>>
>>> bool
>>> Quintuple_List::transition_function(std::set<Quintuple>::iterator&
>>> current_quintuple)
>>> {
>>> unsigned int next_state = current_quintuple->next_state;
>>> unsigned int current_input = Tape[Tape_Head];
>>> std::set<Quintuple>::iterator next_quintuple;
>>>
>>> Tape[Tape_Head] = current_quintuple->write_symbol;
>>> if (toupper(current_quintuple->tape_head_move) == 'L')
>>> Tape_Head--; // Left
>>> else
>>> Tape_Head++; // Right
>>>
>>> next_quintuple = NextState(next_state, current_input);
>>> if (next_quintuple == States.end())
>>> return false;
>>> current_quintuple = next_quintuple;
>>> return true;
>>> }
>>>
>>> If you also assume that I got All the missing pieces correctly then it
>>> should work just fine.
>>
>> As written, it can't, for reasons I've pointed out before (summary:
>> assigned to local, uses the wrong symbol to pick the next rule).
>>
>> But it still also uses bad names. It's a big help that you've fixed
>> some of the names, but NextState returns (an iterator to) a quintuple,
>> not a state, and the collection States is a collections of quintuples.
>>
>>>> Do you know how to
>>>> get it to work? The result will not be a natural use of a set.
>>>
>>> The natural use of a std::set it to look things up very quickly with
>>> no need for a linear search.
>>
>> That's not the point. You need to play a little trick or a set is the
>> just the wrong collection.
>>
>
> The TM interpreter uses linear search, I hate that, it doesn't scale.
That means it is using the wrong data structure.
I would probably just use an array for the rule storage, having an array
of structures of Next State, Replacement Charactrer, Tape Motion, and
index it on Current State and Current Tape Character.
Then the processing loop is just a tight loop like:
curr_char = tape[index]
next_state = rules[current_state][curr_char].next_state;
tape[index] = rules[current_state][curr_char].new_char;
index += rules[current_state][curr_char].tape_incr;
current_state = next_state;
Add an end test, trace logging, and something to read in the rules and
tape, and you are done.
>
>>> I decided to make my system exactly compatible with these code samples:
>>> http://www.lns.mit.edu/~dsw/turing/examples/examples.html
>>
>> Here's an interesting test case that's useful for timing and so on:
>>
>> A_1RB
>> A11LC
>> B_1RC
>> B11RB
>> C_1RD
>> C1_LE
>> D_1LA
>> D11LD
>> E_1RH
>> E1_LA
>>
>> You will need to add a '(' for DSW compatibility. Also, note that my
>> interpreter uses _ as the tape's blank symbol. Change all _s to an
>> actual spaces if that's what you use.
>>
>> This is (as far as I know) the current BB(5) champion. It runs for more
>> that 47 million steps before halting.
>>
>
>
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-08 14:46 +0100 |
| Message-ID | <87zgjst9v9.fsf@bsb.me.uk> |
| In reply to | #50008 |
olcott <NoOne@NoWhere.com> writes: > The TM interpreter uses linear search, I hate that, it doesn't scale. What do you use linear search for? I thought the key structure you used was a std::set. -- Ben. "le génie humain a des limites, quand la bêtise humaine n’en a pas" Alexandre Dumas (fils)
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-09 10:19 -0500 |
| Message-ID | <0YCdnaiQZ9yHrOT_nZ2dnUU7_8xQAAAA@giganews.com> |
| In reply to | #50029 |
On 5/8/2022 8:46 AM, Ben wrote: > olcott <NoOne@NoWhere.com> writes: > >> The TM interpreter uses linear search, I hate that, it doesn't scale. > > What do you use linear search for? I thought the key structure you used > was a std::set. > David S. Woodruff's TM interpretor uses linear search. -- 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-07 01:22 +0100 |
| Message-ID | <87sfpmyywj.fsf@bsb.me.uk> |
| In reply to | #49897 |
Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > ThIs looks along the right lines. > The quintuples need to be indexed by the current state and the current > input, and a set, properly specified, will achieve this. How? std::set is not the right container for this. > You can probably get away with chars for the symbols. Few people work > with Turing machines with a large number of symbols. ACK. It's painful to write TMs with more than even a handful of distinct symbols. There may be some value in using something like wchar_t so that fancy symbols matching those seen in some of the papers can be used, but that's a bit of a stretch. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <polcott2@gmail.com> |
|---|---|
| Date | 2022-05-06 19:38 -0500 |
| Message-ID | <t54f2k$mqp$1@dont-email.me> |
| In reply to | #49910 |
On 5/6/2022 7:22 PM, Ben wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> ThIs looks along the right lines.
>> The quintuples need to be indexed by the current state and the current
>> input, and a set, properly specified, will achieve this.
>
> How? std::set is not the right container for this.
std::set::find()
std::set<Quintuple> States;
std::vector<unsigned char> Tape;
void insert(const Quintuple& QT){ States.insert(QT); };
std::set<Quintuple>::iterator
NextState(int current_input, int next_state)
{
Quintuple QT(current_input, next_state);
return States.find(QT);
}
>
>> You can probably get away with chars for the symbols. Few people work
>> with Turing machines with a large number of symbols.
>
The TM interpreter uses ASCII text as its tape elements.
For compatibility I will do the same, that way I can directly execute
all of his same filename.tm examples.
> ACK. It's painful to write TMs with more than even a handful of
> distinct symbols. There may be some value in using something like
> wchar_t so that fancy symbols matching those seen in some of the papers
> can be used, but that's a bit of a stretch.
>
One need to use more than one or two {'0', '1'} of the possible tape
elements.
--
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 9 of 10 — ← Prev page 1 … 7 8 [9] 10 Next page →
Back to top | Article view | comp.theory
csiph-web