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 1 of 10 [1] 2 3 … 10 Next page →
| From | olcott <polcott2@gmail.com> |
|---|---|
| Date | 2022-05-06 15:53 -0500 |
| Subject | Validating that the implementation meets the spec for TM transition function |
| Message-ID | <t541t8$upu$1@dont-email.me> |
A turing machine is a model of a computer. It has a finite number of
states, and it is capable of reading and modifying a tape. A turing
machine program consists of a list of 'quintuples', each one of which is
a five-symbol turing machine instruction. For example, the quintuple
'SCcsm' is executed by the machine if it is in state 'S' and is reading
the symbol 'C' on the tape. In that case, the instruction causes the
machine to make a transition to state 's' and to overwrite the symbol
'C' on the tape with the symbol 'c'. The last operation it performs
under this instruction is to move the tape reading head one symbol to
the left or right according to whether 'm' is 'l' or 'r'.
http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
For example, the quintuple 'SCcsm' is executed by the machine:
If it is in state 'S' and is reading the symbol 'C' on the tape then
(a) make a transition to state 's'.
(b) overwrite the symbol 'C' on the tape with the symbol 'c'.
// Must do this before transition to state 's' or we lose 'c' from S.
(c) move the tape reading head one symbol to the left or right
according to whether 'm' is 'l' or 'r'.
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);
};
}
bool transition_function(std::set<Quintuple>::iterator& current_quintuple)
{
u32 next_state = current_quintuple->next_state;
u32 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 == Quintuple_List.end())
return false;
current_quintuple = next_quintuple;
return true;
}
--
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] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2022-05-06 22:08 +0100 |
| Message-ID | <20220506220822.000061d0@reddwarf.jmc> |
| In reply to | #49891 |
On Fri, 6 May 2022 15:53:58 -0500
olcott <polcott2@gmail.com> wrote:
> A turing machine is a model of a computer. It has a finite number of
> states, and it is capable of reading and modifying a tape. A turing
> machine program consists of a list of 'quintuples', each one of which
> is a five-symbol turing machine instruction. For example, the
> quintuple 'SCcsm' is executed by the machine if it is in state 'S'
> and is reading the symbol 'C' on the tape. In that case, the
> instruction causes the machine to make a transition to state 's' and
> to overwrite the symbol 'C' on the tape with the symbol 'c'. The
> last operation it performs under this instruction is to move the tape
> reading head one symbol to the left or right according to whether 'm'
> is 'l' or 'r'. http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
>
> For example, the quintuple 'SCcsm' is executed by the machine:
>
> If it is in state 'S' and is reading the symbol 'C' on the tape then
> (a) make a transition to state 's'.
> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
> // Must do this before transition to state 's' or we lose 'c'
> from S. (c) move the tape reading head one symbol to the left or right
> according to whether 'm' is 'l' or 'r'.
>
> 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);
> };
> }
>
> bool transition_function(std::set<Quintuple>::iterator&
> current_quintuple) {
> u32 next_state = current_quintuple->next_state;
> u32 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 == Quintuple_List.end())
> return false;
> current_quintuple = next_quintuple;
> return true;
> }
If you are going to use C++ for this then at least create proper
abstractions rather than a struct containing anonymous types. At the
very least created named typedefs for things rather than the anonymous
'u32' etc.
/Flibble
[toc] | [prev] | [next] | [standalone]
| From | olcott <polcott2@gmail.com> |
|---|---|
| Date | 2022-05-06 16:25 -0500 |
| Message-ID | <t543p9$d1h$1@dont-email.me> |
| In reply to | #49893 |
On 5/6/2022 4:08 PM, Mr Flibble wrote:
> On Fri, 6 May 2022 15:53:58 -0500
> olcott <polcott2@gmail.com> wrote:
>
>> A turing machine is a model of a computer. It has a finite number of
>> states, and it is capable of reading and modifying a tape. A turing
>> machine program consists of a list of 'quintuples', each one of which
>> is a five-symbol turing machine instruction. For example, the
>> quintuple 'SCcsm' is executed by the machine if it is in state 'S'
>> and is reading the symbol 'C' on the tape. In that case, the
>> instruction causes the machine to make a transition to state 's' and
>> to overwrite the symbol 'C' on the tape with the symbol 'c'. The
>> last operation it performs under this instruction is to move the tape
>> reading head one symbol to the left or right according to whether 'm'
>> is 'l' or 'r'. http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
>>
>> For example, the quintuple 'SCcsm' is executed by the machine:
>>
>> If it is in state 'S' and is reading the symbol 'C' on the tape then
>> (a) make a transition to state 's'.
>> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
>> // Must do this before transition to state 's' or we lose 'c'
>> from S. (c) move the tape reading head one symbol to the left or right
>> according to whether 'm' is 'l' or 'r'.
>>
>> 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);
>> };
>> }
>>
>> bool transition_function(std::set<Quintuple>::iterator&
>> current_quintuple) {
>> u32 next_state = current_quintuple->next_state;
>> u32 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 == Quintuple_List.end())
>> return false;
>> current_quintuple = next_quintuple;
>> return true;
>> }
>
> If you are going to use C++ for this then at least create proper
> abstractions rather than a struct containing anonymous types. At the
It is not a struct containing anonymous types they are fixed width
unsigned integers. I could have just used int and unsigned char, I will
change it.
> very least created named typedefs for things rather than the anonymous
> 'u32' etc.
>
> /Flibble
>
>
It is all in a pair of C++ classes, I didn't want to show all of the
pages, (1) They are not done yet (2) The distract attention way from the
only function that I need reviewed.
--
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-06 22:29 +0100 |
| Message-ID | <20220506222911.00000dd9@reddwarf.jmc> |
| In reply to | #49894 |
On Fri, 6 May 2022 16:25:58 -0500
olcott <polcott2@gmail.com> wrote:
> On 5/6/2022 4:08 PM, Mr Flibble wrote:
> > On Fri, 6 May 2022 15:53:58 -0500
> > olcott <polcott2@gmail.com> wrote:
> >
> >> A turing machine is a model of a computer. It has a finite number
> >> of states, and it is capable of reading and modifying a tape. A
> >> turing machine program consists of a list of 'quintuples', each
> >> one of which is a five-symbol turing machine instruction. For
> >> example, the quintuple 'SCcsm' is executed by the machine if it is
> >> in state 'S' and is reading the symbol 'C' on the tape. In that
> >> case, the instruction causes the machine to make a transition to
> >> state 's' and to overwrite the symbol 'C' on the tape with the
> >> symbol 'c'. The last operation it performs under this instruction
> >> is to move the tape reading head one symbol to the left or right
> >> according to whether 'm' is 'l' or 'r'.
> >> http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
> >>
> >> For example, the quintuple 'SCcsm' is executed by the machine:
> >>
> >> If it is in state 'S' and is reading the symbol 'C' on the tape
> >> then (a) make a transition to state 's'.
> >> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
> >> // Must do this before transition to state 's' or we lose
> >> 'c' from S. (c) move the tape reading head one symbol to the left
> >> or right according to whether 'm' is 'l' or 'r'.
> >>
> >> 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);
> >> };
> >> }
> >>
> >> bool transition_function(std::set<Quintuple>::iterator&
> >> current_quintuple) {
> >> u32 next_state = current_quintuple->next_state;
> >> u32 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 == Quintuple_List.end())
> >> return false;
> >> current_quintuple = next_quintuple;
> >> return true;
> >> }
> >
> > If you are going to use C++ for this then at least create proper
> > abstractions rather than a struct containing anonymous types. At the
>
> It is not a struct containing anonymous types they are fixed width
> unsigned integers. I could have just used int and unsigned char, I
> will change it.
It is obvious that they are fixed width unsigned integers but that
doesn't tell us anything about what they actually are apart from being
represented as integers, 'state_t' is more meaningful than 'u32':
using state_t = std::uint32_t;
/Flibble
[toc] | [prev] | [next] | [standalone]
| From | olcott <polcott2@gmail.com> |
|---|---|
| Date | 2022-05-06 17:08 -0500 |
| Message-ID | <t5469b$115$1@dont-email.me> |
| In reply to | #49895 |
On 5/6/2022 4:29 PM, Mr Flibble wrote:
> On Fri, 6 May 2022 16:25:58 -0500
> olcott <polcott2@gmail.com> wrote:
>
>> On 5/6/2022 4:08 PM, Mr Flibble wrote:
>>> On Fri, 6 May 2022 15:53:58 -0500
>>> olcott <polcott2@gmail.com> wrote:
>>>
>>>> A turing machine is a model of a computer. It has a finite number
>>>> of states, and it is capable of reading and modifying a tape. A
>>>> turing machine program consists of a list of 'quintuples', each
>>>> one of which is a five-symbol turing machine instruction. For
>>>> example, the quintuple 'SCcsm' is executed by the machine if it is
>>>> in state 'S' and is reading the symbol 'C' on the tape. In that
>>>> case, the instruction causes the machine to make a transition to
>>>> state 's' and to overwrite the symbol 'C' on the tape with the
>>>> symbol 'c'. The last operation it performs under this instruction
>>>> is to move the tape reading head one symbol to the left or right
>>>> according to whether 'm' is 'l' or 'r'.
>>>> http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
>>>>
>>>> For example, the quintuple 'SCcsm' is executed by the machine:
>>>>
>>>> If it is in state 'S' and is reading the symbol 'C' on the tape
>>>> then (a) make a transition to state 's'.
>>>> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
>>>> // Must do this before transition to state 's' or we lose
>>>> 'c' from S. (c) move the tape reading head one symbol to the left
>>>> or right according to whether 'm' is 'l' or 'r'.
>>>>
>>>> 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);
>>>> };
>>>> }
>>>>
>>>> bool transition_function(std::set<Quintuple>::iterator&
>>>> current_quintuple) {
>>>> u32 next_state = current_quintuple->next_state;
>>>> u32 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 == Quintuple_List.end())
>>>> return false;
>>>> current_quintuple = next_quintuple;
>>>> return true;
>>>> }
>>>
>>> If you are going to use C++ for this then at least create proper
>>> abstractions rather than a struct containing anonymous types. At the
>>
>> It is not a struct containing anonymous types they are fixed width
>> unsigned integers. I could have just used int and unsigned char, I
>> will change it.
>
> It is obvious that they are fixed width unsigned integers but that
> doesn't tell us anything about what they actually are apart from being
> represented as integers, 'state_t' is more meaningful than 'u32':
>
> using state_t = std::uint32_t;
>
> /Flibble
>
We really only need to know that they are integers, the rest of the code
explains how everything fits together. I want to make my TM interpreter
as simple as possible.
The purpose of this thread is to simply confirm that the implementation
of meets the specs:
THESE ARE THE SPECS:
For example, the quintuple 'SCcsm' is executed by the machine:
If it is in state 'S' and is reading the symbol 'C' on the tape then
(a) make a transition to state 's'.
(b) overwrite the symbol 'C' on the tape with the symbol 'c'.
// Must do this before transition to state 's' or we lose 'c' from S.
(c) move the tape reading head one symbol to the left or right
according to whether 'm' is 'l' or 'r'.
THIS IS THE IMPLEMENTATION:
struct Quintuple
{
int state;
int symbol;
int write_symbol;
int next_state;
unsigned char 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);
};
}
bool transition_function(std::set<Quintuple>::iterator& current_quintuple)
{
u32 next_state = current_quintuple->next_state;
u32 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 == Quintuple_List.end())
return false;
current_quintuple = next_quintuple;
return true;
}
--
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-07 13:02 +0100 |
| Message-ID | <20220507130216.00006cd3@reddwarf.jmc> |
| In reply to | #49900 |
On Fri, 6 May 2022 17:08:40 -0500
olcott <polcott2@gmail.com> wrote:
> On 5/6/2022 4:29 PM, Mr Flibble wrote:
> > On Fri, 6 May 2022 16:25:58 -0500
> > olcott <polcott2@gmail.com> wrote:
> >
> >> On 5/6/2022 4:08 PM, Mr Flibble wrote:
> >>> On Fri, 6 May 2022 15:53:58 -0500
> >>> olcott <polcott2@gmail.com> wrote:
> >>>
> >>>> A turing machine is a model of a computer. It has a finite
> >>>> number of states, and it is capable of reading and modifying a
> >>>> tape. A turing machine program consists of a list of
> >>>> 'quintuples', each one of which is a five-symbol turing machine
> >>>> instruction. For example, the quintuple 'SCcsm' is executed by
> >>>> the machine if it is in state 'S' and is reading the symbol 'C'
> >>>> on the tape. In that case, the instruction causes the machine
> >>>> to make a transition to state 's' and to overwrite the symbol
> >>>> 'C' on the tape with the symbol 'c'. The last operation it
> >>>> performs under this instruction is to move the tape reading head
> >>>> one symbol to the left or right according to whether 'm' is 'l'
> >>>> or 'r'. http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
> >>>>
> >>>> For example, the quintuple 'SCcsm' is executed by the machine:
> >>>>
> >>>> If it is in state 'S' and is reading the symbol 'C' on the tape
> >>>> then (a) make a transition to state 's'.
> >>>> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
> >>>> // Must do this before transition to state 's' or we lose
> >>>> 'c' from S. (c) move the tape reading head one symbol to the left
> >>>> or right according to whether 'm' is 'l' or 'r'.
> >>>>
> >>>> 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);
> >>>> };
> >>>> }
> >>>>
> >>>> bool transition_function(std::set<Quintuple>::iterator&
> >>>> current_quintuple) {
> >>>> u32 next_state = current_quintuple->next_state;
> >>>> u32 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 == Quintuple_List.end())
> >>>> return false;
> >>>> current_quintuple = next_quintuple;
> >>>> return true;
> >>>> }
> >>>
> >>> If you are going to use C++ for this then at least create proper
> >>> abstractions rather than a struct containing anonymous types. At
> >>> the
> >>
> >> It is not a struct containing anonymous types they are fixed width
> >> unsigned integers. I could have just used int and unsigned char, I
> >> will change it.
> >
> > It is obvious that they are fixed width unsigned integers but that
> > doesn't tell us anything about what they actually are apart from
> > being represented as integers, 'state_t' is more meaningful than
> > 'u32':
> >
> > using state_t = std::uint32_t;
> >
> > /Flibble
> >
>
> We really only need to know that they are integers, the rest of the
> code explains how everything fits together. I want to make my TM
> interpreter as simple as possible.
>
> The purpose of this thread is to simply confirm that the
> implementation of meets the specs:
>
> THESE ARE THE SPECS:
> For example, the quintuple 'SCcsm' is executed by the machine:
>
> If it is in state 'S' and is reading the symbol 'C' on the tape then
> (a) make a transition to state 's'.
> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
> // Must do this before transition to state 's' or we lose 'c'
> from S. (c) move the tape reading head one symbol to the left or right
> according to whether 'm' is 'l' or 'r'.
>
> THIS IS THE IMPLEMENTATION:
> struct Quintuple
> {
> int state;
> int symbol;
> int write_symbol;
> int next_state;
> unsigned char 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);
> };
> }
>
> bool transition_function(std::set<Quintuple>::iterator&
> current_quintuple) {
> u32 next_state = current_quintuple->next_state;
> u32 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 == Quintuple_List.end())
> return false;
> current_quintuple = next_quintuple;
> return true;
> }
Using 'int' directly just makes matters worse as far as writing code
which is easy to understand is concerned. Create named typedefs whose
names describe what the type actually is.
using state_t = std::uint32_t.
Also if there are a finite number of states then consider using an
enum.
/Flibble
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2022-05-06 14:41 -0700 |
| Message-ID | <0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com> |
| In reply to | #49894 |
On Friday, 6 May 2022 at 22:26:03 UTC+1, olcott wrote:
> On 5/6/2022 4:08 PM, Mr Flibble wrote:
> > On Fri, 6 May 2022 15:53:58 -0500
> > olcott <polc...@gmail.com> wrote:
> >
> >> A turing machine is a model of a computer. It has a finite number of
> >> states, and it is capable of reading and modifying a tape. A turing
> >> machine program consists of a list of 'quintuples', each one of which
> >> is a five-symbol turing machine instruction. For example, the
> >> quintuple 'SCcsm' is executed by the machine if it is in state 'S'
> >> and is reading the symbol 'C' on the tape. In that case, the
> >> instruction causes the machine to make a transition to state 's' and
> >> to overwrite the symbol 'C' on the tape with the symbol 'c'. The
> >> last operation it performs under this instruction is to move the tape
> >> reading head one symbol to the left or right according to whether 'm'
> >> is 'l' or 'r'. http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
> >>
> >> For example, the quintuple 'SCcsm' is executed by the machine:
> >>
> >> If it is in state 'S' and is reading the symbol 'C' on the tape then
> >> (a) make a transition to state 's'.
> >> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
> >> // Must do this before transition to state 's' or we lose 'c'
> >> from S. (c) move the tape reading head one symbol to the left or right
> >> according to whether 'm' is 'l' or 'r'.
> >>
> >> 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);
> >> };
> >> }
> >>
> >> bool transition_function(std::set<Quintuple>::iterator&
> >> current_quintuple) {
> >> u32 next_state = current_quintuple->next_state;
> >> u32 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 == Quintuple_List.end())
> >> return false;
> >> current_quintuple = next_quintuple;
> >> return true;
> >> }
> >
> > If you are going to use C++ for this then at least create proper
> > abstractions rather than a struct containing anonymous types. At the
> It is not a struct containing anonymous types they are fixed width
> unsigned integers. I could have just used int and unsigned char, I will
> change it.
> > very least created named typedefs for things rather than the anonymous
> > 'u32' etc.
> >
> > /Flibble
> >
> >
> It is all in a pair of C++ classes, I didn't want to show all of the
> pages, (1) They are not done yet (2) The distract attention way from the
> only function that I need reviewed.
>
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.
You can probably get away with chars for the symbols. Few people work with Turing
machines with a large number of symbols.
Since the tape cannot in reality be infinite, you might consider throwing an exception
when it goes out of bounds.
I'd rename "Quintuple_List", "TuringMachine". Of course in your system, a Turing
machine is a quintuple list, so it's moot which name is better. But if you make the
list private, you can shift to another representation whilst keeping the interfaces the
same.
[toc] | [prev] | [next] | [standalone]
| From | olcott <polcott2@gmail.com> |
|---|---|
| Date | 2022-05-06 17:02 -0500 |
| Message-ID | <t545tm$u69$1@dont-email.me> |
| In reply to | #49897 |
On 5/6/2022 4:41 PM, Malcolm McLean wrote:
> On Friday, 6 May 2022 at 22:26:03 UTC+1, olcott wrote:
>> On 5/6/2022 4:08 PM, Mr Flibble wrote:
>>> On Fri, 6 May 2022 15:53:58 -0500
>>> olcott <polc...@gmail.com> wrote:
>>>
>>>> A turing machine is a model of a computer. It has a finite number of
>>>> states, and it is capable of reading and modifying a tape. A turing
>>>> machine program consists of a list of 'quintuples', each one of which
>>>> is a five-symbol turing machine instruction. For example, the
>>>> quintuple 'SCcsm' is executed by the machine if it is in state 'S'
>>>> and is reading the symbol 'C' on the tape. In that case, the
>>>> instruction causes the machine to make a transition to state 's' and
>>>> to overwrite the symbol 'C' on the tape with the symbol 'c'. The
>>>> last operation it performs under this instruction is to move the tape
>>>> reading head one symbol to the left or right according to whether 'm'
>>>> is 'l' or 'r'. http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
>>>>
>>>> For example, the quintuple 'SCcsm' is executed by the machine:
>>>>
>>>> If it is in state 'S' and is reading the symbol 'C' on the tape then
>>>> (a) make a transition to state 's'.
>>>> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
>>>> // Must do this before transition to state 's' or we lose 'c'
>>>> from S. (c) move the tape reading head one symbol to the left or right
>>>> according to whether 'm' is 'l' or 'r'.
>>>>
>>>> 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);
>>>> };
>>>> }
>>>>
>>>> bool transition_function(std::set<Quintuple>::iterator&
>>>> current_quintuple) {
>>>> u32 next_state = current_quintuple->next_state;
>>>> u32 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 == Quintuple_List.end())
>>>> return false;
>>>> current_quintuple = next_quintuple;
>>>> return true;
>>>> }
>>>
>>> If you are going to use C++ for this then at least create proper
>>> abstractions rather than a struct containing anonymous types. At the
>> It is not a struct containing anonymous types they are fixed width
>> unsigned integers. I could have just used int and unsigned char, I will
>> change it.
>>> very least created named typedefs for things rather than the anonymous
>>> 'u32' etc.
>>>
>>> /Flibble
>>>
>>>
>> It is all in a pair of C++ classes, I didn't want to show all of the
>> pages, (1) They are not done yet (2) The distract attention way from the
>> only function that I need reviewed.
>>
> 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.
> You can probably get away with chars for the symbols. Few people work with Turing
> machines with a large number of symbols.
My initial vision was to use unsigned 8-bit integers and let the data be
quintuples be defined by ASCII chars, as it is in my model system.
All this cane be defined on the parse side, leaving int as the
underlying size.
> Since the tape cannot in reality be infinite, you might consider throwing an exception
> when it goes out of bounds.
Or put it in a std::vector and grow it as needed.
I think that the conventional TM has a tape with a beginning, thus a
tape_head move to before the beginning would be an error.
> I'd rename "Quintuple_List", "TuringMachine". Of course in your system, a Turing
> machine is a quintuple list, so it's moot which name is better. But if you make the
> list private, you can shift to another representation whilst keeping the interfaces the
> same.
>
I thought that States was a fine name.
--
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 | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2022-05-06 15:36 -0700 |
| Message-ID | <bdfe868a-80d1-4eaf-a86a-f5bd25e2d842n@googlegroups.com> |
| In reply to | #49899 |
On Friday, 6 May 2022 at 23:02:33 UTC+1, olcott wrote:
> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
> > On Friday, 6 May 2022 at 22:26:03 UTC+1, olcott wrote:
> >> On 5/6/2022 4:08 PM, Mr Flibble wrote:
> >>> On Fri, 6 May 2022 15:53:58 -0500
> >>> olcott <polc...@gmail.com> wrote:
> >>>
> >>>> A turing machine is a model of a computer. It has a finite number of
> >>>> states, and it is capable of reading and modifying a tape. A turing
> >>>> machine program consists of a list of 'quintuples', each one of which
> >>>> is a five-symbol turing machine instruction. For example, the
> >>>> quintuple 'SCcsm' is executed by the machine if it is in state 'S'
> >>>> and is reading the symbol 'C' on the tape. In that case, the
> >>>> instruction causes the machine to make a transition to state 's' and
> >>>> to overwrite the symbol 'C' on the tape with the symbol 'c'. The
> >>>> last operation it performs under this instruction is to move the tape
> >>>> reading head one symbol to the left or right according to whether 'm'
> >>>> is 'l' or 'r'. http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
> >>>>
> >>>> For example, the quintuple 'SCcsm' is executed by the machine:
> >>>>
> >>>> If it is in state 'S' and is reading the symbol 'C' on the tape then
> >>>> (a) make a transition to state 's'.
> >>>> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
> >>>> // Must do this before transition to state 's' or we lose 'c'
> >>>> from S. (c) move the tape reading head one symbol to the left or right
> >>>> according to whether 'm' is 'l' or 'r'.
> >>>>
> >>>> 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);
> >>>> };
> >>>> }
> >>>>
> >>>> bool transition_function(std::set<Quintuple>::iterator&
> >>>> current_quintuple) {
> >>>> u32 next_state = current_quintuple->next_state;
> >>>> u32 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 == Quintuple_List.end())
> >>>> return false;
> >>>> current_quintuple = next_quintuple;
> >>>> return true;
> >>>> }
> >>>
> >>> If you are going to use C++ for this then at least create proper
> >>> abstractions rather than a struct containing anonymous types. At the
> >> It is not a struct containing anonymous types they are fixed width
> >> unsigned integers. I could have just used int and unsigned char, I will
> >> change it.
> >>> very least created named typedefs for things rather than the anonymous
> >>> 'u32' etc.
> >>>
> >>> /Flibble
> >>>
> >>>
> >> It is all in a pair of C++ classes, I didn't want to show all of the
> >> pages, (1) They are not done yet (2) The distract attention way from the
> >> only function that I need reviewed.
> >>
> > 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.
> > You can probably get away with chars for the symbols. Few people work with Turing
> > machines with a large number of symbols.
> My initial vision was to use unsigned 8-bit integers and let the data be
> quintuples be defined by ASCII chars, as it is in my model system.
> All this cane be defined on the parse side, leaving int as the
> underlying size.
>
If you use chars for the symbols, you can make the tape human-readable. Which
might help.
But as you say, you can manipulate the symbols internally as 32 bit integers if
you want, even if in reality they are constrained to take the values "1", "0" and
"blank".
[toc] | [prev] | [next] | [standalone]
| From | olcott <polcott2@gmail.com> |
|---|---|
| Date | 2022-05-06 17:54 -0500 |
| Message-ID | <t548uc$hh4$1@dont-email.me> |
| In reply to | #49901 |
On 5/6/2022 5:36 PM, Malcolm McLean wrote:
> On Friday, 6 May 2022 at 23:02:33 UTC+1, olcott wrote:
>> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
>>> On Friday, 6 May 2022 at 22:26:03 UTC+1, olcott wrote:
>>>> On 5/6/2022 4:08 PM, Mr Flibble wrote:
>>>>> On Fri, 6 May 2022 15:53:58 -0500
>>>>> olcott <polc...@gmail.com> wrote:
>>>>>
>>>>>> A turing machine is a model of a computer. It has a finite number of
>>>>>> states, and it is capable of reading and modifying a tape. A turing
>>>>>> machine program consists of a list of 'quintuples', each one of which
>>>>>> is a five-symbol turing machine instruction. For example, the
>>>>>> quintuple 'SCcsm' is executed by the machine if it is in state 'S'
>>>>>> and is reading the symbol 'C' on the tape. In that case, the
>>>>>> instruction causes the machine to make a transition to state 's' and
>>>>>> to overwrite the symbol 'C' on the tape with the symbol 'c'. The
>>>>>> last operation it performs under this instruction is to move the tape
>>>>>> reading head one symbol to the left or right according to whether 'm'
>>>>>> is 'l' or 'r'. http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
>>>>>>
>>>>>> For example, the quintuple 'SCcsm' is executed by the machine:
>>>>>>
>>>>>> If it is in state 'S' and is reading the symbol 'C' on the tape then
>>>>>> (a) make a transition to state 's'.
>>>>>> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
>>>>>> // Must do this before transition to state 's' or we lose 'c'
>>>>>> from S. (c) move the tape reading head one symbol to the left or right
>>>>>> according to whether 'm' is 'l' or 'r'.
>>>>>>
>>>>>> 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);
>>>>>> };
>>>>>> }
>>>>>>
>>>>>> bool transition_function(std::set<Quintuple>::iterator&
>>>>>> current_quintuple) {
>>>>>> u32 next_state = current_quintuple->next_state;
>>>>>> u32 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 == Quintuple_List.end())
>>>>>> return false;
>>>>>> current_quintuple = next_quintuple;
>>>>>> return true;
>>>>>> }
>>>>>
>>>>> If you are going to use C++ for this then at least create proper
>>>>> abstractions rather than a struct containing anonymous types. At the
>>>> It is not a struct containing anonymous types they are fixed width
>>>> unsigned integers. I could have just used int and unsigned char, I will
>>>> change it.
>>>>> very least created named typedefs for things rather than the anonymous
>>>>> 'u32' etc.
>>>>>
>>>>> /Flibble
>>>>>
>>>>>
>>>> It is all in a pair of C++ classes, I didn't want to show all of the
>>>> pages, (1) They are not done yet (2) The distract attention way from the
>>>> only function that I need reviewed.
>>>>
>>> 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.
>>> You can probably get away with chars for the symbols. Few people work with Turing
>>> machines with a large number of symbols.
>> My initial vision was to use unsigned 8-bit integers and let the data be
>> quintuples be defined by ASCII chars, as it is in my model system.
>> All this cane be defined on the parse side, leaving int as the
>> underlying size.
>>
> If you use chars for the symbols, you can make the tape human-readable. Which
> might help.
> But as you say, you can manipulate the symbols internally as 32 bit integers if
> you want, even if in reality they are constrained to take the values "1", "0" and
> "blank".
>
They are constrained to any value that unsigned int can hold.
The parse side will initially only be 7-bit ASCII to make it compatible
with the TM interpreter 7-bit TM code examples. The other {8,16,32} bit
parses will be all be in hexadecimal. (I may skip 8, and 16 bits).
--
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-07 00:39 +0100 |
| Message-ID | <t54bkf$g23$1@gioia.aioe.org> |
| In reply to | #49899 |
On 06/05/2022 23:02, olcott wrote:
> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
>> On Friday, 6 May 2022 at 22:26:03 UTC+1, olcott wrote:
>>> On 5/6/2022 4:08 PM, Mr Flibble wrote:
>>>> On Fri, 6 May 2022 15:53:58 -0500
>>>> olcott <polc...@gmail.com> wrote:
>>>>
>>>>> A turing machine is a model of a computer. It has a finite number of
>>>>> states, and it is capable of reading and modifying a tape. A turing
>>>>> machine program consists of a list of 'quintuples', each one of which
>>>>> is a five-symbol turing machine instruction. For example, the
>>>>> quintuple 'SCcsm' is executed by the machine if it is in state 'S'
>>>>> and is reading the symbol 'C' on the tape. In that case, the
>>>>> instruction causes the machine to make a transition to state 's' and
>>>>> to overwrite the symbol 'C' on the tape with the symbol 'c'. The
>>>>> last operation it performs under this instruction is to move the tape
>>>>> reading head one symbol to the left or right according to whether 'm'
>>>>> is 'l' or 'r'. http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
>>>>>
>>>>> For example, the quintuple 'SCcsm' is executed by the machine:
>>>>>
>>>>> If it is in state 'S' and is reading the symbol 'C' on the tape then
>>>>> (a) make a transition to state 's'.
>>>>> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
>>>>> // Must do this before transition to state 's' or we lose 'c'
>>>>> from S. (c) move the tape reading head one symbol to the left or right
>>>>> according to whether 'm' is 'l' or 'r'.
>>>>>
>>>>> 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);
>>>>> };
>>>>> }
>>>>>
>>>>> bool transition_function(std::set<Quintuple>::iterator&
>>>>> current_quintuple) {
>>>>> u32 next_state = current_quintuple->next_state;
>>>>> u32 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 == Quintuple_List.end())
>>>>> return false;
>>>>> current_quintuple = next_quintuple;
>>>>> return true;
>>>>> }
>>>>
>>>> If you are going to use C++ for this then at least create proper
>>>> abstractions rather than a struct containing anonymous types. At the
>>> It is not a struct containing anonymous types they are fixed width
>>> unsigned integers. I could have just used int and unsigned char, I will
>>> change it.
>>>> very least created named typedefs for things rather than the anonymous
>>>> 'u32' etc.
>>>>
>>>> /Flibble
>>>>
>>>>
>>> It is all in a pair of C++ classes, I didn't want to show all of the
>>> pages, (1) They are not done yet (2) The distract attention way from the
>>> only function that I need reviewed.
>>>
>> 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.
>
>> You can probably get away with chars for the symbols. Few people work with Turing
>> machines with a large number of symbols.
>
> My initial vision was to use unsigned 8-bit integers and let the data be quintuples be defined by
> ASCII chars, as it is in my model system.
> All this cane be defined on the parse side, leaving int as the underlying size.
>
>> Since the tape cannot in reality be infinite, you might consider throwing an exception
>> when it goes out of bounds.
>
> Or put it in a std::vector and grow it as needed.
> I think that the conventional TM has a tape with a beginning, thus a tape_head move to before the
> beginning would be an error.
>
>> I'd rename "Quintuple_List", "TuringMachine". Of course in your system, a Turing
>> machine is a quintuple list, so it's moot which name is better. But if you make the
>> list private, you can shift to another representation whilst keeping the interfaces the
>> same.
>>
>
> I thought that States was a fine name.
Well you must be confused by what a TM state is - the quintuples do not represent the TM states as
lots of people have said.
Look, check your favourite Linz book, figure 9.7 (in my edition; the figure for Example 9.10 "Design
a TM that copiess strings of 1's"). You see there are several CIRCLES joined by annotated ARROWS?
The TM states are THE LITTLE CIRCLES, with their state names q0, q1... written inside.
Your quintuples are the equivalent of THE *ARROWS* in the figure. So, not states at all. Someone
suggested "rules", which is what I might have chosen.
Your E TM will probably end up with around 5 circles and 6 arrows (if you go with your binary number
tape representation) so if you need an emulator to debug your E and check you've got it right that
doesn't say much for your problem solving skills! :)
Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <polcott2@gmail.com> |
|---|---|
| Date | 2022-05-06 18:54 -0500 |
| Message-ID | <t54cfo$7gm$1@dont-email.me> |
| In reply to | #49903 |
On 5/6/2022 6:39 PM, Mike Terry wrote:
> On 06/05/2022 23:02, olcott wrote:
>> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
>>> On Friday, 6 May 2022 at 22:26:03 UTC+1, olcott wrote:
>>>> On 5/6/2022 4:08 PM, Mr Flibble wrote:
>>>>> On Fri, 6 May 2022 15:53:58 -0500
>>>>> olcott <polc...@gmail.com> wrote:
>>>>>
>>>>>> A turing machine is a model of a computer. It has a finite number of
>>>>>> states, and it is capable of reading and modifying a tape. A turing
>>>>>> machine program consists of a list of 'quintuples', each one of which
>>>>>> is a five-symbol turing machine instruction. For example, the
>>>>>> quintuple 'SCcsm' is executed by the machine if it is in state 'S'
>>>>>> and is reading the symbol 'C' on the tape. In that case, the
>>>>>> instruction causes the machine to make a transition to state 's' and
>>>>>> to overwrite the symbol 'C' on the tape with the symbol 'c'. The
>>>>>> last operation it performs under this instruction is to move the tape
>>>>>> reading head one symbol to the left or right according to whether 'm'
>>>>>> is 'l' or 'r'. http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
>>>>>>
>>>>>> For example, the quintuple 'SCcsm' is executed by the machine:
>>>>>>
>>>>>> If it is in state 'S' and is reading the symbol 'C' on the tape then
>>>>>> (a) make a transition to state 's'.
>>>>>> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
>>>>>> // Must do this before transition to state 's' or we lose 'c'
>>>>>> from S. (c) move the tape reading head one symbol to the left or
>>>>>> right
>>>>>> according to whether 'm' is 'l' or 'r'.
>>>>>>
>>>>>> 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);
>>>>>> };
>>>>>> }
>>>>>>
>>>>>> bool transition_function(std::set<Quintuple>::iterator&
>>>>>> current_quintuple) {
>>>>>> u32 next_state = current_quintuple->next_state;
>>>>>> u32 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 == Quintuple_List.end())
>>>>>> return false;
>>>>>> current_quintuple = next_quintuple;
>>>>>> return true;
>>>>>> }
>>>>>
>>>>> If you are going to use C++ for this then at least create proper
>>>>> abstractions rather than a struct containing anonymous types. At the
>>>> It is not a struct containing anonymous types they are fixed width
>>>> unsigned integers. I could have just used int and unsigned char, I will
>>>> change it.
>>>>> very least created named typedefs for things rather than the anonymous
>>>>> 'u32' etc.
>>>>>
>>>>> /Flibble
>>>>>
>>>>>
>>>> It is all in a pair of C++ classes, I didn't want to show all of the
>>>> pages, (1) They are not done yet (2) The distract attention way from
>>>> the
>>>> only function that I need reviewed.
>>>>
>>> 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.
>>
>>> You can probably get away with chars for the symbols. Few people work
>>> with Turing
>>> machines with a large number of symbols.
>>
>> My initial vision was to use unsigned 8-bit integers and let the data
>> be quintuples be defined by ASCII chars, as it is in my model system.
>> All this cane be defined on the parse side, leaving int as the
>> underlying size.
>>
>>> Since the tape cannot in reality be infinite, you might consider
>>> throwing an exception
>>> when it goes out of bounds.
>>
>> Or put it in a std::vector and grow it as needed.
>> I think that the conventional TM has a tape with a beginning, thus a
>> tape_head move to before the beginning would be an error.
>>
>>> I'd rename "Quintuple_List", "TuringMachine". Of course in your
>>> system, a Turing
>>> machine is a quintuple list, so it's moot which name is better. But
>>> if you make the
>>> list private, you can shift to another representation whilst keeping
>>> the interfaces the
>>> same.
>>>
>>
>> I thought that States was a fine name.
>
> Well you must be confused by what a TM state is - the quintuples do not
> represent the TM states as lots of people have said.
>
> Look, check your favourite Linz book, figure 9.7 (in my edition; the
> figure for Example 9.10 "Design a TM that copiess strings of 1's"). You
> see there are several CIRCLES joined by annotated ARROWS?
>
> The TM states are THE LITTLE CIRCLES, with their state names q0, q1...
> written inside.
>
AKA directed graphs the abstract away key details of the actions
required by a state transitions. We can ignore these actions when we are
presenting a high level overview in directed graphs. The actual state
transitions require these actions and can't possibly work correctly
without them.
> Your quintuples are the equivalent of THE *ARROWS* in the figure. So,
> not states at all. Someone suggested "rules", which is what I might
> have chosen.
>
OK that makes perfect sense.
> Your E TM will probably end up with around 5 circles and 6 arrows (if
> you go with your binary number tape representation) so if you need an
> emulator to debug your E and check you've got it right that doesn't say
> much for your problem solving skills! :)
>
> Mike.
So you didn't find any errors in my transition_function?
I got all the code to compile now. I can adapt the TM interpreter
examples: http://www.lns.mit.edu/~dsw/turing/examples/examples.html
--
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:54 +0100 |
| Message-ID | <87h762yxg6.fsf@bsb.me.uk> |
| In reply to | #49899 |
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. Do you know how to
get it to work? The result will not be a natural use of a 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 <polcott2@gmail.com> |
|---|---|
| Date | 2022-05-06 20:05 -0500 |
| Message-ID | <t54gl1$cp$1@dont-email.me> |
| In reply to | #49913 |
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.
> 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.
I decided to make my system exactly compatible with these code samples:
http://www.lns.mit.edu/~dsw/turing/examples/examples.html
--
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 23:21 +0100 |
| Message-ID | <87a6btx9uz.fsf@bsb.me.uk> |
| In reply to | #49916 |
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.
> 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.
--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)
[toc] | [prev] | [next] | [standalone]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2022-05-07 19:57 -0600 |
| Message-ID | <t5782u$1p6$1@dont-email.me> |
| In reply to | #49975 |
On 5/7/2022 4: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.
>
>> 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.
Questions:
Was 47 million steps a measured or a theoretically computed measure?
How long would you estimate that a well-written TM interpreter on modern
hardware needs to interpret the above? A few seconds or minutes?
--
Jeff Barnett
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-05-08 07:34 -0400 |
| Message-ID | <zVNdK.10345$Awz.6657@fx03.iad> |
| In reply to | #50007 |
On 5/7/22 9:57 PM, Jeff Barnett wrote:
> On 5/7/2022 4: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.
>>
>>> 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.
>
> Questions:
>
> Was 47 million steps a measured or a theoretically computed measure?
>
> How long would you estimate that a well-written TM interpreter on modern
> hardware needs to interpret the above? A few seconds or minutes?
A well written TM interpreter on modern hardware should be able to do
many millions of steps a second (as I posted a main loop that can do
that), so we are in seconds.
IF we need to generate a trace that can be inspected by a human, we
likely get I/O bound generating that trace, and it may go to order of
minutes to maybe hours
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2022-05-08 05:11 -0700 |
| Message-ID | <8783735f-7f11-4914-9724-044c3b57831en@googlegroups.com> |
| In reply to | #50021 |
On Sunday, 8 May 2022 at 12:35:00 UTC+1, richar...@gmail.com wrote:
> On 5/7/22 9:57 PM, Jeff Barnett wrote:
> > On 5/7/2022 4:21 PM, Ben wrote:
> >> olcott <polc...@gmail.com> writes:
> >>
> >>> On 5/6/2022 7:54 PM, Ben wrote:
> >>>> olcott <polc...@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.
> >>
> >>> 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.
> >
> > Questions:
> >
> > Was 47 million steps a measured or a theoretically computed measure?
> >
> > How long would you estimate that a well-written TM interpreter on modern
> > hardware needs to interpret the above? A few seconds or minutes?
> A well written TM interpreter on modern hardware should be able to do
> many millions of steps a second (as I posted a main loop that can do
> that), so we are in seconds.
>
> IF we need to generate a trace that can be inspected by a human, we
> likely get I/O bound generating that trace, and it may go to order of
> minutes to maybe hours
>
Whilst you might write a pure implementation of a Turing machine as a
first step, you're unlikely to use it much. People want to see the machine
buzz and whir away, as it performs its magic.
So that means some sort of graphical interface. Which is orders of
magnitude slower than a simple virtual machine.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-05-08 14:20 -0400 |
| Message-ID | <PRTdK.8710$t72a.4785@fx10.iad> |
| In reply to | #50025 |
On 5/8/22 8:11 AM, Malcolm McLean wrote:
> On Sunday, 8 May 2022 at 12:35:00 UTC+1, richar...@gmail.com wrote:
>> On 5/7/22 9:57 PM, Jeff Barnett wrote:
>>> On 5/7/2022 4:21 PM, Ben wrote:
>>>> olcott <polc...@gmail.com> writes:
>>>>
>>>>> On 5/6/2022 7:54 PM, Ben wrote:
>>>>>> olcott <polc...@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.
>>>>
>>>>> 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.
>>>
>>> Questions:
>>>
>>> Was 47 million steps a measured or a theoretically computed measure?
>>>
>>> How long would you estimate that a well-written TM interpreter on modern
>>> hardware needs to interpret the above? A few seconds or minutes?
>> A well written TM interpreter on modern hardware should be able to do
>> many millions of steps a second (as I posted a main loop that can do
>> that), so we are in seconds.
>>
>> IF we need to generate a trace that can be inspected by a human, we
>> likely get I/O bound generating that trace, and it may go to order of
>> minutes to maybe hours
>>
> Whilst you might write a pure implementation of a Turing machine as a
> first step, you're unlikely to use it much. People want to see the machine
> buzz and whir away, as it performs its magic.
> So that means some sort of graphical interface. Which is orders of
> magnitude slower than a simple virtual machine.
Yes, if you want to watch the machine run, you are limiting your step
rate to Human speed.
If you can watch 1 step a second, the 47 million steps is on the order
of a year and a half at 24-7, but then the limiting factor isn't the
computer but the observer.
You could probably "checkpoint" the results every, say, 1000 steps to
some log, and then build a browser to let you pull up any of the 47,000
checkpoints to see the progress, and maybe do a step by step run from
the checkpoint if interested.
The key point is that the computer running the Turing Machine isn't the
limiting factor for this case, but the human observer.
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-08 19:59 +0100 |
| Message-ID | <87fslju9xv.fsf@bsb.me.uk> |
| In reply to | #50025 |
Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> On Sunday, 8 May 2022 at 12:35:00 UTC+1, richar...@gmail.com wrote:
>> On 5/7/22 9:57 PM, Jeff Barnett wrote:
>> > On 5/7/2022 4:21 PM, Ben wrote:
>> >> Here's an interesting test case that's useful for timing and so on:
>> >>
>> >> A_1RB
>> >> A11LC
>> >> B_1RC
>> >> B11RB
>> >> C_1RD
>> >> C1_LE
>> >> D_1LA
>> >> D11LD
>> >> E_1RH
>> >> E1_LA
>> >>
>> >> You will need to add a '(' for DSW compatibility. Also, note that my
>> >> interpreter uses _ as the tape's blank symbol. Change all _s to an
>> >> actual spaces if that's what you use.
>> >>
>> >> This is (as far as I know) the current BB(5) champion. It runs for more
>> >> that 47 million steps before halting.
>> >
>> > Questions:
>> >
>> > Was 47 million steps a measured or a theoretically computed measure?
>> >
>> > How long would you estimate that a well-written TM interpreter on modern
>> > hardware needs to interpret the above? A few seconds or minutes?
>> A well written TM interpreter on modern hardware should be able to do
>> many millions of steps a second (as I posted a main loop that can do
>> that), so we are in seconds.
>>
>> IF we need to generate a trace that can be inspected by a human, we
>> likely get I/O bound generating that trace, and it may go to order of
>> minutes to maybe hours
>>
> Whilst you might write a pure implementation of a Turing machine as a
> first step, you're unlikely to use it much. People want to see the machine
> buzz and whir away, as it performs its magic.
> So that means some sort of graphical interface. Which is orders of
> magnitude slower than a simple virtual machine.
You don't really need much. A simple print of the tape (centred on the
head) give the feel for what's happening. Throw in a \r and a delay and
will look like an animation even in a plain tty.
With tracing turned on, my simple implementation shows this for the
BB(4) champion:
$ ./simple-tm bb-4-2 ""
A B C D H
1 1LB _LC 1LD _RA
_ 1RB 1LA 1RH 1RD
________________________________[A|_]_________________________________
________________________________[B|_]_________________________________
________________________________[A|_]_________________________________
_______________________________1[B|_]_________________________________
________________________________[A|1]1________________________________
________________________________[B|_]11_______________________________
________________________________[A|_]111______________________________
_______________________________1[B|1]11_______________________________
________________________________[C|1]_11______________________________
________________________________[D|_]1_11_____________________________
_______________________________1[D|1]_11______________________________
______________________________1_[A|_]11_______________________________
_____________________________1_1[B|1]1________________________________
______________________________1_[C|1]_1_______________________________
_______________________________1[D|_]1_1______________________________
______________________________11[D|1]_1_______________________________
_____________________________11_[A|_]1________________________________
____________________________11_1[B|1]_________________________________
_____________________________11_[C|1]_________________________________
______________________________11[D|_]1________________________________
_____________________________111[D|1]_________________________________
____________________________111_[A|_]_________________________________
___________________________111_1[B|_]_________________________________
____________________________111_[A|1]1________________________________
_____________________________111[B|_]11_______________________________
______________________________11[A|1]111______________________________
_______________________________1[B|1]1111_____________________________
________________________________[C|1]_1111____________________________
________________________________[D|_]1_1111___________________________
_______________________________1[D|1]_1111____________________________
______________________________1_[A|_]1111_____________________________
_____________________________1_1[B|1]111______________________________
______________________________1_[C|1]_111_____________________________
_______________________________1[D|_]1_111____________________________
______________________________11[D|1]_111_____________________________
_____________________________11_[A|_]111______________________________
____________________________11_1[B|1]11_______________________________
_____________________________11_[C|1]_11______________________________
______________________________11[D|_]1_11_____________________________
_____________________________111[D|1]_11______________________________
____________________________111_[A|_]11_______________________________
___________________________111_1[B|1]1________________________________
____________________________111_[C|1]_1_______________________________
_____________________________111[D|_]1_1______________________________
____________________________1111[D|1]_1_______________________________
___________________________1111_[A|_]1________________________________
__________________________1111_1[B|1]_________________________________
___________________________1111_[C|1]_________________________________
____________________________1111[D|_]1________________________________
___________________________11111[D|1]_________________________________
__________________________11111_[A|_]_________________________________
_________________________11111_1[B|_]_________________________________
__________________________11111_[A|1]1________________________________
___________________________11111[B|_]11_______________________________
____________________________1111[A|1]111______________________________
_____________________________111[B|1]1111_____________________________
______________________________11[C|1]_1111____________________________
_______________________________1[D|1]1_1111___________________________
______________________________1_[A|1]_1111____________________________
_______________________________1[B|_]1_1111___________________________
________________________________[A|1]11_1111__________________________
________________________________[B|_]111_1111_________________________
________________________________[A|_]1111_1111________________________
_______________________________1[B|1]111_1111_________________________
________________________________[C|1]_111_1111________________________
________________________________[D|_]1_111_1111_______________________
_______________________________1[D|1]_111_1111________________________
______________________________1_[A|_]111_1111_________________________
_____________________________1_1[B|1]11_1111__________________________
______________________________1_[C|1]_11_1111_________________________
_______________________________1[D|_]1_11_1111________________________
______________________________11[D|1]_11_1111_________________________
_____________________________11_[A|_]11_1111__________________________
____________________________11_1[B|1]1_1111___________________________
_____________________________11_[C|1]_1_1111__________________________
______________________________11[D|_]1_1_1111_________________________
_____________________________111[D|1]_1_1111__________________________
____________________________111_[A|_]1_1111___________________________
___________________________111_1[B|1]_1111____________________________
____________________________111_[C|1]__1111___________________________
_____________________________111[D|_]1__1111__________________________
____________________________1111[D|1]__1111___________________________
___________________________1111_[A|_]_1111____________________________
__________________________1111_1[B|_]1111_____________________________
___________________________1111_[A|1]11111____________________________
____________________________1111[B|_]111111___________________________
_____________________________111[A|1]1111111__________________________
______________________________11[B|1]11111111_________________________
_______________________________1[C|1]_11111111________________________
________________________________[D|1]1_11111111_______________________
________________________________[A|1]_11111111________________________
________________________________[B|_]1_11111111_______________________
________________________________[A|_]11_11111111______________________
_______________________________1[B|1]1_11111111_______________________
________________________________[C|1]_1_11111111______________________
________________________________[D|_]1_1_11111111_____________________
_______________________________1[D|1]_1_11111111______________________
______________________________1_[A|_]1_11111111_______________________
_____________________________1_1[B|1]_11111111________________________
______________________________1_[C|1]__11111111_______________________
_______________________________1[D|_]1__11111111______________________
______________________________11[D|1]__11111111_______________________
_____________________________11_[A|_]_11111111________________________
____________________________11_1[B|_]11111111_________________________
_____________________________11_[A|1]111111111________________________
______________________________11[B|_]1111111111_______________________
_______________________________1[A|1]11111111111______________________
________________________________[B|1]111111111111_____________________
________________________________[C|_]_111111111111____________________
_______________________________1[H|_]111111111111_____________________
steps=109
--
Ben.
[toc] | [prev] | [next] | [standalone]
Page 1 of 10 [1] 2 3 … 10 Next page →
Back to top | Article view | comp.theory
csiph-web